COMP90038
Algorithms and Complexity
Lecture 7: Graphs and Graph Concepts (with thanks to Harald Søndergaard)
Toby Murray
toby.murray@unimelb.edu.au
DMD 8.17 (Level 8, Doug McDonell Bldg)
http://people.eng.unimelb.edu.au/tobym @tobycmurray
2
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 search.
•
every node of a graph, namely depth-first and breadth-first
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 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
•
to graph problems—more on this in Week 12
Basic Graph Concepts
an edge weight
a node (aka vertex)
an edge
This graph is undirected since edges do not have directions associated with them.
3 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Graph Concepts
Undirected Graph
(Edges do not have directions associated with them.)
4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Graph Concepts
Directed Graph
(Each edge has an associated direction.)
5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Graph Concepts
Connected Graph
(Each node is reachable from all others by following edges.)
6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Graph Concepts
Not Connected Graph, with 2 Components
7 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
8
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
V = {a,b,c,d,e,f,g}
•
•
•
•
E = symmetric closure of E = {(a, b), (a, c), (a, d),
{(a, b), (a, c), (a, d), (a, e), (b, d), (b, e),
(a, e), (b, d), (b, e), (c, f), (d, e), (f, g)}
(c, f), (d, e), (f, g)}
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
V = {a,b,c,d,e,f,g}
•
•
•
•
9
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
E
== {{((a,,b)),,((a,,c)),,((a,,d)),, (a(a,,ee),),(b(b,,dd),),(c(b,,f)e,), (d(c,,ef), (ed, be), (gf,,gf)}
E
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 For connected graphs:
In-degree of v: number
of edges going to v
Out-degree of v: number of edges leaving from v
• •
•
10
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
11
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
Paths
A path:
b, a, e, d, a, c
12
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Cycles
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.)
Weighted Graphs
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.
13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Dense vs Sparse Graphs
Dense Graph
(lots of edges, relative
to number of nodes)
Sparse Graph
(few edges, relative
to number of nodes)
14 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Cyclic vs Acyclic
Cyclic
Directed Cyclic
Acyclic
Directed Acyclic Graph
(a dag)
15 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Rooted Trees
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.
16 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
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 (they’d better be dags) are central in scheduling problems:
17 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Modelling with Graphs
Imagine I’m doing the seating plan for a wedding.
Table 1
Table 5
Table Table 24
Table 3
Guest List
1 Aunt Martha
2 Aunt Sally
3 Uncle Joe
4 Cousin Andy
… ….
18 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Modelling with Graphs
Each person becomes a node. An edge between v and u means v and u cannot sit together.
12
Now colour the nodes so that no two adjacent nodes have the same colour.
Guest List
1 Aunt Martha
2 Aunt Sally
3 Uncle Joe
4 Cousin Andy
… ….
3
19 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
4
Modelling with Graphs
Each person becomes a node. An edge between v and u means v and u cannot sit together.
12
Now colour the nodes so that no two adjacent nodes have the same colour.
Guest List
1 Aunt Martha
2 Aunt Sally
3 Uncle Joe
4 Cousin Andy
… ….
3
20 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
4
Modelling with Graphs
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.
21 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Graph Representations: Undirected Graphs
For an undirected graph, this matrix is symmetric about the diagonal.
22 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Adjacency Matrix
Graph Representations: Undirected Graphs
Adjacency List
An array of linked lists
(Assuming lists are kept in sorted order.)
23 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Graph Representations: Directed Graphs
24 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Adjacency Matrix
Graph Representations: Directed Graphs
25 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Adjacency List
Graph Representations
Different kinds of representations are better suited to different kinds of graphs.
26
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
For a dense graph adjacency matrix might be better
For a sparse graph adjacency list might
be better
27
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