Discrete Mathematics – Graphs and Trees.pdf

Discrete Mathematics – Graphs and Trees.pdf

1. Discrete Mathematics 5. Graphs & Trees

2. What are Graphs?
•General meaning in everyday math:
A plot or chart of numerical data using a coordinate
system.
Not
Discrete Mathematics, Spring 2009
•Technical meaning in discrete mathematics:
A particular class of discrete structures (to be
defined) that is useful for representing relations and
has a convenient webby-looking graphical
representation.

3. Simple Graphs
•The graph in which each edge connects two
different vertices and where no two edges
connect the same pair of vertices
Visual Representation
of a Simple Graph
Discrete Mathematics, Spring 2009
connect the same pair of vertices
•Correspond to symmetric binary relations R.

4. Simple Graphs
•Definition:
A simple graphG=(V,E)
consists of:
−
a set
V
of
vertices
or
nodes
(
V
corresponds to the
Visual Representation
of a Simple Graph
Discrete Mathematics, Spring 2009
−
a set
V
of
vertices
or
nodes
(
V
corresponds to the
universe of the relation R), and
−
a set Eof edges/ arcs/ links: unordered pairs of [distinct?]
elements u,v∈V, such that uRv.

5. •Let Vbe the set of states in the far-southeastern U.S.:
V={FL, GA, AL, MS, LA, SC, TN, NC}
•Let E={{u,v}|u adjoins v}
={{FL,GA},{FL,AL},{FL,MS}, Example of a Simple Graph
Discrete Mathematics, Spring 2009
={{FL,GA},{FL,AL},{FL,MS},
{FL,LA},{GA,AL},{AL,MS},
{MS,LA},{GA,SC},{GA,TN},
{SC,NC},{NC,TN},{MS,TN},
{MS,AL}}
TN
AL MS
LA
SC
GA
FL
NC

6. Multigraphs
•Like simple graphs, but there may be more than one
edge connecting two given nodes.
•
Definition
:
Discrete Mathematics, Spring 2009
•
Definition
:
A multigraphG=(V, E, f ) consists of a set Vof vertices, a
set Eof edges (as primitive objects), and a function
f:E→{{u,v}|u,v∈V
∧u≠v
}.
•Example:
nodes are cities and
edges are segments of major highways.
Parallel
edges

7. Pseudographs
•Like a multigraph, but edges connecting a
node to itself are allowed.
•
Definition
:
Discrete Mathematics, Spring 2009
•
Definition
:
A pseudographG=(V, E, f ) where
f:E→{{u,v}|u,v∈V}. Edge e∈Eis a loopif
f(e)={u,u}={u}.
•Example:
nodes are campsites
in a state park and edges are
hiking trails through the woods.
loop

8. Directed Graphs
•Correspond to arbitrary binary relations R,
which need not be symmetric.
•
Definition
:
Discrete Mathematics, Spring 2009
•
Definition
:
A directed graph(V, E) consists of a set of vertices
Vand a binary relation Eon V.
•Example:
V= people, E={(x,y) | xloves y}

9. Walk, loop, sling, and path
•Definition:
−A walkis a sequence x
0
, x
1
, …, x
n
of the vertices of
a digraph such that x
ix
i+1
, 0≤i≤n-1, is an edge.
−
The
length of a walk
is the number of edges in the
Discrete Mathematics, Spring 2009
−
The
length of a walk
is the number of edges in the
walk.
−If a walk holds x
i≠x
j
(i≠j) i,j=0, …, n, except x
0
, x
n
(i.e
x
0
=x
n
), the walk is called a cycle.
−A loopis a cycle of length one.
−A slingis a cycle of length two.
−A walk is a pathif no edge is repeated more than
once.

10. Directed Multigraphs
•Like directed graphs, but there may be more than one
arc from a node to another.
•Definition:
A
directed
multigraph
G
=(
V
,
E
,
f
) consists of a set
V
of
Discrete Mathematics, Spring 2009
A
directed
multigraph
G
=(
V
,
E
,
f
) consists of a set
V
of
vertices, a set Eof edges, and a function f:E→V×V.
•Example:
−
The WWW is a directed multigraph.
−
V=web pages, E=hyperlinks.

11. Types of Graphs: Summary
•Keep in mind this terminology is not fully standardized...
Discrete Mathematics, Spring 2009
Term
Edge
type
Multiple
edges ok?
Self-
loops ok?
Simple graph Undir. No No
Multigraph Undir. Yes No
Pseudograph Undir. Yes Yes
Directed graph Directed No Yes
Directed multigraph Directed Yes Yes

12. Graph Terminology
•Adjacent, connects, endpoints, degree, initial,
terminal, in-degree, out-degree, complete, cycles,
wheels, n-cubes, bipartite, subgraph, and union.
Discrete Mathematics, Spring 2009

13. Adjacency
Let Gbe an undirected graph with edge set E. Let
e∈Ebe (or map to) the pair {u,v}. Then we say:
•u, vare adjacent/ neighbors/ connected.
Discrete Mathematics, Spring 2009
•Edge eis incident withvertices uand v.
•Edge econnectsuand v.
•Vertices uand vare endpointsof edge e.

14. Degree of a Vertex
•Let Gbe an undirected graph, v∈Va vertex.
•The degreeof v, deg(v), is its number of incident
edges. (Except that any self-loops are counted
twice.)
Discrete Mathematics, Spring 2009
twice.)
•A vertex with degree 0 is isolated.
•A vertex of degree 1 is pendant.

15. Handshaking Theorem
•Theorem:
−
Let Gbe an undirected (simple, multi-, or
pseudo-) graph with vertex set Vand edge set E.
Then
Discrete Mathematics, Spring 2009
Then
•Corollary:
−
Any undirected graph has an even number of
vertices of odd degree.
E v
Vv
2) deg(=
∑
∈

16. Directed Adjacency
•Let Gbe a directed (possibly multi-) graph, and
let ebe an edge of Gthat is (or maps to) ( u,v).
Then we say:
−
u
is
adjacent to
v
,
v
is
adjacent from
u
Discrete Mathematics, Spring 2009
−
u
is
adjacent to
v
,
v
is
adjacent from
u
−
ecomes fromu, e goes tov.
−
e connects u to v, e goes from u to v
−
the initial vertexof eis u
−
the terminal vertexof eis v

17. Directed Degree
•Definition:
Let Gbe a directed graph, va vertex of G.
−
The in-degreeof v, deg
−
(v), is the number of
edges going to
v
.
Discrete Mathematics, Spring 2009
edges going to
v
.
−
The out-degreeof v, deg
+
(v), is the number of
edges coming from v.
−
The degreeof v, deg(v)≡deg
−
(v)+deg
+
(v), is the
sum of v’sin-degree and out-degree.

18. Directed Handshaking Theorem
•Theorem:
−
Let Gbe a directed (possibly multi-) graph with
vertex set Vand edge set E. Then:
∑
∑
∑
1
Discrete Mathematics, Spring 2009
•Note that the degree of a node is unchanged by
whether we consider its edges to be directed or
undirected.
E v v v
Vv Vv Vv
= = =
∑
∑
∑
∈ ∈
+
∈
−
) deg(
2
1
)( deg )( deg

19. Special Graph Structures
Special cases of undirected graph structures:
•Complete Graphs K
n
•
Cycles
C
n
Discrete Mathematics, Spring 2009
•
Cycles
C
n
•Wheels W
n
•n-Cubes Q
n
•Bipartite Graphs
•Complete Bipartite Graphs K
m,n

20. Complete Graphs
•Definition:
−
For any n∈N, a complete graphon nvertices, K
n,
is a simple graph with nnodes in which every
node is adjacent to every other node:
∀
u
,
v
∈
V
:
Discrete Mathematics, Spring 2009
node is adjacent to every other node:
∀
u
,
v
∈
V
:
u≠v↔{u,v}∈E.
K
1K
2K
3K
4K
5K
6
Note that K
nhas edges.
2
)1 (
1
1
−
=
∑
−
=
nn
i
n
i

21. Cycles
•Definition:
−
For any n≥3, a cycleon nvertices, C
n, is a simple
graph where V={v
1,v
2,…,v
n} and
E
={{
v
1
,
v
2
},{
v
2
,
v
3
},
…
,{
v
n
−
1
,
v
n
},{
v
n
,
v
1
}}.
Discrete Mathematics, Spring 2009
E
={{
v
1
,
v
2
},{
v
2
,
v
3
},
…
,{
v
n
−
1
,
v
n
},{
v
n
,
v
1
}}.
C
3C
4C
5C
6C
7
C
8
How many edges are there in C
n?

22. Wheels
•Definition:
−
For any n≥3, a wheelW
n, is a simple graph obtained by
taking the cycle C
nand adding one extra vertex v
hub
and
n
extra edges {{
v
hub
,
v
1
}, {
v
hub
,
v
2
},
…
,{
v
hub
,
v
n
}}.
Discrete Mathematics, Spring 2009
and
n
extra edges {{
v
hub
,
v
1
}, {
v
hub
,
v
2
},
…
,{
v
hub
,
v
n
}}.
W
3W
4W
5W
6W
7
W
8
How many edges are there in W
n?

23. n-Cubes (hypercubes)
•Definition:
−
A graph that has vertices representing the 2
n
bit
strings of length n
−
For any
n
∈
N
, the
hypercube
Q
n
is a simple
Discrete Mathematics, Spring 2009
−
For any
n
∈
N
, the
hypercube
Q
n
is a simple
graph consisting of two copies of Q
n-1connected
together at corresponding nodes. Q
0has 1 node.
Q
0Q
1Q
2Q
3
Q
4
Number of vertices: 2
n
. Number of edges:Exercise to try!

24. n-Cubes (hypercubes)
•Definition:
For any n∈N, the hypercube Q
ncan be defined
recursively as follows:
•
Q
=({
v
},
∅
)
(one node and no edges) Discrete Mathematics, Spring 2009
•
Q
0
=({
v
0
},
∅
)
(one node and no edges)
•For any n∈N, if Q
n
=(V,E), where V={v
1
,…,v
a
} and
E={e
1
,…,e
b
}, then Q
n+1
=(V∪{v
1
´,…,v
a
´},
E∪{e
1
´,…,e
b
´}∪{{v
1
,v
1
´},{v
2
,v
2
´},…,
{v
a
,v
a
´}}) where v
1
´,…,v
a
´are new vertices, and
where if e
i={v
j,v
k
} then e
i´={v
j´,v
k
´}.

25. Bipartite Graphs
•Definition:
−
A simple graph Gis called bipartiteif its vertex
set Vcan be partitioned into two disjoint sets V
1
and V
2such that every edge in the graph
connects a vertex in
V
1
and a vertex in
V
2
(so
Discrete Mathematics, Spring 2009
connects a vertex in
V
1
and a vertex in
V
2
(so
that no edge in Gconnects either two vertices in
V
1or two vertices in V
2)
V
1V
2
a bipartite

26. Complete Bipartite Graphs
•Definition:
Let m, nbe positive integers. The complete
bipartite graphK
m,nis the graph whose vertices
can be partitioned
V
=
V
∪
V
such that
Discrete Mathematics, Spring 2009
can be partitioned
V
=
V
1
∪
V
2
such that
1.|V
1
| = m
2.|V
2
| = n
3.For all x∈ V
1
and for all y∈V
2
, there is an
edge between xand y
4.No edge has both its endpoints in V
1
or both its
endpoints in V
2

27. Complete Bipartite Graphs (cont.)
V
1V
2
Discrete Mathematics, Spring 2009
K
2,3
K
3,4
V
1
V
2

28. Subgraphs
•Definition:
−
A subgraphof a graph G=(V,E) is a graph
H=(W,F) where W⊆Vand F⊆E.
Discrete Mathematics, Spring 2009
GH

29. Graph Unions
•Definition:
−
The unionG
1∪G
2of two simple graphs G
1=(V
1,
E
1) and G
2=(V
2,E
2) is the simple graph (V
1∪V
2,
E
∪
E
).
Discrete Mathematics, Spring 2009
E
1
∪
E
2
).

30. Graph Representations & Isomorphism
•Graph representations:
−
Adjacency lists.
−
Adjacency matrices.
Discrete Mathematics, Spring 2009
−
Incidence matrices.
•Graph isomorphism:
−
Two graphs are isomorphic iff they are identical
except for their node names.

31. Adjacency Lists
•A table with 1 row per vertex, listing its adjacent
vertices.
•A way to represent a graph w/ no multiple edges
Discrete Mathematics, Spring 2009
ab
d c
f
e
Vertex Adjacent Vertices
a
b
b, c
a, c, e, f
c a, b, f d e b f c, b

32. Directed Adjacency Lists
•1 row per node, listing the terminal nodes of
each edge incident from that node.
Discrete Mathematics, Spring 2009

33. Adjacency Matrices
•Matrix A=[a
ij], where a
ijis 1 if {v
i, v
j} is an edge
of G, 0 otherwise.
Discrete Mathematics, Spring 2009
•Simple graph representation

34. Adjacency Matrices
•Matrix M=[m
ij], where
−
m
ij= 1 when edge e
jis incident with v
i,
−
m
ij= 0 otherwise. •
A way of represent graphs
Discrete Mathematics, Spring 2009
•
A way of represent graphs
−
can be used to represent multiple edges and
loops

35. Graph Isomorphism
•Definition:
Simple graphs G
1=(V
1, E
1) and G
2=(V
2, E
2) are isomorphic
iff
∃
a
bijection
f
:
V
1
→
V
2
such that
∀
a
,
b
∈
V
1
,
a
and
b
are
Discrete Mathematics, Spring 2009
iff
∃
a
bijection
f
:
V
1
→
V
2
such that
∀
a
,
b
∈
V
1
,
a
and
b
are
adjacent in G
1ifff(a) and f(b) are adjacent in G
2.
•fis the “renaming”function that makes the two
graphs identical.
•Definition can easily be extended to other types of
graphs.

36. Graph Invariants under Isomorphism
•Graph Invariant
−
a property preserved by isomorphism of graphs
−
Necessarybut not sufficientconditions for G
1
=(V
1
,
E
) to be isomorphic to
G
=(
V
,
E
):
Discrete Mathematics, Spring 2009
1
1
E
1
) to be isomorphic to
G
2
=(
V
2
,
E
2
):
•|V
1
|=|V
2
|, |E
1
|=|E
2
|.
•The number of vertices with degree nis the same
in both graphs.
•For every proper subgraphgof one graph, there
is a proper subgraphof the other graph that is
isomorphic to g.

