代写代考 - PowCoder代写

STUDY MATERIAL:
• [CLRS] chapters 22, 23, 24, 25, 26 • Lecture Note 10
• Algorithmics Animation Workshop:

 Dijkstra – Single Source Shortest Paths  Minimum Spanning Tree
 Max-Flow Min-Cut
 Traveling Salesman

 Graph Representations
 Graph Traversals:  Breadth First Search  Depth First Search
 Un-weighted Graphs:
 Topological Sort
 Strongly Connected Components  Bi-connected Components
 Weighted Graphs:
 Minimum Spanning Trees  Shortest Paths
 Matching

GRAPH REPRESENTATIONS

Graph G = (V, E)
V = V(G) = vertex set of G
E = E(G) = edge set of G ( a set of pairs of vertices of G)
Undirected graph: edges are unordered pairs of vertices:
V = { 1, 2, 3, 4, 5, 6 }
E = {(1,2), (1,4), (1,5), (2,3), (2,5), (3,5), (4,5)}
Directed graph (or digraph): edges are ordered pairs of vertices:
V = { 1, 2, 3, 4, 5, 6 }
E = { (1,2), (1,4), (1,5), (3,2),
4 5 6 (4,4), (4,5), (5,1), (5,2), (5,3)}

1 13 2 -16 3
E = {(1,2,13), (1,4,14), (1,5,17), (2,3,-16), (2,5,21), (3,5,18), (4,5,23)}
Edge Weighted Graph
G = (V, E, w) w:E |
6 e.g., w(1,5) = w(5,1) = 17.
1 13 2 -16 3
E = { (1,2,13), (1,4,14), (1,5,15), (3,2,-16) (4,5,23), (5,1,14), (5,2,21), (5,3,18)}
6 e.g., w(1,5) = 15, w(5,1) = 14.

Adjacency Matrix
1 if (i, j)  E(G) A[i,j]0 otherwise
, fori,jV(G). 123456
1 2 3 4 5 6
1 2 3 4 5 6

Weighted Adjacency Matrix
w(i,j) A[i,j] 0
if (i,j)E(G) ifij,(i,j)E(G) otherwise
,fori,jV(G). 123456
9 7 5-6 34

(Weighted) Adjacency List Structure
Adj[i]{j,w(i,j) | (i,j)E(G)}, for iV(G). Adj
1 2 3 4 5 6
9 7 5-6 4 3 3

Vertex vV(G): degree (or valance) , in-degree, out-degree
Undirected G: deg(v) = | { u | (v,u)  E(G) } | = | Adj[v] |
Digraph G: outdeg(v) = | { u | (v,u)  E(G) } | = | Adj[v] | indeg(v) = | { u | (u,v)  E(G) } |
deg(v) = outdeg(v) + indeg(v)
The Hand- :
For any graph (directed or undirected) we have:
deg(v)  2 | E | . vV(G)
For any directed graph we also have:
indeg(v) outdeg(v)|E|. vV(G) vV(G)

Adjacency Matrix vs Adjacency List Structure
complexity
Adjacency Matrix
Adjacency List
# memory cells
Initialize structure
Scan (incident edges of) all vertices
List vertices adjacent to uV(G)
O(|Adj[u]|)
Is (u,v)  E(G)?
O(|Adj[u]|)

BREADTH FIRST SEARCH
Generalizes level-order traversal on trees.

BFS Properties
 A simple linear-time graph search algorithm with many applications.
 Generalizes the level-order traversal on trees.
 G = (V,E) a given directed or undirected graph.
 Given a source sV, BFS explores all parts of G that are reachable from s.
 Discovers (visits) each vertex u in order of its un-weighted distance d(u) from s.  This distance is the length of the un-weighted shortest path from s to u.
d(u) = 1+d(p(u))

