07.key
http://people.eng.unimelb.edu.au/tobym
@tobycmurray
toby.murray@unimelb.edu.au
DMD 8.17 (Level 8, Doug McDonell Bldg)
Toby Murray
COMP90038
Algorithms and Complexity
Lecture 7: Graphs and Graph Concepts
(with thanks to Harald Søndergaard)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Graphs and Trees
• 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.
• The graph algorithms are useful because of the large number of
practical problems we can model as graph problems, in network
design, flow design, planning, scheduling, route finding, and other
logistics applications.
• Moreover, important numeric and logic problems can be reduced
to graph problems—more on this in Week 12
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Basic Graph Concepts
3
a node
(aka vertex)
an
edge
an edge
weight
This graph is
undirected
since edges
do not have
directions
associated
with them.
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Graph Concepts
4
Undirected Graph
(Edges do not have directions associated with them.)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Graph Concepts
5
Directed Graph
(Each edge has an associated direction.)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Graph Concepts
6
Connected Graph
(Each node is reachable from all others
by following edges.)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Graph Concepts
7
Not Connected Graph, with 2 Components
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Graphs, Mathematically
• A Graph G is a pair: 〈V,E〉
• V : set of nodes (aka vertices)
• E : set of edges (a binary relation on V)
• (u,v) ∈ E means there is an edge from u to v
8
V = {a,b,c,d,e,f,g}
E = {(a, b), (a, c), (a, d),
(a, e), (b, d), (b, e),
(c, f), (d, e), (f, g)}
E = symmetric closure of
{(a, b), (a, c), (a, d),
(a, e), (b, d), (b, e),
(c, f), (d, e), (f, g)}
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Graphs, Mathematically
• A Graph G is a pair: 〈V,E〉
• V : set of nodes (aka vertices)
• E : set of edges (a binary relation on V)
• (u,v) ∈ E means there is an edge from u to v
9
V = {a,b,c,d,e,f,g}
E = {(a, b), (a, c), (a, d),
(a, e), (b, d), (b, e),
(c, f), (d, e), (f, g)}
E = {(a, b), (a, c), (a, d),
(a, e), (b, d), (c, f),
(d, e), (e, b), (g, f)}
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Degrees of Nodes
• If (v, u) ∈ E then v and u are adjacent, or neighbours
• Edge (v, u) is incident on, or connects, v and u
• Degree of a node v: number of edges incident on v
10
For connected graphs:
In-degree of v: number
of edges going to v
Out-degree of v:
number of edges
leaving from v
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Paths
11
A path:
b, a, e, d, a , c
A path in ⟨V, E⟩ is a sequence of nodes v0,v1,…,vk from
V, so that each (vi,vi+1) ∈ E.
The path v0,v1,…,vk has length k.
A simple path is one that has no repeated nodes.
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Cycles
12
A cycle:
b, a, e, d, b
A cycle is a path that starts and finishes at
the same node and does not traverse the same
edge more than once.
(Cycles turn out to be very important for
lots of applications.)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Weighted Graphs
13
Each edge (v,u) has a weight indicating some information
about that connection from v to u
The information depends on what the graph represents:
network congestion, physical distance, cost, etc.
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Dense vs Sparse Graphs
14
Dense Graph
(lots of edges, relative
to number of nodes)
Sparse Graph
(few edges, relative
to number of nodes)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Cyclic vs Acyclic
15
Cyclic Acyclic
Directed Cyclic Directed Acyclic Graph(a dag)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Rooted Trees
16
A (free) tree is a
connected, acyclic
graph, e.g.
A rooted tree is a tree with
one node (the root)
identified as special. Every
other node is reachable
from the root node.
When the root is removed, a set of
rooted (sub-)trees remain.
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Modelling with Graphs
17
Graph algorithms are of great importance
because so many different problem types can
be abstracted to graph problems.
For example, directed graphs (they’d better be
dags) are central in scheduling problems:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Modelling with Graphs
18
Imagine I’m doing the seating plan for a wedding.
Table
1
Table
2
Table
3
Table
4
Table
5
Guest List
1 Aunt Martha
2 Aunt Sally
3 Uncle Joe
4 Cousin Andy
… ….
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Modelling with Graphs
19
Each person becomes a node. An edge between
v and u means v and u cannot sit together.
1 2
3
Guest List
1 Aunt Martha
2 Aunt Sally
3 Uncle Joe
4 Cousin Andy
… ….
4
Now colour the nodes so that
no two adjacent nodes
have the same colour.
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Modelling with Graphs
20
Each person becomes a node. An edge between
v and u means v and u cannot sit together.
1 2
3
Guest List
1 Aunt Martha
2 Aunt Sally
3 Uncle Joe
4 Cousin Andy
… ….
4
Now colour the nodes so that
no two adjacent nodes
have the same colour.
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Modelling with Graphs
21
Seating planning with k tables can be
reduced to the graph k-coloring problem:
Find, if possible, a colouring of nodes so that no
two connected nodes get the same colour.
Lots of other problems can be
reduced to graph colouring.
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Graph Representations:
Undirected Graphs
22
Adjacency Matrix
For an undirected graph, this matrix
is symmetric about the diagonal.
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Graph Representations:
Undirected Graphs
23
Adjacency List
An array of linked lists
(Assuming lists are kept in sorted order.)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Graph Representations:
Directed Graphs
24
Adjacency Matrix
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Graph Representations:
Directed Graphs
25
Adjacency List
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Graph Representations
26
Different kinds of representations are better
suited to different kinds of graphs.
For a dense graph
adjacency matrix
might be better
For a sparse graph
adjacency list might
be better
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Next time
• Graph traversal, where we get down to the details
of graph algorithms
27