Class Notes (807,392)
CS 341 (26)
Lecture

# Lecture #8B - Graph Algorithms PathAlgs Fall 2009

27 Pages
83 Views

School
University of Waterloo
Department
Computer Science
Course
CS 341
Professor
Forbes Burkowski
Semester
Fall

Description
Articulations Definition: A node v of a connected graph G is an articulation node (also called a cut vertex) if the removal of v and all its incident edges causes G to become disconnected. Motivation for articulations: Articulations are important in communication networks. In traffic flows they identify places that will stop traffic between two areas of a city if they become blocked. Finding Articulations (1) Problem: Given any graph G = (V, E), find all the articulation points. Possible strategy: For all vertices v in V: Remove v and its incident edges. Test connectivity using a DFS. Execution tim:(n(n + m)). Can we do better? 1 Finding Articulations (2) A DFS tree can be used to discover articulation points in (n + m) time. We start with a program that computes a DFS tree labeling the vertices with their discovery times. We also compute a function called low[v] that can be used to characterize each vertex as an articulation or non-articulation point. The root of the DFS tree (the root has a d[ ] value of 1) will be treated as a special case: Finding Articulations (3) The root of the DFS tree is an articulation point if and only if it has two children. Suppose the root has two or more children. Recall that the back edges never link the vertices in two different subtrees. So, the subtrees are only linked through the root vertex and if it is removed we will get two or more connected components (i.e. the root is an articulation point). Suppose the root is an articulation point. This means that its removal would produce two or more connected components each previously connected to this root vertex. So, the root has two or more children. 2 Finding Articulations (4) Computation of low[v]. We need another function defined on vertices: This quantity will be used in our articulation finding algorithm: low[v] = min{d[v], d[z] such that (u, z) is a back edge for some descendent u of v} So, low[v] is the discovery time of the vertex closest to the root and reachable from v by following zero or more edges downward, and then at most one back edge. Finding Articulations (5) For non-root vertices we have a different test. Suppose v is a non-root vertex of the DFS tree T. Then v is an articulation point of G if and only if there is a child w of v in T withd [ ] low w[ ] . Root Sufficiency: Assume such a child w exists. There is no descendent vertex of v that has a back edge going v above vertex v. Also, there is no cross link from w a descendent of v to any other subtree. So, when v is removed the subtree Possible links with w as its root will be disconnectedNo links like this from the rest of the graph. 3 Finding Articulations (6) Necessity: Assume no such child w exists. In this case all children of v have a descendent with a back edge going to an ancestor of v. When v is removed each of the children of v will still be connected to some vertex on the path going from the root to the vertex v. The graph stays connected and so v would not be an articulation point in this case. Finding Articulation Points Pseudocode function dfs-visit(v) status[v] := gray; time := time+1; d[v] := time; low[v] := d[v]; for each w in out(v) if status[w] == white // In this case (v,w) is a TREE edge dfs-visit(w); // NOTE: low[w] is now computed! if d[v] <= low[w] then Definitionof low[ ] record that vertex v is an articulation low[v] := min(low[v], low[w])// Note how low[ ] can propagate up to a parent. else if w is not the parent of v then //In this case (v,w) is a BACK edge low[v] := min(low[v], d[w]) status[v] := black; 4
More Less

Related notes for CS 341

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.