How BFS works
s d(s)=0 Scanned nodes (BLACK)
d(v) = 1+d(u)
Greedy Choice: Scan the oldest frontier node.
Q: How? A: Maintain
frontier nodes in a Queue Q (FIFO List).
Iteratively dequeue a vertex u & scan it:
visit every unexplored vertex v adjacent to u.
Unexplored nodes (WHITE)

while Q   do
u  Dequeue(Q)
for each vertex v  Adj[u] do
13. end-while end
BFS Algorithm
Algorithm BFS( G, s )
for each vertex v  V(G) do § initialize color[v], d[v], p[v]  WHITE, , nil
color[s], d[s]   GRAY, 0 Q  ; Enqueue(s, Q)
§ s is the first frontier vertex § advance frontier
§ u = earliest visited frontier node § scan u: explore every edge (u,v) §visitunexploredadjacentnodev
ifcolor[v]=WHITE thendo
color[v], d[v], p[v]  GRAY, 1+d[u], u
end-if end-for
Enqueue(v, Q)
§ v is a new frontier node § u is scanned
color[u]  BLACK

Digraph G:
BFS Tree: 1
2 s= 1 2 3
SCAN: 67951243 DONE

Undirected graph G: 012 s=123
BFS Tree: 1

BFS Running Time
WHITE GRAY BLACK
• The only way that a node becomes
gray & hence enters Q is when it was white (lines 2-3-4, 8-9-10).
• So, each node enters Q at most once (& only if it was reachable from s).
• Thus, a node u is removed from Q at most once (line 6).
• So, a node u is scanned at most once & becomes black (lines 7-13).
This takes O(1+|Adj[u]|) time.
• Therefore, the total time is:
Algorithm BFS( G, s )
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. end
for each vertex v  V(G) do
color[v], d[v], p[v]  WHITE, , nil
color[s], d[s]   GRAY, 0 Q  ; Enqueue(s, Q) whileQ do
u  Dequeue(Q)
for each vertex v  Adj[u] do
ifcolor[v]=WHITE thendo
color[v], d[v], p[v]  GRAY, 1+d[u], u Enqueue(v, Q)
color[u]  BLACK
OV  1 | Adj[u] |  OV  1  | Adj[u] |  O(V  E).
 uV(G)   uV(G) uV(G) 

More BFS Properties
For each edge (u,v)  E(G) we have d[v]  1 + d[u].
Furthermore, if G is undirected, then | d[u] – d[v] |  1.
Proof sketch: By the time u becomes black (is scanned), v must have been visited (if not earlier). …
If G is undirected, then (u,v) = (v,u).
FACT 3: BFS Edge Types:
Each traversed edge (u,v)E(G) could be a tree-edge or a non-tree edge with respect to the BFS. There are 3 possible types of non-tree edges:
1. BFS tree-edge: u = p[v]
2. Back-edge: v is a BFS ancestor of u (possibly u itself)
3. Forward-edge: v is a BFS proper descendant of u (not a tree edge). This case will never happen by FACT 2!
4. Cross-edge: u & v are not ancestor-descendant of each other wrt BFS tree.

BFS Tree = Shortest Path Tree rooted at source
FACT 4: For each node v in the BFS tree,
the tree path from root s to v is the un-weighted shortest path from s to v in G. (Nodes that are not in the BFS tree are not reachable from s.)
More specifically, we have:
p[v] = parent of v in the BFS tree
= predecessor of v on its shortest path from s
(nil, if v is not reachable from s),
d[v] = length of shortest path from s to v in G
Algorithm PrintPath(v) if v = nil then return PrintPath(p[v]) print v
if v  s if v  s
end Proof: Let v be a node reachable from s in G. Then, d[v]  0
( if v is not reachable from s).
But that is the solution to the shortest path equations:
1  d[π[v]] 
d [ v ]   0 i f v  s minu{1d[u]|(u,v)E(G)} if vs
because, by Fact 2: (u,v)E(G), we have d[v]  1+d[u]. (The state of nodes not reachable from s is obvious.)

