Transcript here

Graphs
Slide credits:
 K. Wayne, Princeton U.
 C. E. Leiserson and E. Demaine, MIT
 K. Birman, Cornell U.
These are not Graphs
...not the kind we mean, anyway
These are Graphs
K5
K3,3
=
Applications of Graphs







Communication networks
Routing and shortest path problems
Commodity distribution (flow)
Traffic control
Resource allocation
Geometric modeling
...
Undirected Graphs
Undirected graph. G = (V, E) is an ordered pair consisting of
V = nodes.
E = edges between pairs of nodes.
Captures pairwise relationship between objects.
Graph size parameters: n = |V|, m = |E|.
Two nodes connected by an edge are said to be neighbor.





V = { 1, 2, 3, 4, 5, 6, 7, 8 }
E = { 1-2, 1-3, 2-3, 2-4, 2-5, 3-5, 3-7, 3-8, 4-5, 5-6 }
n=8
m = 11
Some Properties of Undirected Graph


|E|= O(V2)
If G is connected |E|≥|V|–1
–
An undirected graph is connected if for every pair of nodes u and
v, there is a path between u and v.

deg(V) is defined as the number of edges incident to V
–
Handshaking lemma: Σv∈V deg(v) = 2|E|
Directed Graphs
Directed graph. G = (V, E)
Edge (u, v) goes from node u to node v.

Ex. Web graph - hyperlink points from one web page to another.
Directedness of graph is crucial.
Modern web search engines exploit hyperlink structure to rank web
pages by importance.


World Wide Web
Web graph.
Node: web page.
Edge: hyperlink from one page to another.


cnn.com
netscape.com
novell.com
cnnsi.com
timewarner.com
hbo.com
sorpranos.com
Graph Representation: Adjacency Matrix
Adjacency matrix. n-by-n matrix with Auv = 1 if (u, v) is an edge.
Two representations of each edge.
Space proportional to n2.
Checking if (u, v) is an edge takes O(1) time.
Identifying all edges takes O(n2) time.
Use for dense graph





1
2
3
4
5
6
7
8
1
0
1
1
0
0
0
0
0
2
1
0
1
1
1
0
0
0
3
1
1
0
0
1
0
1
1
4
0
1
0
1
1
0
0
0
5
0
1
1
1
0
1
0
0
6
0
0
0
0
1
0
0
0
7
0
0
1
0
0
0
0
1
8
0
0
1
0
0
0
1
0
Graph Representation: Adjacency List
Adjacency list. Node indexed array of lists.
Two representations of each edge.
degree = number of neighbors of u
Space proportional to m + n.
Checking if (u, v) is an edge takes O(deg(u)) time.
Identifying all edges takes O(m + n) time.
Use for sparse graph





1
2
3
2
1
3
4
5
3
1
2
5
7
4
2
5
5
2
3
4
6
6
5
7
3
8
8
3
7
8
Paths and Connectivity
Def. A path in an undirected graph G = (V, E) is a sequence P of nodes
v1, v2, …, vk-1, vk with the property that each consecutive pair vi, vi+1 is
joined by an edge in E.
Def. A path is simple if all nodes are distinct.
Def. An undirected graph is connected if for every pair of nodes u and
v, there is a path between u and v.
Cycles
Def. A cycle is a path v1, v2, …, vk-1, vk in which v1 = vk, k > 2, and the
first k-1 nodes are all distinct.
cycle C = 1-2-4-5-3-1
Trees
Def. An undirected graph is a tree if it is connected and does not
contain a cycle.
Theorem. Let G be an undirected graph on n nodes. Any two of the
following statements imply the third.
G is connected.
G does not contain a cycle.
G has n-1 edges.



Rooted Trees
Rooted tree. Given a tree T, choose a root node r and orient each edge
away from r.
Importance. Models hierarchical structure.
root r
parent of v
v
child of v
a tree
the same tree, rooted at 1
Graph Traversal



Problem: Search for a certain node or traverse all nodes in the
graph
Depth First Search
– Once a possible path is found, continue the search until the
end of the path
Breadth First Search
– Start several paths at a time, and advance in each one step
at a time
Depth First Traversal

A natural way to do Depth-first search (BFS) is using
recursion.
DFS( Node c ) {
Mark c "Visited”
For each neighbor n of c
If n "Unvisited"
DFS( n )
}
Possible visit sequence: 1, 2, 4, 5, 6, 3, 8, 7
Breadth First Traversal


Breadth-first search (BFS) not naturally recursive.
Use a queue so that vertices are visited in order according to
their distance from the starting vertex.
BFS(Node v) {
create a queue Q
enqueue v onto Q
mark v “Visited”
while Q is not empty {
dequeue t from Q
for each neighbor u of t do
if u is not marked {
mark u “Visited”
enqueue u onto Q
}
}
Breadth First Search
L0
L1
L2
L3
Visit sequence: 1, 2, 3, 4, 5, 7, 8, 6
Applications: Finding a Path




Find path from source vertex s to destination vertex d
Use graph search starting at s and terminating as soon as we reach d
Need to remember edges traversed
Use depth – first search
DFS
DFS Process
F
B
A
G
D
C
E
start
destination
B DFS on B
A DFS on A A
G
D
B
A
Call DFS on G
C
B
A
DFS on C
D
B
A
Call DFS on D
Return to call on B
found destination - done!
Path is implicitly stored in DFS recursion
Path is: A, B, D, G
Minimum spanning trees
Minimum spanning tree. Given a connected undirected graph G = (V, E)
with real-valued edge weights ce, an MST is a subset of the edges T 
E such that T is a spanning tree whose sum of edge weights is
minimized.
Minimum spanning trees
Greedy Algorithms
Prim's algorithm. Start with some root node s and greedily grow a tree
T from s outward. At each step, add the cheapest edge e to T that has
exactly one endpoint in T.
Theorem. Let T be the MST of G= (V, E), and let A⊆V. Suppose that
(u, v) ∈ E is the least-weight edge connecting A to V–A. Then, (u, v) ∈T.
Greedy Algorithms
Proof:
• Suppose (u, v) ∉T.
• Consider the unique simple path from u to v in T.
• Swap (u, v) with the first edge on this path that connects a vertex in
A to a vertex in V–A to get a lower-weight MST