37. Isomorphism Example
•If isomorphic, label the 2nd graph to show the
isomorphism, else identify difference.
b
d
Discrete Mathematics, Spring 2009
a
b
c d
e
f
b
d
a
e
f c

38. Are These Isomorphic?
•If isomorphic, label the 2nd graph to show the
isomorphism, else identify difference.
a
*
Same # of vertices
Discrete Mathematics, Spring 2009
a
b
c
d
e
*
Same # of vertices
* Same # of edges
* Different # of verts of
degree 2! (1 vs 3)

39. Connectedness
•Definition:
A path of length n from uto vin G is
a
sequence of n edges
e
1
,
e
2
, …,
e
n
such that
e
1
is
associated with {
x
, x
},
e
is associated with {
x
, x
}, and
Discrete Mathematics, Spring 2009
a
sequence of n edges
e
1
,
e
2
, …,
e
n
such that
e
1
is
associated with {
x
0
, x
1
},
e
2
is associated with {
x
1
, x
2
}, and
so on, with e
nassociated with {x
n-1,x
n}, where x
0=uand
x
n=v;
•The path is circuitif it begins and ends at the same
vertex, that is u=v, and has length greater than zero.
•A path or circuit is simpleif it does not contain the
same edge more than once.

40. Connectedness
•Definition: −
An undirected graph is connectediffthere is a path
between every pair of distinct vertices in the graph
.
Discrete Mathematics, Spring 2009
between every pair of distinct vertices in the graph
.
•Theorem:
−
There is a simplepath between any pair of vertices in a
connected undirected graph.

41. Directed Connectedness
•Definition:
−
A directed graph is strongly connectediffthere is
a directed path from ato bfor any two vertices a
and
b
.
Discrete Mathematics, Spring 2009
and
b
.
−
It is weakly connectediffthe underlying undirected
graph (i.e., with edge directions removed) is
connected.
•Note stronglyimplies weaklybut not vice-versa.

42. Paths & Isomorphism
•Note that connectedness, and the existence of a
circuit or simple circuit of length kare graph
invariants with respect to isomorphism.
Discrete Mathematics, Spring 2009

43. Euler & Hamilton Paths
•Definition:
−
An E
uler circuitin a graph Gis a simple circuit
containing every e
dge of G.
−
An E
uler pathin Gis a simple path containing every
e
dge of
G
.
Discrete Mathematics, Spring 2009
e
dge of
G
.
•Examples:
a
b
e
c d
a, e, c, d, e, b, a
Euler circuit
a, c, d, e, b, d, a, b
Euler path
a b
c
d
e

44. Euler & Hamilton Paths (cont.)
•Definition:
−A Hamilt
on circuitis a simple circuit that traverses
each vert
ex in Gexactly once.
−A Hamilt
on pathis a simple path that traverses each
vert
ex in G exactly once.
Discrete Mathematics, Spring 2009
•Examples:
c e
a, b, c, d, e, a
Hamilton circuit
a, b, c, d
Hamilton path dc
ab
d
ab

