COMP9020 23T1
Week 5
Graphs
Textbook (R & W) - Ch. 3, Sec. 3.2
Ch. 6, Sec. 6.1-6.5
A. Aho & J. Ullman. Foundations of Computer Science in C,
p. 522–526 (Ch. 9, Sec. 9.10)
Problem set 5 + quiz
Mid-term test on Friday Week 6
1
Mid-term Test
1 hour (+5mins reading time) online test on Moodle
Friday, 24 March between 10:30am and 11:40am
⇒ must start no later than by 10:35am to get the full 1hr+5mins
Format:
Same environment as weekly quizzes but strictly timed
7 questions, each worth between 2 and 7 marks
maximum marks: 26
mix of multiple choice (with ≥ 1 correct answers),
numerical/short answer and open answer
NB
The test will be manually marked, unlike the quizzes.
2
Mid-term Test
If you
. . . are uncertain about how to interpret a question
. . . are unsure about how to answer a question
. . . find a question too difficult
⇒ do answer to the best of your understanding
⇒ do focus on the questions that you find easier
⇒ do not agonise about a question or your answer after you’ve
submitted
Practice test with 3 sample questions available in Moodle
1hr time limit, opens Friday, closes Thursday week at 10am
sample solutions to open questions will be provided
3
Graphs
Terminology (the most common; there are many variants):
(Undirected) Graph — pair G = (V ,E ) where
V – set of vertices
E – set of edges
Every edge e ∈ E corresponds uniquely to the set (an unordered
pair) {xe , ye} of vertices xe , ye ∈ V .
A directed edge is called an arc; it corresponds to the ordered pair
(xa, ya). A directed graph consist of vertices and arcs.
NB
Edges {x , y} and arcs (x , y) with x = y are called loops.
We will only consider graphs without loops.
NB. Binary relations on finite sets correspond to directed graphs.
Symmetric relations correspond to undirected graphs.
4
Graphs in Computer Science
Examples
1 The WWW can be considered a massive graph where the
nodes are web pages and arcs are hyperlinks.
2 The possible states of a program form a directed graph.
3 The map of the earth can be represented as an undirected
graph where edges delineate countries.
NB
Applications of graphs in Computer Science are abundant, e.g.
route planning in navigation systems, robotics
optimisation, e.g. timetables, utilisation of network structures
compilers using “graph colouring” to assign registers to
program variables
5
Vertex Degrees
Degree of a vertex v in a graph G
deg(v) = | { w ∈ V (G ) : (v ,w) ∈ E (G ) } |
i.e., the number of edges attached to the vertex
Regular graph — all degrees are equal
Degree sequence D0,D1,D2, . . . ,Dk
where Di = no. of vertices of degree i
Question
What is D0 + D1 + . . .+ Dk?∑
v∈V deg(v) = 2 · |E (G )|; thus the sum of vertex degrees is
always even.
There is an even number of vertices of odd degree ( 6.1.8 )
6
Paths
A path in a graph (V ,E ) is a sequence of edges that link up
v0
{v0,v1}−−−−→ v1 {v1,v2}−−−−→ . . . {vn−1,vn}−−−−−−→ vn
where ei = {vi−1, vi} ∈ E
length of the path is the number of edges: n
neither the vertices nor the edges have to be all different
Subpath of length r : (em, em+1, . . . , em+r−1)
Path of length 0: single vertex v0
Connected graph — each pair of vertices joined by a path
Connected component of G — a connected subgraph of G
that is not contained in a larger connected subgraph of G
7
Examples
Exercise
6.1.13(a) Draw a connected, regular graph on four vertices, each
of degree 2
6.1.13(b) Draw a connected, regular graph on four vertices, each
of degree 3
6.1.13(c) Draw a connected, regular graph on five vertices, each
of degree 3
6.1.14(a) Graph with 3 vertices and 3 edges
6.1.14(b) Two graphs each with 4 vertices and 4 edges
8
Examples
Exercise
6.1.13 Connected, regular graphs on four vertices
(a) (b) (b) (c)
none
6.1.14 Graphs with 3 vertices and 3 edges must have a cycle
(a) the only one (b) (b)
9
Exercise
6.1.20(a) Graph with |E (G )| = 21 edges has a degree sequence
D0 = 0,D1 = 7,D2 = 3,D3 = 7,D4 =?
Find |V (G )|!
6.1.20(b) How would your answer change, if at all, when D0 = 6?
10
Exercise
6.1.20(a) Graph with |E (G )| = 21 edges has a degree sequence
D0 = 0,D1 = 7,D2 = 3,D3 = 7,D4 =?
Find |V (G )|∑
v deg(v) = 2|E |; here
7 · 1 + 3 · 2 + 7 · 3 + x · 4 = 2 · 21 giving x = 2, thus
|V | = ∑Di = 19.
6.1.20(b) How would your answer change, if at all, when D0 = 6?
No change to D4; |V | = 25.
11
Cycles
Recall paths v0
e1−→ v1 e2−→ . . . en−→ vn
simple path — ei 6= ej for all edges of the path (i 6= j)
closed path — v0 = vn
cycle — closed simple path, all vi distinct (except v0 = vn)
acyclic path — vi 6= vj for all vertices in the path (i 6= j)
NB
1 Cn = (e1, . . . , en) is a cycle iff removing any single edge leaves
an acyclic path. (Show that the ‘any’ condition is needed!)
2 C is a cycle if it has the same number of edges and vertices
and no proper subpath has this property.
(Show that the ‘subpath’ condition is needed, i.e., there are
graphs G that are not cycles and |E (G )| = |V (G )|; every
such G must contain a cycle!)
12
Trees
Acyclic graph — graph that doesn’t contain any cycle
Tree — connected acyclic graph
A graph is acyclic iff it is a forest (collection of unconnected
trees)
NB
Graph G is a tree
⇔ G is acyclic and |V (G )| = |E (G )|+ 1.
(Show how this implies that the graph is connected!)
⇔ there is exactly one simple path between any two vertices.
⇔ G is connected, but becomes disconnected if any single edge
is removed.
⇔ G is acyclic, but has a cycle if any single edge on already
existing vertices is added.
13
Exercise
6.7.3 (supp) Tree with n vertices, n ≥ 3.
Always true, false or could be either?
(a) |E (T )| ?= n
(b) at least one vertex of deg 2
(c) at least two v1, v2 s.t. deg(v1)=deg(v2)
14
Exercise
6.7.3 (supp) Tree with n vertices, n ≥ 3.
Always true, false or could be either?
(a) |E (T )| ?= n — False
(b) at least one vertex of deg 2 — Could be either
(c) at least two v1, v2 s.t. deg(v1)=deg(v2) — True
NB
A tree with one vertex designated as root is called a rooted tree.
It imposes an ordering on the edges: ‘away’ from the root — from
parent nodes to children. This defines a level number of a node as
its distance (= path length) from the root.
The height of a rooted tree is the largest level number of a vertex.
Another very common notion in Computer Science is that of a
DAG — a directed, acyclic graph.
15
Graph Isomorphisms
ι : G −→ H is a graph isomorphism if
(i) ι : V (G ) −→ V (H) is 1–1 and onto (a so-called bijection)
(ii) {x , y} ∈ E (G ) iff {ι(x), ι(y)} ∈ E (H)
Two graphs are called isomorphic if there exists (at least one)
isomorphism between them.
Example
All nonisomorphic trees on 2, 3, 4 and 5 vertices.
16
Graph Isomorphisms
ι : G −→ H is a graph isomorphism if
(i) ι : V (G ) −→ V (H) is 1–1 and onto (a so-called bijection)
(ii) {x , y} ∈ E (G ) iff {ι(x), ι(y)} ∈ E (H)
Two graphs are called isomorphic if there exists (at least one)
isomorphism between them.
Example
All nonisomorphic trees on 2, 3, 4 and 5 vertices.
17
Automorphisms and Asymmetric Graphs
An isomorphism from a graph to itself is called automorphism.
Every graph has at least the trivial automorphism
(trivial means: ι(v) = v for all v ∈ V (G ))
Graphs with no non-trivial automorphisms are called asymmetric.
The smallest non-trivial asymmetric graphs have 6 vertices.
(Can you find another one with 6 nodes? There are seven more.)
18
Edge Traversal
Definition
Euler path — path containing every edge of G exactly once
Euler circuit — closed Euler path
(Named after Leonhard Euler (Switzerland), 1707–1783)
Characterisations
G (connected) has an Euler circuit iff deg(v) is even for all
v ∈ V (G ).
G (connected) has an Euler path iff either it has an Euler
circuit (above) or it has exactly two vertices of odd degree.
NB
These characterisations apply to graphs with loops as well
For directed graphs the condition for existence of an Euler
circuit is indeg(v) = outdeg(v) for all v ∈ V (G )
19
Special Graphs
Complete graph Kn
n vertices, all pairwise connected, n(n−1)2 edges.
Complete bipartite graph Km,n
Has m + n vertices, partitioned into two (disjoint) sets,
one of n, the other of m vertices.
All vertices from different parts are connected; vertices from
the same part are disconnected. No. of edges is m · n.
Complete k-partite graph Km1,...,mk
Has m1 + . . .+ mk vertices, partitioned into k disjoint sets,
respectively of m1,m2, . . . vertices. All vertices from different
sets are connected; vertices from the same set are
disconnected. No. of edges is
∑
i1
2
∑
i 6=j mimj
These graphs generalise the complete graphs Kn = K1, . . . , 1︸ ︷︷ ︸
n
20
Example
K5 : K3,3 :
Exercise
6.2.14 Which complete graphs Kn have an Euler circuit?
When do bipartite, 3-partite complete graphs have an Euler circuit?
Kn has an Euler circuit for n odd
Km,n — when both m and n are even
Kp,q,r — when p + q, p + r , q + r are all even, ie. when p, q, r are
all even or all odd
21
Example
K5 : K3,3 :
Exercise
6.2.14 Which complete graphs Kn have an Euler circuit?
When do bipartite, 3-partite complete graphs have an Euler circuit?
Kn has an Euler circuit for n odd
Km,n — when both m and n are even
Kp,q,r — when p + q, p + r , q + r are all even, ie. when p, q, r are
all even or all odd
22
Vertex Traversal
Definition
Hamiltonian path visits every vertex of graph exactly once
Hamiltonian circuit visits every vertex exactly once except
the last one, which duplicates the first
(Named after Sir William Rowan Hamilton (Ireland), 1805–1865)
NB
Finding such a circuit, or proving it does not exist, is a difficult
problem — the worst case is NP-complete.
Examples (when the circuit exists)
n-cube; Hamiltonian circuit = Gray code
complete graphs Km; bipartite graphs Km,n if m = n
Knight’s tour on a chessboard (incl. rectangular boards)
23
Exercise
6.5.5(a) How many Hamiltonian circuits does Kn,n have?
Let V = V1 ∪˙ V2
start at any vertex in V1
go to any vertex in V2
go to any new vertex in V1
. . . . . .
There are n! ways to order each part and two ways to choose the
‘first’ part, implying c = 2(n!)2 circuits.
24
Exercise
6.5.5(a) How many Hamiltonian circuits does Kn,n have?
Let V = V1 ∪˙ V2
start at any vertex in V1
go to any vertex in V2
go to any new vertex in V1
. . . . . .
There are n! ways to order each part and two ways to choose the
‘first’ part, implying c = 2(n!)2 circuits.
25
Given a graph it is nontrivial to verify that there is no Hamiltonian
circuit: there is nothing obvious to specify that could assure us
about this property.
In contrast, if a circuit is given, it is immediate to verify that it is a
Hamiltonian circuit.
These situations demonstrate the often enormous discrepancy in
difficulty of ’proving’ versus (simply) ’checking’.
26
Colouring
Informally: assigning a “colour” to each vertex (e.g. a node in an
electric or transportation network) so that the vertices connected
by an edge have different colours.
Formally: A mapping c : V −→ [1 . . n] such that for every
e = {v ,w} ∈ E
c(v) 6= c(w)
The minimum n sufficient to effect such a mapping is called the
chromatic number of a graph G = (E ,V ) and is denoted χ(G ).
NB
This notion is extremely important in operations research, esp. in
scheduling.
There is a dual notion of ‘edge colouring’ — two edges that share
a vertex need to have different colours. Curiously enough, it is
much less useful in practice.
27
Properties of the Chromatic Number
χ(Kn) = n
If G has n vertices and χ(G ) = n then G = Kn
Proof.
Suppose that G is ‘missing’ the edge {v ,w}, as compared with
Kn. Colour all vertices, except w , using n − 1 colours. Then assign
to w the same colour as that of v .
If χ(G ) = 1 then G is totally disconnected: it has 0 edges.
If χ(G ) = 2 then G is bipartite.
For any tree χ(T ) = 2.
For any cycle Cn its chromatic number depends on the parity
of n — for n even χ(Cn) = 2, while for n odd χ(Cn) = 3.
28
Cliques
Graph (V ′,E ′) subgraph of (V ,E ) — V ′ ⊆ V and E ′ ⊆ E .
Definition
A clique in G is a complete subgraph of G . A clique of k nodes is
called k-clique.
The size of the largest clique is called the clique number of the
graph and denoted κ(G ).
Theorem
χ(G ) ≥ κ(G ).
Proof.
Every vertex of a clique requires a different colour, hence there
must be at least κ(G ) colours.
However, this is the only restriction. For any given k there are
graphs with κ(G ) = k, while χ(G ) can be arbitrarily large.
29
NB
This fact (and such graphs) are important in the analysis of
parallel computation algorithms.
κ(Kn) = n, κ(Km,n) = 2, κ(Km1,...,mr ) = r .
If κ(G ) = 1 then G is totally disconnected.
For a tree κ(T ) = 2.
For a cycle Cn
κ(C3) = 3, κ(C4) = κ(C5) = . . . = 2
The difference between κ(G ) and χ(G ) is apparent with just
κ(G ) = 2 — this does not imply that G is bipartite. For example,
the cycle Cn for any odd n has χ(Cn) = 3.
30
Exercise
9.10.1 (Aho & Ullman)
χ(G )? κ(G )? A largest clique?
31
Exercise
9.10.1 (Aho & Ullman)
χ(G1) = κ(G1) = 3; χ(G2) = κ(G2) = 2; χ(G3) = κ(G3) = 3
G1
G2
G3
32
Exercise
9.10.3 (Aho & Ullman) Let G = (V ,E ) be an undirected graph.
What inequalities must hold between
the maximal deg(v) for v ∈ V
χ(G )
κ(G )
maxv∈V deg(v) + 1 ≥ χ(G ) ≥ κ(G )
33
Exercise
9.10.3 (Aho & Ullman) Let G = (V ,E ) be an undirected graph.
What inequalities must hold between
the maximal deg(v) for v ∈ V
χ(G )
κ(G )
maxv∈V deg(v) + 1 ≥ χ(G ) ≥ κ(G )
34
Planar Graphs
Definition
A graph is planar if it can be embedded in a plane without its
edges intersecting.
Theorem
If the graph is planar it can be embedded in a plane (without
self-intersections) so that all its edges are straight lines.
NB
This notion and its related algorithms are extremely important to
VLSI and visualising data.
35
Two minimal nonplanar graphs
K5 : K3,3 :
36
Exercise
9.10.2 (Aho & Ullman)
Is (the undirected version of) this graph planar? Yes
37
Exercise
9.10.2 (Aho & Ullman)
Is (the undirected version of) this graph planar? Yes
38
Theorem
If graph G contains, as a subgraph, a nonplanar graph, then G
itself is nonplanar.
A minor of a graph is any graph obtained by repeatedly deleting
vertices, deleting edges and merging adjacent vertices.
=⇒
Theorem
A graph is nonplanar iff it contains K5 or K3,3 as a minor.
39
Theorem
Kn for n ≥ 5 is nonplanar.
Proof.
It contains K5: choose any five vertices in Kn and consider the
subgraph they define.
Theorem
Km,n is nonplanar when m ≥ 3 and n ≥ 3.
Proof.
They contain K3,3 — choose any three vertices in each of two
vertex parts and consider the subgraph they define.
40
Question
Are all Km,1 planar?
Answer
Yes, they are trees of two levels — the root and m leaves.
41
Question
Are all Km,1 planar?
Answer
Yes, they are trees of two levels — the root and m leaves.
42
Question
Are all Km,2 planar?
43
Question
Are all Km,2 planar?
Answer
Yes; they can be represented by “glueing” together two such trees
at the leaves.
Sketching Km,2:
Also, among the k-partite graphs, planar are K2,2,2 and K1,1,m.
The latter can be depicted by drawing one extra edge in K2,m,
connecting the top and bottom vertices.
44
NB
Finding a ‘basic’ nonplanar obstruction is not always simple.
Petersen’s graph
(Julius Petersen (Denmark), 1839–1910)
It contains both K5 and K3,3 as a minor (cf. Slide 39) while it does
not directly contain either of them. (Try to find K3,3 as a minor!)
45
Summary
Graphs, trees, vertex degree, connected graphs, connected
components, paths, cycles Cn
Graph isomorphisms, automorphisms
Special graphs: complete Kn, complete bi-, k-partite Km1,...,mk
Traversals
Euler paths and circuits (edge traversal)
Hamiltonian paths and circuits (vertex traversal)
Graph properties:
chromatic number χ(G ), clique number κ(G ), planarity
Coming up . . .
Mid-term test (covers weeks 1-5)
Ch. 4, Sec. 4.2-4.6 (Induction and Recursion)