- Forward


Graphs/Networks
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Notation
Back Forward
  • Getting Started:
    • \(V\) is a non-empty, finite set of vertices (or nodes)
    • \(L\) is a finite set of unordered pairs of distinct elements of \(V\) called links (or edges or arcs)
    • A link \({v,w}\) is said to join the vertices \(v\) and \(w\)
  • Graphs:
    • A simple graph, \(G\), is an ordered pair \((V,L)\)
  • Visualization:
    • images/simple-graph.gif
Simple Graphs
Back Forward
  • Observations:
    • There can never be more than one link joining any two vertices in a simple graph.
    • Since links can only join distinct vertices, simple graphs cannot contain loops
  • Visualization:
    • images/non-simple-graph.gif
General and Directed Graphs
Back Forward
  • General Graph:
    • A general graph (or simply a graph) can contain multiple links between two vertices and loops
  • Directed Graph:
    • In a directed graph (or digraph) the link-set contains ordered pairs of elements of \(V\)
    • images/digraph.gif
Terminology
Back Forward
  • Vertices and Links:
    • Two vertices, \(v\) and \(w\), are said to be adjacent if there is a link joining them, and the two vertices are then said to be incident to such a link
    • The degree (or valency) of a vertex, \(v\), is the number of links incident to it
    • Any vertex of degree 0 is said to be isolated
    • Any vertex of degree 1 is said to be an end-vertex
  • Visualization:
    • images/vertex-degree.gif
Terminology (cont.)
Back Forward
  • A Walk:
    • A finite sequence of arcs of the form \((v_{0}, v_{1}), (v_{1}, v_{2}), ... , (v_{k-1}, v_{k})\)
    • \(v_{0}\) is referred to as the initial vertex and \(v_{k}\) is referred to as the final vertex
  • A Trail:
    • A walk in which all of the arcs are distinct
  • A Path (or Route):
    • A trail in which all of the vertices are distinct
  • A Tour (or Circuit):
    • A path in which \(v_{0} = v_{k}\)
Terminology (cont.)
Back Forward
  • Graphs:
    • A graph whose link-set is empty is called a null graph (or a totally-disconnected graph)
    • A simple graph in which every pair of distinct vertices are adjacent is called a complete graph
    • A graph in which every vertex has the same degree is called a regular graph
    • A graph which contains no tours/circuits is said to be a forest
    • A connected forest is called a tree
    • A spanning tree of a graph is a partial graph (i.e., another graph with the same number of vertices) that forms a tree
  • Visualization:
    • images/graph-types.gif
There's Always More to Learn
Back -