45. Trees
•
Definition:
−A treeis a connected undirected graph with no simple
circuits.
•
Since a tree cannot have a circuit, a tree cannot c ontain
Discrete Mathematics, Spring 2009
•
Since a tree cannot have a circuit, a tree cannot c ontain multiple edges or loops.
•Therefore, any tree must be a simple graph.
•
Theorem:
−An undirected graph is a tree if and only if there is a
unique simple pathbetween any two of its vertices.
•In general, we use trees to represent hierarchical structures.

46. Trees
Example:Are the following graphs trees?
Discrete Mathematics, Spring 2009
No.No. Yes. Yes.
Yes. Yes.
No.No.

47. Root & Rooted tree
•We often designate a particular vertex of a tree
as the root. Since there is a unique path from
the root to each vertex of the graph, we direct
each edge away from the root
.
Discrete Mathematics, Spring 2009
each edge away from the root
.
•Definition:
A rooted tree is a tree in which one vertex has been
designated as the root and every edge is directed
away from the root

48. Tree Terminology
•Definition:
−
If vis a vertex in a rooted tree other than the root,
the parentof v is the unique vertex usuch that
there is a directed edge from
u
to
v
.
Discrete Mathematics, Spring 2009
there is a directed edge from
u
to
v
.
−
When uis the parent of v, vis called the childof u.
−
Vertices with the same parent are called siblings.
−
The ancestorsof a vertex other than the root are
the vertices in the path from the root to this verte x,
excluding the vertex itself and including the root.

