Graphs

Sometimes it seems a graph can represent almost anything....

Definitions

A graph, or network is a data structure that can be used to represent general relationships among a set of elements. The elements are called vertices, nodes, or points; the relationships are called edges or arcs.

Rahter than define terms, we'll illustrate their use in the graph above:

The order of the graph is 16, because it has 16 vertices, $A$...$P$.
The size of the graph is 21, because it has 21 edges, $a$...$u$.
$h$ is an undirected edge, whose endpoints are $N$ and $C$.
$f$ is a directed edge, whose tail is $H$ and whose head is $G$.
$t$ and $i$ are parallel edges; $g$ and $k$ are antiparallel edges.
$r$ and $s$ are loops; all the other edges are links.
$M$ is an isolated node.
$J$ is an articulation point.
$o$ is a bridge.
$C$ and $D$ are adjacent.
$C$ and $j$ are incident.
$G$ has degree 2; $H$ has degree 5.
$A$ has degree $5$, indegree 1, and outdegree 2.
$\langle PrPoJdAgBkAuEuAnF\rangle$ is a walk of length 8, start $P$, and end $F$.
$\langle PrPoJdA\rangle$ is an open walk.
$\langle PrPoJeHsHeJoP\rangle$ is a closed walk.
$\langle AdJeHfG\rangle$ is a path (open walk with no repeated vertices).
$\langle OtChNpO\rangle$ is a cycle (closed walk of length>0 with no repeated vertices other than the first/last, and no repeated edges).
$\langle OtChNpOiCjD\rangle$ is a trail (open walk with no repeated edges)
$\langle AgBkAuElHeJdA\rangle$ is a tour (closed walk with no repeated edges)
The graph is not connected; it has 4 blocks.

There are a few terms that apply only to connected graphs. Consider the block in the graph above containing vertices $\{D, C, O, N\}$ and edges $\{q, p, h, i, t, j\}$:

$\langle OiCjDqN\rangle$ is a Hamilton Path (Hamiltonian: all the vertices).
$\langle DqNpOtCjD\rangle$ is a Hamilton Cycle.
$\langle OtChNpOiCjDqN\rangle$ is an Euler Trail (Eulerian: all the edges).
The block has no Euler Tour.

Uses

Graphs can model, for example

Chips — Electric Pathways
Airports — Flight Paths
Software Modules — Interfaces
Software Functions — Calls
Problem States — Inferences
Chess Board Positions — Moves
Computers — Communication Lines
Tasks — Time Orderings
Cities — Highways
Countries — Borders

Kinds of Graphs

Here are a few types of graphs. The types overlap, of course; you can have a simple, directed, weighted graph.

Connected: consists of only one block
Simple: no parallel edges and no loops
Multi: has parallel edges
Undirected: none of the edges have a direction
Directed: all of the edges have a direction
Mixed: some of the edges have a direction and some do not
Complete: simple, undirected, and every pair of nodes connected by an edge
Labelled: all edges have labels
Weighted: all edges have numeric labels
Acyclic: there are no cycles
Unicyclic: there is exactly one cycle
Pancyclic: has all cycles of length 3 up to order of graph
Tree: acyclic and connected
List: a tree with maximum degree = 2

Exercise: Prove that in a simple graph with $n$ nodes and $e$ edges that $e < n(n-1)/2$.

Exercise: Prove that in a tree with $n$ nodes that the number of edges is $n-1$.

Exercise: Prove that a graph with $n$ nodes and less than $n-1$ edges is not connected.

Implementations

Adjacency Matrix

Rows and columns are indexed by nodes; cells contain the edges (or pointers to edges, really).

	A	B	C	D	E	F	G	H	I	J	K	L	N	O	P
A		g			u	n				d
B	k
C				j									h
D			j										q
E	u							l
F							m
G						m
H					l		f	s,s		e
I											c
J	d							e							o
K												a
L									b
M
N			h	q										p
O			i,t										p
P										o					r

Note that undirected edges appear twice. It is also possible to store only a triangular matrix.

Incidence List

For each node, store the list(s) of its outgoing edges, incoming edges, and incident undirected edges.

Adjacency List

For each node, store a list of the nodes that it is adjacent to.