Graph Coloring
G = an undirected graph.
Graph Coloring:
Let k be a positive integer.
G is k-colorable if each node of G can be colored by one of at most k colors such that for each edge (u,v) E(G), color(u)  color(v).
(This problem has long history and many applications.)
A 3-coloring of the Peterson graph: (It is not 2-colorable.)
1-colorable  E(G) = 
2-colorable: also easy to detect (see next slides) 3-colorable: is hard to detect (see NP-completeness)
Kn needs n colors.
All planar graphs are 4-colorable.

Bipartite Graphs
G = an undirected graph.
Bipartiteness:
G is bipartite if V(G) can be partitioned into two disjoint subsets X and Y such that for each edge (u,v)E(G), either uX & vY, or vX & uY.

FACT 5: Let G be an undirected graph. The following statements are equivalent:
1. G is bipartite,
2. G is 2-colorable,
3. G has no odd-length cycle,
4. In BFS of G, for every edge (u,v)E(G), we have | d[u] – d[v] | = 1.
These can be tested in O(V+E) time (constructive proof).
[(1)  (2)]: Let (X,Y) be a bipartition of V(G). Color nodes in X with color 1, and nodes in Y with color 2.
[(2)  (3)]: If G is 2-colorable, then vertices of any cycle have alternate colors. Hence, the cycle has even length.
[(3)  (4)]: By Fact 2 we know that for each edge (u,v), |d[u] – d[v]|  1. If d[u] = d[v] (i.e., they are at the same BFS tree level), then edge (u,v) plus the tree paths from each of u and v to their lowest common ancestor form an odd-length cycle.
A contradiction.
[(4)  (1)]: Do BFS of each connected component of G: Set
V1 = { u V(G) | d[u] is even }, V2 = { u V(G) | d[u] is odd }. (V1 , V2 ) is a valid bipartition of G.

DEPTH FIRST SEARCH
Generalizes preorder and postorder traversal on trees.

DFS Properties
 Another simple linear-time graph search algorithm with many applications.
 Generalizes the pre-order and post-order traversals on trees.
 G = (V,E) a given directed or undirected graph.
 DFS creates a forest of node-disjoint trees with non-tree edges between nodes. Pick an unvisited node as the root of the next DFS tree and advance the search.
 Greedy Choice:
within the same DFS tree, advance the search from the most recent visited node.
 Recursive DFSvisit(u):
explores nodes in the sub-tree rooted at u
(the nodes reachable from u that are still unexplored at the time u gets visited).
 DFS(u) recursive call is active  u is an ancestor of the most recent visited node.
 [ d[u], f[u] ] = DFS time stamp for node u: d[u] = start time of DFSvisit(u),
f[u] = finishing time of DFSvisit(u).

DFS Algorithm
Algorithm DFS(G)
2. for each vertex u  V(G) do color[u], p[u]  WHITE, nil
3. for each vertex u  V(G) do
if color[u] = WHITE then DFSvisit(u) § u is root of next DFS tree
Procedure DFSvisit(u)
d[u]  time  time + 1 color[u]  GRAY
for each vertex v  Adj[u] do
§ DFSvisit(u) discovery time § u is visited
§ explore edge (u,v)
§ visit unexplored adjacent node v § (u,v) is a DFS tree-edge
§ v is most recent visited node
§ u is scanned
§ DFSvisit(u) finishing time
11. end-for
12. color[u]  BLACK
13. f[u]timetime+1 end
ifcolor[v]=WHITE thendo p[v]  u
DFSvisit(v) end-if

Tree drawing convention Downward & left-to-right

bcdef hijk
[1,16] [2,15]
[18,21] [19,20]
[11,14] [12,13]
[4,7] [5,6]
Each edge is traversed twice (once in each direction). The first traversal of each edge is:
downward if it’s a tree-edge; upward otherwise. 29

