COMP20007 Design of Algorithms
Graphs and Graph Concepts
Lars Kulik Lecture 6 Semester 1, 2020
1
Graphs Again
One instance of the exhaustive search paradigm is graph traversal.
After this lecture we shall look at two ways of systematically visiting every node of a graph, namely depth-first and breadth-first search.
These two methods of graph traversal form the backbone of a surprisingly large number of useful graph algorithms.
Graph algorithms are useful for a large number of practical problems: network design, flow design, planning, scheduling, route finding, and other logistics applications.
2
Graphs, Mathematically
G = ⟨V , E ⟩
V : Set of nodes or vertices
E: Set of edges (a binary relation on V)
ac ac
df df begbeg
V = E =
{a,b,c,d,e,f ,g} symmetric closure of {(a, b), (a, c), (a, d),
(a, e), (b, d), (b, e), (c,f ),(d,e),(f ,g)}
V = E =
{a,b,c,d,e,f ,g} {(a, b), (a, c), (a, d), (a, e), (b, d), (c, f ),
(d, e), (e, b), (g, f )}
3
Graph Concepts
Undirected:
Directed:
ac ac
df df egbeg
Not connected, two components: ac ac
b
Connected:
df df begbeg
4
More Graph Concepts: Degrees of Nodes
If (u, v ) ∈ E then u and v are adjacent, or neighbours.
(u,v) is connects u and v, and are u and v incident to (u,v). The degree of node v is the number of edges incident to v.
For directed graphs, we talk about v’s in-degree (number of edges going to v) and its out-degree (number of edges going from v).
5
More Graph Concepts: Paths and Cycles
ac d
e
A path in ⟨V,E⟩ is a sequence of nodes v0,v1,…,vk from V, so
that (vi,vi+1) ∈ E.
The path v0,v1,…,vk has length k.
A simple path is one that has no repeated nodes.
A cycle is a simple path, except that v0 = vk , that is, the last node is the same as the first node.
b
f g
Path b,a,d,e,a,c shown in blue
6
More Graph Concepts
Unweighted:
Weighted:
ac ac
3
2
Dense:
b
9
1 df7d4f
egbeg
5
Sparse:
ac ac
df df begbeg
12
7
More Graph Concepts
Cyclic: Acyclic (actually, a tree): ac ac
df df begbeg
Directed cyclic: Directed acyclic (a dag): ac ac
df df begbeg
8
Rooted Trees
A (free) tree is a connected a acyclic graph.
A rooted tree is a tree with one node identified as special. Every other node is reachable from the root node.
bcd
e f g h i
j
When the root is removed, a set of rooted (sub-)trees remain.
We should draw the rooted tree as a directed graph, but usually we instead rely on the layout: “parents” sit higher than “children”.
9
Modelling with Graphs
Graph algorithms are of great importance because so many different problem types can be abstracted to graph problems.
For example, directed graphs are central in scheduling problems: walls doors
foundation
roof
windows
painting
10
Modelling with Graphs
Graphs find use in all sorts of modelling.
Assume you want to invite friends to dinner and you have k tables available.
Some guests dislike some of the others; thus we need a seating plan that avoids placing foes at the same table.
The natural model is an undirected graph, with a node for each guest, and an edge between any two guests that don’t get along.
This reduces your problem to the “graph k-colouring problem”: find, if possible, a colouring of nodes so that all connected nodes have a different colour.
11
Graph Representations, Undirected Graphs
abcdefg
a b c d e f g
0111100 1001100 1000000 1100100 1101000 0000001 0000010
ac
f eg
d b
The adjacency matrix for the graph.
12
Graph Representations, Undirected Graphs
ac d
b
→b→c→d→e →a→d→e
→a
→a→b→e →a→b→d
a b c d e f g
f eg→g
→f
The adjacency list representation.
(Assuming lists are kept in sorted order.)
13
Graph Representations, Directed Graphs
abcdefg
a b c d e f g
0111100 0001000 1000000 0000100 0100000 0000000 0000010
ac
f eg
d b
The adjacency matrix for the graph.
14
Graph Representations, Directed Graphs
a b c d e f g
ac
f eg
→b→c→d→e →d
→a
→e
→b
→f
The adjacency list representation.
d b
15
Graph Representations
Each representation has advantages and disadvantages.
Think of some! ✎
16
Up Next
Graph traversal, in which we get down to the nitty-gritty details of graph algorithms.
17