程序代写代做代考 algorithm 07.key

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)

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

Basic Graph Concepts

a node
(aka vertex)

an
edge

an edge
weight

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}

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

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 = {(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)}

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

Paths

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.

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.

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 Acyclic

Directed Cyclic 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
2

Table
3

Table
4

Table
5

Guest List

1 Aunt Martha

2 Aunt Sally

3 Uncle Joe

4 Cousin Andy

… ….

Modelling with Graphs

Each person becomes a node. An edge between
v and u means v and u cannot sit together.

1 2

Guest List

1 Aunt Martha

2 Aunt Sally

3 Uncle Joe

4 Cousin Andy

… ….

Now colour the nodes so that
no two adjacent nodes
have the same colour.

Modelling with Graphs

Each person becomes a node. An edge between
v and u means v and u cannot sit together.

1 2

Guest List

1 Aunt Martha

2 Aunt Sally

3 Uncle Joe

4 Cousin Andy

… ….

Now colour the nodes so that
no two adjacent nodes
have the same colour.

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

Adjacency Matrix

For an undirected graph, this matrix
is symmetric about the diagonal.

Graph Representations:
Undirected Graphs

Adjacency List
An array of linked lists

(Assuming lists are kept in sorted order.)

Graph Representations:
Directed Graphs

Adjacency Matrix

Graph Representations:
Directed Graphs

Adjacency List

Graph Representations

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

Next time

• Graph traversal, where we get down to the details
of graph algorithms

Related Posts