DFS Running Time
Algorithm DFS(G)
1. time  0
2. for each vertex uV(G) do color[u], p[u]  WHITE, nil
3. for each vertex uV(G) do
if color[u] = WHITE then DFSvisit(u)
Procedure DFSvisit(u)
d[u]timetime+1 color[u]  GRAY
for each vertex vAdj[u] do
10. end-if
11. end-for
12. color[u]  BLACK
13. f[u]timetime+1 end
ifcolor[v]=WHITE thendo p[v]  u
DFSvisit(v)
GRAY BLACK
• DFSvisit(u) is called exactly once for each node u.
• Excluding recursive calls, DFSvisit(u) takes O(1+|Adj[u]|) time. • Therefore, the total time is:
OV  1 | Adj[u] |  OV  1  | Adj[u] |  O(V  E).
 uV(G)   uV(G) uV(G) 

The Parenthesis Theorem (PT)
The Parenthesis Theorem (PT):
1. For all nodes u: d[u] < f[u]. [d[u], f[u]] is activation time interval of DFSvisit(u). 2. For every pair of nodes u & v, their time intervals [d[u],f[u]] and [d[v],f[v]] are either disjoint or one encloses the other (no partial overlap). 3. u is a DFS ancestor of v if and only if [d[u],f[u]] encloses [d[v],f[v]], that is, d[u]  d[v] < f[v]  f[u]. Consider DFS sub-trees Tu and Tv rooted at u & v, respectively. Tu and Tv are either completely disjoint, or one includes the other. Their DFSvisit activation time intervals will behave accordingly. In the illustrative figure to the right, [d[u],f[u]] encloses [d[v],f[v]], but is disjoint from [d[w],f[w]]. The White-Path Theorem (WPT) The White-Path Theorem (WPT): Node u is a DFS ancestor of node v if and only if when u is discovered, there is a path of all white nodes from u to v. Proof [of ]: The nodes on the DFS tree path from u to v are all white at the activation time of DFSvisit(u). Proof [of ]: P = an all white-node path from u to v when DFSvisit(u) is called. Claim: v will be visited before DFSvisit(u) is finished, i.e., v will become a descendant of u. Proof of Claim: by induction on length of P: Basis ( |P| = 0): Obvious; u=v. Ind. Step (|P| > 0): Let w be successor of u on P.
During DFSvisit(u), when wAdj[u] is considered, if w is still white, it will get visited & becomes a descendant of u.
So, some node on P, other that u, becomes a descendant of u.
Consider the last node x of P that becomes a descendant of u.
The sub-path P’ of P from x to v is strictly shorter than P and is all white when x is discovered. So, by the induction hypothesis, v becomes a descendant of x, which is a descendant of u. [Note: P is not necessarily the DFS tree path from u to v! Where is that in the proof?]

DFS Edge Classification of Digraphs
At the time edge uv is traversed, we have the following possibilities:
tree-edge: color[v] = WHITE
back-edge: color[v] = GRAY
Tree drawing convention Downward & left-to-right
forward-edge:
color[v] = BLACK &vu
cross-edge:
color[v] = WHITE Impossible by WPT!33
d[u] < d[v] cross-edge: color[v] = BLACK & d[v] < d[u] DiGraph: state of edge uv at the completion of DFS: u DFS Finishing Times f[u] > f[v]:
cross-edge
forward-edge
f[u]  f[v]:

DFS Edge Classification of Undirected Graphs
Undirected Graph:
only 2 types of edges: tree-edges & back-edges.
f[u] > f[v]
f[u]  f[v] u
Cross edge: impossible by the White Path Theorem.
So each edge is between an ancestor-descendant pair.
Such non-tree edges are called back-edges by convention
(the first time they are traversed from descendant towards ancestor).

The Cycle Theorem
The Cycle Theorem: [G = a directed or undirected graph]
G has a cycle if and only if DFS(G) has a back-edge.
Proof [of ]:
A back-edge from u to v followed by the DFS tree path from v to u forms a cycle.
Proof [of ]:
Suppose there is a cycle C in G.
Among the nodes on C, let u be the one with minimum f[u]. Let v be the successor of u on C.
Then f[u]  f[v] by the choice of u.
So, edge (u,v) is a back-edge.
For undirected graphs there is a simpler argument:
without back-edges, we are left with a forest of trees. Trees are acyclic.