49. Tree Terminology (cont.)
•Definition:
−
The descendantsof a vertex vare those vertices that
have vas an ancestor.
Discrete Mathematics, Spring 2009
−
A vertex of a tree is called a leafif it has no children.
−
Vertices that have children are called internal
vertices.
−
If ais a vertex in a tree, then the subtreewith aas its
root is the subgraphof the tree consisting of aand its
descendants and all edges incident to these
descendants.

50. Tree Terminology
•Definition:
−
The levelof a vertex v in a rooted tree is the
length of the unique path from the root to this
vertex.
Discrete Mathematics, Spring 2009
vertex.
−
The level of the root is defined to be zero.
−
The heightof a rooted tree is the maximum of
the levels of vertices.

51. Trees
Example 1:Family tree
James James
Discrete Mathematics, Spring 2009
BobBob
Christine Christine
Frank Frank
Joyce Joyce
Petra Petra

52. Trees (cont.)
Example 2:File system
//
Discrete Mathematics, Spring 2009
temp temp
usrusr
binbin spoolspool
lsls
binbin

53. Trees (cont.)
Example 3:Arithmetic expressions
⋅⋅
Discrete Mathematics, Spring 2009
++
--
yy zz
xx yy
•This tree represents the expression (y + z) ⋅(x -y).

