# CS代考 COMP90038 – cscodehelp代写

COMP90038
Algorithms and Complexity
Lecture 7: Graphs and Graph Concepts (with thanks to Harald Søndergaard)

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

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 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.

Graph Concepts
Undirected Graph
(Edges do not have directions associated with them.)

Graph Concepts
Directed Graph
(Each edge has an associated direction.)

Graph Concepts
Connected Graph
(Each node is reachable from all others by following edges.)

Graph Concepts
Not Connected Graph, with 2 Components

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}

8
E
== {{((a,,b)),,((a,,c)),,((a,,d)),, (d(c,,ef), (ed, be), (gf,,gf)}
E
(a(a,,ee),),(b(b,,dd),),(c(b,,f)e,),

9
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)}

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

Paths
A path:
b, a, e, d, a, c
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.

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.)
12

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.

Dense vs Sparse Graphs
Dense Graph
(lots of edges, relative to number of nodes)
Sparse Graph
(few edges, relative to number of nodes)

Cyclic vs Acyclic
Cyclic
Directed Cyclic
Acyclic
Directed Acyclic Graph
(a dag)

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.

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:

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
… ….

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
… ….
3
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
… ….
3
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.

Graph Representations: Undirected Graphs
For an undirected graph, this matrix is symmetric about the diagonal.

Graph Representations: Undirected Graphs
(Assuming lists are kept in sorted order.)

Graph Representations: Directed Graphs

Graph Representations: Directed Graphs

Graph Representations
Different kinds of representations are better suited to different kinds of graphs.
26