TOPOLOGICAL SORT
Linearly Order a Partially Ordered Set

Directed Acyclic Graph (DAG)
 DAG = digraph with no directed cycles.  Modeling applications:
 generalization of layered digraphs
 reachability paths in a DAG form a partial order on nodes
(reflexive, anti-symmetric, transitive)
 tasks with precedence constraints
 job sequencing
 Topological ordering of a DAG G:
A linear ordering of V(G) such that
(u,v)E(G), u appears before v in the linear order. abdhgcfe

Topological Sort Algorithm 1
A DAG G has at least one vertex with in-degree 0 (& one vertex with out-degree 0).
G has no cycles  all paths in G have finite length (no node can repeat on a path). Let P be a longest path in G.
Suppose P starts at node u and ends in node v.
indeg(u) = outdeg(v) = 0 (otherwise, we can extend P to a longer path).
Example DAG:
indeg(a) indeg(d) outdeg(e) = 0
TOPOLOGICAL SORT ALGORITHM 1:
• Find a node u with in-degree 0.
• Remove u and all its out-edges from G. A smaller DAG remains. • Add u to the end of the linear order.
• Iterate this process until there is no more node remaining in G.
EXERCISE: Give an O(V+E)-time implementation of this algorithm.

Topological Sort Algorithm 2
FACT 2: Reverse DFS Post-Order, i.e., reverse DFS finishing time is a topological order on a DAG.
For any edge uv in digraph G:
f[u]  f[v]  uv is a back edge.
DAG G has no cycles, hence no back-edges.
So, for every edge uv in DAG G: f[u] > f[v]. Linearly order nodes in decreasing order of f[.]. See implementation & example on the next page.

Topological Sort Algorithm 2
In O(V + E) time do a DFS of G with the following modification: Push nodes into an initially empty stack S when they become black
(i.e., an added line at the end of DFSvisit).
At the end of DFS(G): repeatedly pop(S); nodes come out in topological order.
DFS(G): ae
A topological ordering of G: efabdc

STRONGLY CONNECTED
COMPONENTS

Graph Connectivity
 How well is a graph connected?
 Connectivity issues arise in communication & transportation networks.
 Identify bottlenecks in case parts of the network break down or malfunction.  Fault tolerance in distributed networks.
 Digraph Connectivity:
 Semi-connectivity:
can every pair of nodes have at least one-way communication?
 Strong connectivity (discussed next)
can every pair of nodes have two-way communication?
 Un-directed graph Connectivity:
 Edge/Node connectivity (discussed in the following section)
How many edges/nodes need to be removed to disconnect the graph?

Digraph Strong Connectivity abc
Strongly Connected: There is a directed path from any node to any other node.
NOT Strongly Connected: there is no path from d to a.
3 Strongly Connected Components
SCC Component Graph is a DAG:

Strongly Connected Components
 Reachability: u ~~ v.
v is reachable from u, – Reflexive
– Transitive
 Mutual Reachability:
i.e., there is a directed path from u to v.
u ~~ v : u and v are mutually reachable, i.e., u~~v & v~~u.
 equivalence relation on V(G)  ~~ partitions V(G) into equivalence classes.
– Reflexive – Symmetric – Transitive
 Strongly Connected Components of G:
Subgraphs of G induced by these equivalence classes.
 Remaining edges are called cross-component edges.

aa bc GT:bc
ghij ghij a
By the WPT
every node of an SCC falls within the same DFS tree.
So, each DFS tree is the union of one or more
How can we disentangle them?

• SCC roof = the node x with minimum d[x] among all nodes of the SCC (nodes d, f, e, a in the example below).
• WPT  all nodes of an SCC are DFS descendants of its roof.
•  SCC roof x has maximum f

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts