Basic Graph
Theory
Graph theory provides a mathematical structure that is
convenient
for understanding a number of
problems and writing algorithms to solve them.
At one level, graphs are very simple. They are just dots connected by lines.
The “dots”, generally drawn as labeled circles, are
called “vertices” (singular is “vertex”) or “nodes”. The lines are usually called “edges”, but may
be called “links” or “arcs”.
The vertices are generally labeled by positive
integers, but can be labeled otherwise.
In a graph that is read as a map, many of the vertices are labeled with city
names.
One special class of graphs is called “trees”, to be
defined soon.
For some reason, we tend to use the term “node” when
discussing trees
and use the term “vertex” when discussing general graphs.
Definition
of a Graph
We
present two definitions of the mathematical object called a graph.
Definition 1: A
graph is a finite subset of the positive integers, denoted by
V = { 1, 2, …, N }, for N ³ 1, and a possibly empty subset E Í V ´ V.
WOW! That is a lot of help.
Definition 2: A
graph G is a finite non-empty set of objects called vertices (the word “vertices” is the plural of “vertex) together
with a (possibly empty) finite set of pairs of distinct vertices of G called edges.
The
vertex set is commonly denoted by V(G) = {1, 2, 3, …, N}, where N is the number
of vertices in the set. It is convenient
to use integers to label vertices.
The
edge set, commonly denoted by E(G), is a subset of (V(G) ´ V(G)), the set of all pairs of elements from the
vertex set V(G).
The
cardinality of the vertex set of a graph G is called the order of G.
The cardinality of the edge set is called the size of G. Commonly |E(G)| = M.
An (N, M)-graph G is a graph with N vertices and M edges.
Directed and
Undirected Graphs
Consider
an (N, M)–graph G with vertex set V = {1, 2, …, N}, N ³ 1.
The
edge set E is defined as E(G) = { (J, K) | J Î V(G) and K Î V(G) }
We
immediately invoke the definition of a set that duplicate elements are not
found in a graph. Thus we have no duplicate edges; that is two edges
(J1, K1) and (J2, K2) with both J1 = J2 and K1 =
A
loop is an edge of the form (J, J),
with J Î V(G); that is the “end
points” are equal. A simple graph is a graph without loops.
A
simple graph is thus defined as the pair (V(G), E(G)), with
V(G) = {1, 2, …, N}, N ³ 1 (again, we
use integers as vertex labels).
E(G) = { (J, K) | J, K Î V(G) and J ¹ K }
The
basic question is whether the pairs (J, K) are ordered or unordered.
A
directed graph, often called a “digraph”, is a simple graph in which
the edge set is considered as a set of ordered
pairs (J, K) with J ¹ K.
An undirected graph is a simple graph in which the edge set is
considered as a set of unordered pairs
(J, K) with J ¹ K.
Example:
V(G) = {1, 2, 3, 4}
V(G) ´ V(G) = { (1, 1), (1, 2), (1, 3), (1, 4),
(2,
1), (2, 2), (2, 3), (2, 4),
(3,
1), (3, 2), (3, 3), (3, 4),
(4,
1), (4, 2), (4, 3), (4, 4) }. This set has 16 elements.
A
directed graph with vertex set V(G) would
have its edge set as a subset of the following subset of V(G) ´ V(G).
{ (1, 2), (1, 3), (1, 4),
(2,
1), (2, 3), (2, 4),
(3,
1), (3, 2), (3, 4),
(4,
1), (4, 2), (4, 3) }. |E(G)| £ 12.
An
undirected graph with vertex set V(G)
would have its edge set as a subset of the following subset of V(G) ´ V(G).
{ (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3,
4) }. |E(G)| £ 6.
Representations
of Graphs
So
far, we have followed the strict mathematical definition of a graph.
The
problem is that most people (your instructor included) prefer a visual
depiction of these mathematical objects.
With
the understanding that these depictions can occasionally be misleading, as we
shall show later, we now begin with the simpler depictions.
An
(N, M)–graph G is depicted with N circles denoting the N vertices and
M lines connecting the circles and representing the edges.
Labeled Graphs: While we often
use subsets of the set of integers to denote the vertices in a graph, we note
that this is just a convenience. A
four–vertex graph might have the vertex set {
As
examples, let’s look at representation of some graphs on four vertices.
V(G) = {1, 2, 3, 4}.
The Empty
Graph
Consider
the four vertex set V(G) = {1, 2, 3, 4}
One
possible graph on this vertex set has no edges.
Here is its representation.
Note
that E(G) = F.
This is a disconnected
graph. We define the term later, but for
now we shall just mention that most people see a single disconnected graph as a
number of smaller graphs. One might see
this as four single–vertex graphs; that view is valid.
As
a four–vertex empty graph, this is a (4, 0)–graph.
It is only of theoretical interest.
Some
Undirected Graphs
Let’s
examine three undirected graphs with four vertices and three edges.
Two of the graphs are connected; the one at the right is disconnected.
E(G) = { (1,2), (1, 3) E(G)
= { (1, 2), (1, 4), E(G) = { (1, 2), (1,
4)
(1, 4) } (2, 3) } (2,
4) }
Here are a number of undirected
graphs on three vertices.
Some Directed
(4, 3)–Graphs
Here
are two (4, 3) directed graphs. Note
that they are different graphs.
E(G1) = {
(1, 2), (1, 4), (4, 3) } E(G2)
= { (1, 4), (2, 1), (4, 3) }
Note
specifically that (1, 2) Î E(G1) but (1, 2) Ï E(G2).
also (2, 1) Ï E(G1) but (2, 1) Î E(G2)
In
the directed graph, the edges are ordered pairs taken from
the set V(G) ´ V(G). For this reason (1, 2) ¹ (2, 1).
More on
Directed and Undirected Graphs
Directed graphs
correspond to edge sets that contain ordered pairs.
Undirected graphs correspond to edge
sets that contain unordered pairs.
Consider
the figure below, which shows an undirected graph and a directed graph.
The two
graphs appear similar, but are quite different.
The graph at the left is said to be the undirected
graph that underlies the directed graph.
The undirected graph has E(G) = { (1, 4), (2, 3), (2, 4), (3,4) };
implicitly (3, 2) Î E(G), (4, 1) Î E(G), (4, 2) Î E(G), and (4, 3) Î E(G).
The directed graph has E(G)
= { (1, 4), (2, 4), (3, 2), (4, 1), (4, 3) },
with no edges implicitly added.
Still More
on Directed and Undirected Graphs
Consider the following two graphs, one directed and
one undirected.
In what sense are they similar?
Each graph has V(G) = {1, 2, 3, 4}
The undirected graph has E(G) = { (1, 2), (1, 4), (2, 3), (3, 4) }
more conventionally written as E(G)
= { (1, 2), (2, 3), (3, 4), (4, 1) }.
The directed graph has E(G)
= { (1, 2), (2, 3), (3, 4), (4, 1),
(1,
4), (4, 3), (3, 2), (2, 1) }
The undirected graph can be seen as a simpler
representation containing the same information as the directed graph. Nevertheless, they are not the same graph.
Equivalence
of Undirected and Directed Graphs
For
every directed graph, there is an undirected graph that has a similar
structure. These graphs are not equivalent.
In
some cases, the structure of the underlying undirected graph may yield insights
into the structure of the directed graph.
The
main use of this concept arises when we discuss the idea of connectivity in
directed graphs.
While the idea of a connected
graph is intuitive, we shall wait a while before giving a formal definition.
Summary:
Directed and Undirected Graphs
Both
are defined over a non–empty set of vertices, conventionally denoted by
V(G) = {1, 2, …, N }, for N ³ 1.
When
useful, graph vertices may be given other labels as convenient.
Neither
directed nor undirected graphs have loops;
that is, edges that begin or end on the same vertex.
For directed (N, M)–graphs:
1. The edge set is a subset of ordered pairs
from V(G) ´ V(G).
2. The
maximum edge count is N·(N – 1).
For undirected (N, M)–graphs:
1. The edge set is a subset of unordered pairs
from V(G) ´ V(G).
2. The
maximum edge count is 
= N·(N – 1) / 2.
For
the next few lectures, we shall focus on simple
undirected graphs.
Complement
of a Graph
Let
G be an (N, M)–graph with vertex set V(G) = {1, 2, …, N}
and edge set E(G).
The
complement of graph G, denoted GC,
is defined to be the graph with vertex set V(GC) = V(G) and edge set
E(GC) defined by
e Î E(GC) if and only if e Ï E(G)
Example:
Define G by V(G) = {1, 2, 3, 4} and E(G)
= {(1, 2), (1, 3), (1, 4)}
Then
GC is defined by V(GC) = {1, 2, 3, 4} and E(GC)
= {(2, 3), (2, 4), (3, 4)}
In pictures, we have:
Undirected
Graphs: Basic Structure
We
begin this section of the lecture by considering two questions related to the
basic structure of undirected graphs.
Similar considerations can be applied to directed graphs; it is just
that the presentation is simpler in the undirected case.
Look
at the following two graphs. How do they
differ? How are they similar?
Each
of the two graphs contains a triangle and an isolated vertex.
Obviously,
the two graphs are not the same graph, in that the one on the left has vertex 3
isolated while the one on the right has vertex 1 isolated.
We
shall develop a concept that describes the basic structural level at which
these two graphs are essentially the same graph.
Another
Example of Structure in Undirected Graphs
Consider
the next two graphs. They look very
different.
But
note that the two diagrams represent exactly
the same graph.
In
each graph, we have two facts:
Each vertex with an odd number is connected to every even–numbered vertex
Each
vertex with an even number is connected to every odd–numbered vertex.
We
need a way to focus on the structure of a graph, independent of the way it is
depicted or otherwise represented. One
answer is graph isomorphism.
Graph
Isomorphism
Two
graphs G1 and G2 are said to be isomorphic,
denoted by G1 @ G2,
if there exists a one-to-one mapping F
from V(G1) onto V(G2)
such that (u, v) Î E(G1) if and only if (F(u), F(v)) Î E(G2).
Consider
the following two graphs, with different vertex labels.
These two graphs are
isomorphic under the following transformation: F(1) = A, F(2) = B, F(3) = C,
and F(4) = D. The edge lists of the two
graphs show this.
Graph on left: (1, 2), (1, 4), (2, 3), and (3, 4)
Graph on right: (A,
B), (A, D), (B, C), and (C, D).
In
a sense, two isomorphic graphs represent the same graph.
More on
Isomorphism
The
idea of graph isomorphism allows us to focus on the basic structure.
If
two graphs are non–isomorphic, they
have basically different structures.
Here
are three non–isomorphic graphs on three vertices.
For
any value of N, there are only a finite number of non–isomorphic
graphs on N vertices. We can view these
as a finite set.
Define
G(N) as the set of non–isomorphic graphs on N vertices.
Define
G(N, M) as the set of non–isomorphic graphs on N vertices and
M edges.
For smaller values of N (N £ 4) we may easily display the entire sets G(N).
The Smaller
Graphs: G(1), G(2), and G(3)
Here
are the sets.
G(3, 0) G(3, 1) G(3, 2) G(3, 3)
The Set G(4)
Standard
Undirected Graphs: PN
Certain
graph structures appear with sufficient regularity to be given names.
The Path
The
path on N vertices is a connected graph with (N – 1) edges in the form of a
path. It has (N – 2) vertices of degree
2 and two vertices of degree 1.
The
path on N vertices is denoted by PN.
Here
are depictions of the graphs P2, P3, and P4.
Standard Undirected
Graphs: CN
The Cycle
The
cycle on N vertices is a connected graph with N edges and N vertices.
Each vertex has degree 2. The cycle on N
vertices is denoted CN.
Note
that we cannot define a cycle on two vertices.
Here
are C3 and C4.
Comment: It is the
structure, not the labels, that make the graph.
The labels are for
convenience only and could be removed.
Standard
Undirected Graphs: KN
The Complete Graph
The
complete graph on N vertices, denoted by KN, is a graph in which
every pair of vertices is adjacent. It
has N vertices, each with degree (N – 1).
It
has = N·(N – 1) / 2 edges.
Here
are four complete graphs: K1,
Don’t
two of these graphs have other names?
More later.
Standard
Undirected Graphs: Bipartite Graphs
A
set X Í V(G) of vertices is said
to be an independent set (stable set) if no two vertices in the
set are adjacent.
A
set of vertices X Í V(G) is said to be a maximal
independent set if it is an independent set and not a subset of a larger
independent set.
The
set {1, 2} is independent, but not maximal.
The set {1, 2, 3} is a maximal
independent set, although it is not the largest independent set.
The set {4, 5, 6, 7} is also
a maximal independent set.
Bipartite
and Complete Bipartite Graphs
A
graph G = (V(G), E(G)) is called bipartite
if the vertex set V(G) can be divided into two independent sets, called the partite sets of G. Let the two independent vertex sets be called
X and Y. Then V(G) = X È Y and X Ç Y = F.
A
graph is called complete bipartite
if each vertex in either partite set is adjacent to every vertex in the other
partite set.
By
Ka,b we mean the complete bipartite graph
with partite sizes a and b.
Here is the complete
bipartite graph K3,4.
The Star
Graph
The
complete bipartite graph K1,N–1 is often called either a “star graph” or a “claw”. This configuration
is seen in network theory, where it is called a “star topology” with the
central vertex (node) being called a “hub”.
Here
are two depictions of the complete bipartite graph K1,4.
The representation on the
left is more typical of the graph theory usage.
The representation on the right is more often seen in discussions of networks.
Some
Isomorphic Graphs
Here
are two isomorphic graphs on two vertices.
Here are some isomorphic graphs
on three vertices. These are triangles.
Here are some isomorphic graphs
on four vertices.
The Vertices
and Edges
Let
G = (V, E) be a graph with vertex set V(G) and edge set E(G).
Note: If (u,
v) Î E(G), then necessarily u Î V(G) and v Î V(G).
Undirected Graphs
If u Î V(G), v Î V(G), and (u,
v) Î E(G), then
1. Vertices u
and v are said to be adjacent to each other.
2. Edge (u,
v) is said to be incident on each of
vertices u and v.
3. The degree of vertex v, denoted d(v), is the
number of edges incident on v.
Equivalently, it is the number of
vertices adjacent to the vertex v.
The Vertices
and Edges (Part 2)
Let
G = (V, E) be a graph with vertex set V(G) and edge set E(G).
Note: If (u,
v) Î E(G), then necessarily u Î V(G) and v Î V(G).
Directed Graphs
If u Î V(G), v Î V(G), and (u,
v) Î E(G), then
1. Vertex u
is adjacent to vertex v and vertex v is adjacent from
vertex u.
2. Edge (u,
v) is said to be incident on each of
vertices u and v.
3. The in–degree
of a vertex v, d–(v), is the number of vertices adjacent
to v.
It is the number of vertices x such that (x, v) Î E(G).
The out–degree of a vertex v, d+(v), is the number of vertices adjacent
from v. It is the number of
vertices y such that (v, y)
Î E(G).
Neighborhoods
in Undirected Graphs
Let
G = (V, E) be an undirected graph with vertex set V(G) and edge set E(G).
For v Î V(G) we define N(v),
called the open neighborhood of the
vertex v, as the set of vertices
adjacent to v.
The size of this open neighborhood is the out–degree
of the vertex; |N(v)| = d(v).
Again, for undirected graphs, this is just the degree of the vertex v.
A vertex v
is called isolated if d(v) = 0, equivalently N(v) = F.
For v Î V(G) we define N[v],
called the closed neighborhood of
the vertex v, as N[v] = N(v) È {v}; the open neighborhood
with the vertex itself added.
Note the equation N[v] = N(v) È {v}.
This
depicts the standard way of showing an element added to a set. As set union is defined only for a number of
sets, we take the element v and first create the singleton set {v}.
This keeps the notation simple and consistent.
Neighborhoods
in Directed Graphs
Let
G = (V, E) be a directed graph with vertex set V(G) and edge set E(G).
For v Î V(G) we define N+(v), called the out–neighborhood
of the vertex v, as the set of
vertices adjacent from v; the set of
vertices y with (v, y) Î E(G).
Note that the size of the out–neighborhood is |N+(v)| = d+(v).
A vertex v
with d+(v) = 0 is
sometimes called a sink vertex.
For v Î V(G) we define N–(v), called the in–neighborhood
of the vertex v, as the set of
vertices adjacent to v; the set of
vertices x with (x, v) Î E(G).
Note that the size of the in–neighborhood is |N–(v)| = d–(v).
A vertex v
with d–(v) = 0 is
sometimes called a source vertex.
For a vertex v
Î V(G), we define the
following sets
the successor set of v is the out–neighborhood of v.
the predecessor
set of v is the in–neighborhood
of v.
The
Adjacency Matrix
Let
G = (V, E) be a graph with vertex set V(G) = {1, 2, …, N}
and edge set E(G) Ì V(G) ´ V(G).
We have used a pictorial representation of graphs to
facilitate discussing them. We need a
more formal method of representation if we want to develop algorithms that
operate on graphs.
We have two data structures that can be adapted to
depiction of graphs.
These are the matrix and the linked list.
The adjacent matrix of a graph G with vertex set V(G)
= {1, 2, …, N} is defined as the square N by N matrix A, where
A[J, K] = 1 if edge (J, K) Î E(G)
= 0 otherwise.
In the case of an undirected graph, we note that (J,
K) Î E(G) if and only if
(K, J) Î E(G). For this reason, the adjacency matrix of an
undirected graph
is symmetric; A[J, K] = A[K, J].
Example on
Four Vertices
Consider G with V(G) = {1, 2, 3, 4} and E(G) = { (1,
2), (1, 3), (1, 4), (2, 4) }
The 4–by–4 adjacency matrix of G is as follows.
|
0 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
|
1 |
0 |
0 |
0 |
|
1 |
1 |
0 |
0 |
NOTE: An undirected graph will always
have a symmetric adjacency matrix.
A
directed graph might have a symmetric adjacency matrix;
it is just not required to.
If the adjacency matrix is not
symmetric, the graph must be directed.
Another
Example: A Directed Graph on Four Vertices
Here is a directed graph on four vertices.
V(G) = {1, 2, 3, 4} E(G)
= { (1, 4), (2, 4), (3, 2), (4, 3) }
The
4–by–4 adjacency matrix of G is as follows.
|
0 |
0 |
0 |
1 |
|
0 |
0 |
0 |
1 |
|
0 |
1 |
0 |
0 |
|
0 |
0 |
1 |
0 |
Adjacency
Lists
Let G be a graph with V(G) = {1, 2, …, N} and edge set
E(G).
The adjacency
list representation of the graph has a set of N linked lists.
Each list has
a header node identifying the vertex.
Each list
contains the set of vertices adjacent from
that vertex.
(For undirected graphs, this is the
same as those adjacent to that vertex).
Walks,
Paths, and Connectivity
Let
G = (V, E) be a graph with vertex set V(G) and edge set E(G).
Let u Î V(G), v Î V(G).
A
sequence of edges (v1, v2), (v2, v3),
…, (vK,
vK+1) with u = v1,
v = vK+1, and
(vJ,
vJ+1) Î E(G) for 1 £ J £ K is called a walk from u to v.
The
walk can be described by listing its vertices (u = v1, v2, …, vK, vK+1 = v).
If
G is an undirected graph, the sequence is also a walk from v to u.
The
number of edges in the sequence is the length
of the walk.
A
walk with no edge repeated is called a path.
A
simple path (u = v1, v2, …, vK, vK+1 = v) is a path with no repeated vertices.
A
cycle is similar to a simple path,
except that the first vertex is also the last.
Example
of a cycle: (u = v1, v2,
v3, v4, v5
= u)
NOTE: This terminology has yet to “settle down”;
various authors will give
similar, but not identical,
definitions.
Connected
Graphs and Components
A
graph G is said to be connected if
for every distinct pair of vertices
u Î V(G) and v Î V(G) there is a path from u to v. It is called a (u, v)–path.
A
connected component, or simply a component, of a graph G is a maximal
connected subgraph of G.
A
graph is connected if and only if it has one component.
A
disconnected graph has two or more components.
Here
is a graph with three components.
It is tempting to view this as three connected graphs
G1 with V(G1) = {1, 2, 3, 4}, G2 with V(G2) = {5, 6, 8}, and G3 with V(G3) =
{7}.
Example:
Paths in a Graph
Here
is a graph on nine vertices, with two (1, 9)–paths shown.
Vertex disjoint paths are two paths with common end points but no
other vertices in common.
We
have two vertex disjoint (1, 6)–paths, followed by two vertex disjoint
(6, 9)–paths. But every (1, 9)–path must
go through vertex 6.
As
a result of this fact, removal of vertex 6 will cut the graph in two.
Cycles and
A u-v
walk of G is a finite, alternating sequence of vertices and edges starting
with u and ending with v.. It can be denoted as sequence of edges (v1,
v2), (v2, v3),
…, (vK,
vK+1) with u = v1,
v = vK+1, and (vJ, vJ+1)
Î E(G) for 1 £ J £ K
A
walk with no edge repeated is called a path.
A
simple path (u = v1, v2, …, vK, vK+1 = v) is a path with no repeated vertices.
A closed walk
is a walk in which the first vertex is the last vertex; u = v.
A
cycle is similar to a simple path,
except that the first vertex is also the last.
A Euler Tour (Euler
Circuit) of a graph is a path is a closed walk through the graph
that covers each edge exactly one time.
Vertices may be covered multiple times.
A Hamiltonian
Cycle of a graph is a cycle that contains each vertex exactly one
time.
It is likely that not all edges will be covered; no edge can be covered more
than once.
A graph is said to be Hamiltonian if it contains at least one Hamiltonian Cycle.
Examples of
Walks, Paths, and Cycles
Consider the following sample undirected graph.
Here V(G) = {1,
2, 3, 4, 5}
E(G) =
{ (1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 5), (4, 5) }
A (1, 4)–walk (1,
2), (2, 3), (3, 5), (5, 2), (2, 4)
often written as (1, 2, 3, 4, 2, 4)
– just the vertices. Note the repeated
vertex.
One (1, 4)–path (1,
2), (2, 4) – the shortest (1,
4)–path.
Another (1, 4)–path (1,
3), (3, 5), (5, 2), and (2, 4).
One cycle (1,
2), (2, 4), (4, 5), (5, 3), (3, 1)
Another cycle (1,
2), (2, 3), (3, 1) – this is called a
triangle.
Examples:
Euler and Hamiltonian Circuit
Euler circuits and Hamiltonian circuits appear
similar, but they are quite distinct.
Consider two sets of graphs. We begin
with a graph having an Euler circuit.
Here is the Euler Circuit. It has no Hamiltonian circuit.
We have displayed the Euler circuit. Theoretically, it is easy to determine
whether or not
a graph has a Euler circuit, and thus is to be called “Eulerian”.
There is no easy way to determine the existence of a
Hamiltonian circuit in a graph; it can be done only by a complete enumeration
of all candidates; there are 24 in this graph.
Examples:
Euler and Hamiltonian Circuit (Part 2)
We now consider a Hamiltonian graph having no Euler
circuit.
Again, there is no easy way to determine if a general
graph contains a Hamiltonian cycle. Here
I have just displayed one.
The claim that the graph lacks a Euler circuit can be
established by a theorem proved in
1736 by the Swiss mathematician Leonhard Euler (1707 – 1783).
Theorem: Let G = (V, E)
be an undirected graph with no isolated vertices. Then
G has an Euler circuit
if and only if G is connected,
and every vertex of G
has even degree.
This example graph has two vertices of odd degree;
hence no Euler circuit.
Distances in
Graphs
Let U and V be two vertices in a graph G.
If there is a U–V path in G, then the distance from U to V
is the number of edges in the
shortest U–V path.
If the vertices U
and V are adjacent, then the from U to V
is 1.
If there is no U–V path in G, the distance from U to V
is not defined.
The distance from 1 to 2 is dist(1, 2) = 1
The distance from 1 to 4 is dist(1, 4) = 2.
Connectivity
in Directed Graphs
A
directed graph is said to be weakly
connected if its underlying undirected graph is connected. It is said to be strongly connected if there is a (u, v)–path for each
ordered pair (u, v) of vertices.
This
directed (4, 3)–graph is weakly connected, but not strongly connected. There is no path from vertex 3 to any other
vertex. However, its underlying
undirected graph (shown to the right) is connected.
Connectivity
in Directed Graphs
The
next example shows a directed (4, 4)–graph that is strongly connected.
Terminology: This graph
meets the technical definition for being
weakly
connected; its underlying graph is also connected.
However, the
term “weakly connected” is always used to
imply “not
strongly connected”.
Subgraphs
Let
G = (V(G), E(G)) be a graph. A subgraph H of the graph G is a graph
H = (V(H), E(H)) with V(H) Í V(G) and E(H) Í E(G).
Obviously,
any graph G is a subgraph of itself.
Here
is a rather straightforward example of a subgraph. The subgraph on the left is a subgraph of the
one on the right.
As
we shall see later, the graph on the left is a spanning tree of the one at right.
The graph at right is often
called a “wheel graph”, with a
central vertex attached to a number of peripheral vertices, otherwise arrayed
as a cycle.
More on
Subgraphs
When
we say either “H is a subgraph of G” or “G contains H as a subgraph”, we often
mean that the graph G contains a graph isomorphic to H.
Consider
the following (4, 4)–graph.
We
say that it contains a triangle (C3 or K3), a star graph
(K1,3), several paths on three vertices (P3), and a
number of other subgraphs.
C3: (1, 2), (2, 4), (4, 1) K1,3: (1,
2), (1, 3), (1, 4)
P3: (2, 1), (1, 3) P3: (2, 1),
(1, 4) P3: (3, 1), (1, 4)
Acyclic
Graphs
A
graph may contain one or more cycles (CN) as subgraphs.
Here
we see K4, the complete graph on four vertices.
This
graph contains a 4–cycle and four 3–cycles as subgraphs.
A
graph that does not contain a cycle as a subgraph is called “acyclic”.
Tree
Definition: A tree is a connected acyclic graph.
Note:
This differs from the book’s definition on page 9, which is incorrect.
This
definition is simple and very powerful.
It is also a bit puzzling.
Here
is a set of statements that can be proven to be logically equivalent.
1. G
is a tree with n vertices and m edges.
2. Every
two distinct vertices of G are connected by a unique path.
3. G
is connected and m = n – 1.
4. G
is acyclic and m = n – 1.
Theoretically,
a single node (K1) satisfies the above definitions. In order to avoid this nuisance fact in our
theorems, we make a further definition.
Definition: A nontrivial
tree is a tree with at least two vertices.
Unless
specifically stated, when we say “tree” we mean “nontrivial tree”.
Examples of
Trees
All
PN (paths on N vertices) are trees, although P2 is not
much of a tree.
All
star graphs (K1,N–1) are trees.
We
shall give some examples that are more interesting.
But first, a few more definitions.
Spanning
Subgraphs and Spanning Trees
Let
G = (V(G), E(G)) be a graph with vertex set V(G) and edge set E(G).
A
spanning subgraph is a subgraph H
with V(H) = V(G) and E(H) Í E(G).
The spanning subgraph is not required to be a connected graph.
The
only spanning subgraph of much practical use is the spanning tree.
Definition: A spanning tree is a spanning subgraph
that is a tree.
Let
T be a spanning tree of an (N, M)–graph G = (V(G), E(G)).
What can we conclude?
1. T is a connected graph with N vertices and (N
– 1) edges.
2. T is a spanning subgraph of G, so V(T) = V(G)
and E(T) Í E(G).
3. G is a connected graph with at least (N – 1)
edges.
Remark: A connected
(N, M)–graph with M = (N – 1) is a tree; thus
it is its own
spanning tree.
A connected (N, M)–graph
with M ³ N has many spanning
trees.
Example:
Spanning Trees for K4
The
complete graph on four vertices has six edges.
A spanning tree on four vertices will have three edges. We have 
= 20 different ways to
remove three edges from a set of six.
Not all of these will yield a connected subgraph.
Here
is K4 and two non–isomorphic spanning trees.
Rooted Trees
Definition: A rooted tree is a tree in which one
vertex has been chosen
and designated as the
root of the tree.
Question: Is a rooted
tree a directed graph?
Answer: Nothing in
the definition requires it to be a directed graph,
though all common
usage treats it as a directed graph.
Here
is the books definition from page 9, as corrected.
A [rooted] tree is a directed graph that has no cycles, and that has
one distinct vertex, called the root, such that there is exactly one path from
the root to every other vertex.
A
vertex in a in tree is more commonly
called a “node”.
The
distance of a vertex in this rooted tree from the root vertex is the number of
edges in the unique path from the root to that vertex.
Vertices
in rooted trees are often ranked by level.
The level of a vertex is the distance of the vertex from the root. The root is at level 0, by definition.
Rooted Trees
(Part 2)
Let
v be a vertex in a rooted directed
tree. We can prove a few facts about the
vertex that lead to some common definitions.
Incoming Edges
Either
the vertex v is the root of the tree
or there is exactly one vertex w
adjacent to v; that is (w, v) is an edge in the tree. This one node is the parent node of v.
If
x is a node on the unique path from
the root node to a vertex v, then x is said to be an ancestor node of v. The root node is an ancestor of all other
nodes.
Outgoing Edges
The
vertex v has zero or more vertices
that are adjacent from it.
In
directed graph terminology, this is N(v),
the open neighborhood of v.
In
tree terminology, this is the set of child nodes of v.
A
node v with no child nodes is called
a leaf node.
If
node v is the ancestor node of a
vertex y, then vertex y is said to be a descendant node of vertex v. All child nodes are descendant nodes.
Binary Trees
Definition: A binary tree is a rooted tree in which
each node has at most
two child nodes.
Each
child node is called a “left child”
or “right child” depending on how it
is drawn in a typical depiction. By
convention of the drawing style, a node has a right child only if it has a left
child. There is no theory behind this convention.
Each
child node is the root of a subtree.
The
left subtree is the subtree rooted
at the left child node.
The
right subtree is the subtree rooted
at the right child node.
Note
that a single node, by definition, is a binary tree. It is the root of that tree.
Search Trees
The process of searching a graph is usually based on
the generation of a spanning
tree of the graph rooted at a specific start node.
There may be a number of ways to select the start
node. The search results will vary.
The figure at left shows a search tree that started at
vertex 1 and moved to vertex 3.
The figure at right shows a search tree that started
at vertex 2.
The figure at right might have been generated by
Breadth First Search (more on this later)
but the figure at left was generated to be a pretty picture.
Weighted
Graphs
A weighted graph is a simple graph (directed or
undirected) in which
each edge has a weight, cost, or
capacity associated with it.
More formally: A weighted graph G is a triple (V, E,
W) in which
V is a non–empty set of vertices,
E Í V ´ V is a set of edges (the
graph can be directed or undirected), and
W is a function from the edge set E into R, the set of
real numbers.
For any edge e
Î E, w(e) is the weight of e.
For any two vertices u Î V(G) and v Î V(G), the distance between these two
vertices is normally the smallest sum of weights of edges in any path from u to v.
Much of graph theory, and almost all of our examples,
uses edge weights
from the set of non–negative
integers.
An
unweighted graph can easily be represented as a weighted graph
in which every edge has weight
of 1; w(e) = 1.
Associated with each weighted graph G = (V, E, W) is
an underlying unweighted
graph that has the same structure, but which has no edge weights assigned.
Weighted
Subtrees
Given a weighted graph G = (V, E, W), we often
generate a number of specific
spanning trees.
There are two trees of interest:
1. A minimal
spanning tree (MST), which is the spanning tree of G with
smallest total edge weight. A MST need not be unique.
2. A shortest distance tree (nonstandard name)
generated as a part of
computing the shortest distance
Here is a graph and two spanning subtrees
The tree at left is a MST. The one at right shows minimum distances from
vertex 2.
The
Adjacency Matrix of a Weighted Graph
Let
G = (V, E, W) be a weighted graph with vertex set V(G) = {1, 2, …, N},
edge set E(G) Ì V(G) ´ V(G), and W as the set of weights.
We have two data structures that can be adapted to
depiction of graphs.
These are the matrix and the linked list.
The adjacent matrix of a weighted graph G with vertex
set V(G) = {1, 2, …, N} is defined as the square N by N matrix A, where
A[J, K] = W(J, K) the weight of the
edge if edge (J, K) Î E(G)
If edge (J, K) is not in the graph, the assignment of
a weight will depend
on the algorithm used to examine the graph.
Often we use “¥” for no edge.
Here
is the adjacency matrix for the above graph, which was used to
illustrate spanning trees.
|
0 |
5 |
¥ |
1 |
|
5 |
0 |
4 |
7 |
|
¥ |
4 |
0 |
2 |
|
1 |
7 |
2 |
0 |
The
Adjacency List Representation of a Weighted Graph
In the adjacency list representation, the node in the
linked list includes not only the vertex to which the edge is incident, but also
the weight of that edge.
Here is the graph and its adjacency list
representation.
Minimum Cost
Hamiltonian Circuits
A weighted graph G = (V, E, W) is said to be
Hamiltonian if its underlying
unweighted graph is also Hamiltonian.
Some Hamiltonian graphs contain more than one
Hamiltonian cycle. It is easy
to show that the complete graph on N vertices, KN, has (N – 1) such
cycles.
In some very interesting problems, we study a weighted
graph that is known to
have Hamiltonian cycles and ask to find one cycle of minimum total cost.
This is the well–known TSP (Traveling Salesman
Problem). Here is an actual
instance of the TSP, based on direct–flight airfares.