54. m-arytree •
Definition:
−
A rooted tree is called an m-arytreeif every internal
vertex has no more than m children. −
The
tree is called a
full
m
-
ary
tree
if every internal
Discrete Mathematics, Spring 2009
−
The
tree is called a
full
m
-
ary
tree
if every internal
vertex has exactly m children.
−
An m-arytree with m= 2 is called a binary tree.
•
Theorem:
−
A tree with nvertices has (n–1) edges.
−A full m-arytree with iinternal vertices contains n=
m·i+ 1 vertices.

55. Ordered Rooted Tree •
Definition:
−
An ordered rooted treeis a rooted tree where
the children of each internal vertex are ordered.
Discrete Mathematics, Spring 2009
•
For example, in an ordered binary tree (just called
binary tree), if an internal vertex has two childre n,
−
the first child is called the left child and the
second is called the right child.
−
the tree rooted at the left child is called the lef t
subtree, and at the right child, the right subtree
•
Ordered rooted trees can be defined recursively.

56. Ordered Rooted Tree (binary tree)
aa
bb
cc
Left subtree of the Vertex b
Left child of the
Vertex a
Right child of
the Vertex a
Discrete Mathematics, Spring 2009
gg
dd
hh
kk
jj
ll
ee
ff
ii
the Vertex b
Right subtree of
the Vertex b

57. Tree Traversal
•Procedures for systematically visiting every
vertex of an ordered rooted tree are called
traversal algorithms.
Discrete Mathematics, Spring 2009

58. Preorder traversal
r
step 1
Visit r
•Definition:
Let Tbe an ordered rooted
tree with root r.
If Tconsists only of r, then ris
the
preorder traversal
of
T
.
Discrete Mathematics, Spring 2009
T
1
T
2
T
n
...
Step 2
Visit T
1in
preorder
step 3
Visit T
2in
preorder
Step n+1
Visit T
nin
preorder
the
preorder traversal
of
T
.
Otherwise, suppose that T
1
,
T
2
, …, T
n
are the subtreesat r
from left to right in T. The
preorder traversalbegins by
visiting r. It continues by
traversing T
1
in preorder,
then T
2
in preorder, and so on,
until T
n
is traversed in
preorder.

59. Inorder traversal
r
step 2
Visit r
•Definition:
Let Tbe an ordered rooted
tree with root r.
If Tconsists only of r, then ris
the
inorder
traversal
of
T
.
Otherwise, suppose that
T
,
Discrete Mathematics, Spring 2009
T
1
T
2
T
n
...
Step 1
Visit T
1in
inorder
step 3
Visit T
2in
inorder
Step n+1
Visit T
nin
inorder
the
inorder
traversal
of
T
.
Otherwise, suppose that
T
1
,
T
2
, …, T
n
are the subtreesat r
from left to right. The inorder
traversalbegins by traversing
visiting T 1
in inorder, then
visiting r. It continues by
traversing T
2
in inorder, then
T
3
in inorder, …, and finally
T
n
in inorder

60. Postorder traversal
•Definition:
Let Tbe an ordered rooted
tree with root r.
If Tconsists only of r, then ris
the
postorder
traversal
of
T
.
Otherwise, suppose that
T
,
T
,
r
step n+1
Visit r
Discrete Mathematics, Spring 2009
the
postorder
traversal
of
T
.
Otherwise, suppose that
T
1
,
T
2
,
…, T
n
are the subtreesat r
from left to right. The postorder
traversalbegins by traversing
T
1
in postorder, then T
2
in
postorder, …, then T
n
in
postorder, and ends by
visiting r.
T
1
T
2
T
n
...
Step 1
Visit T
1in
postorder
step 2
Visit T
2in
postorder
Step n
Visit T
nin
postorder

61. Traversal Example
•
Preorder
: a, b, e, j, k, n, o,
a
b
c d
Discrete Mathematics, Spring 2009
•
Preorder
: a, b, e, j, k, n, o,
p, f, c, d, g, l, m, h, I
•Inorder: j, e, n, k, o, p, b, f,
a, c, l, g, m, d, h, i
•Postorder: j, n, o, p, k, e, f,
b, c, l, m, g, h, i, d, a
e
f
g
h
i
j
k
lm
n o p