Download presentation

1
**Internally Disjoint Paths**

Internally Disjoint Paths : Two paths u to v are internally disjoint if they have no common internal vertex. Internally disjoint paths u v Common internal vertex u v

2
Theorem 4.2.2 A graph G having at least three vertices is 2-connected if and only if for each pair u,vV(G) there exists internally disjoint u,v-paths in G. (Proof of if part) It suffices to show for each pair u,vV(G), deletion of any vertex in V(G) cannot separate u from v. 2. This is clearly true because G has internally disjoint u,v-paths.

3
**Theorem 4.2.2 (Proof of only if part) G is 2-connected. (Premise)**

That G has internally disjoint u,v-paths is proved by induction on d(u,v). 3. Basis Step: d(u,v)=1. 3.1. The graph G-uv is connected since ’(G)>=(G)>=2. 3.2. There exists a u,v-path in G-uv, which is internally disjoint in G from the u,v-path formed by the edge uv itself.

4
**Theorem 4.2.2 4. Induction Step: d(u,v)>1. 4.1. Let k=d(u,v).**

4.2. Let w be the vertex before v on a shortest u,v-path. d(u,w)=k-1. 4.3 G has internally disjoint u,w-paths P and Q. (Induction Hypothesis)

5
**Theorem 4.2.2 v u w P Q 4.4. If vV(P)V(Q), then**

we find the desired paths in the cycle PQ. v u w P Q

6
**Theorem 4.2.2 Q w v P u R since G is 2-connected.**

4.5. Otherwise, G-w is connected 4.6. G-w contains a u,v-path R. 4.7. If R avoids P or Q, we are done. Q w v P u R

7
Theorem 4.2.2 4.8. Otherwise, let z be the last vertex of R (before v) belonging to PQ. We assume that zP by symmetry. 4.9. We combine the u,z-subpath of P with the z,v-subpath of R to obtain a u,v-path internally disjoint from Qwv. R z P w u v Q

8
**Lemma 4.2.3 (Expansion Lemma)**

If G is a k-connected graph, and G’ is obtained from G by adding a new vertex y with at least k neighbors in G, then G’ is k-connected.

9
Theorem 4.2.4 For a graph G with at least three vertices, the following conditions are equivalent (and characterize 2-connected graphs). G is connected and has no cut-vertex. For all x,yV(G), there are internally disjoint x,y-paths. For all x,yV(G), there is a cycle through x and y. (G)>=1, and every pair of edges in G lies on a common cycle.

10
**Theorem 4.2.4 Proof. 1. Theorem 4.2.2 proves AB.**

2. For BC, the cycles containing x and y corresponds to pairs of internally disjoint x,y-paths. 3. For DC, (G)>=1 implies that vertices x and y are not isolated.

11
**Theorem 4.2.4 4. Consider edges incident to x and y.**

5. Case 1: there are at least two such edges e and f. Then e and f lies on a common cycle. There is a cycle through x and y. 6. Case 2: only one such edge e. Let f be an edge incident to the third vertex. e and f lies on a common cycle. There is a cycle through x and y. u x y z f x y e f y x e

12
**Theorem 4.2.4 7. For CD. G satisfies condition C.**

G satisfies condition A. G is connected. (G)>=1. 8. We need to show any two edges, uv and xy, lie on a common cycle. 9. Add to G the vertices w with neighborhood {u,v} and z with neighborhood {x,y} to form G’.

13
Theorem 4.2.4 10. Since G is 2-connected, Lemma implies G’ is 2-connected. 11. w and z lie on a cycle C in G’. 12. Since w,z each have degree 2, C must contain the paths u,w,v and x,z,y but not the edges uv or xy. 13. Replacing the path u,w,v and x,z,y in C with the edges uv and xy yields the desired cycle through uv and xy in G. u v x y w z

14
x,y-cut x,y-cut: Given x,yV(G), a set SV(G)-{x,y} is an x,y-separator or x,y-cut if G-S has no x,y-path. (x,y): the minimum size of x,y-cut. (x,y): the maximum size of a set of pairwise internally disjoint x,y-paths.

15
**Example 4.2.16 {b,c,z,d} is an x,y-cut of size 4. (x,y)<=4.**

G has four internally disjoint x,y-paths. (x,y)>=4. {b,c,x} is an w,z-cut of size 3. (w,z)<=3. G has three internally disjoint w,z-paths. (w,z)>=3.

16
**Theorem 4.2.17 (Menger Theorem)**

If x,y are vertices of a graph G and xyE(G), then (x,y) = (x,y). Proof. 1. An x,y-cut must contain an internal vertex of every internally disjoint x,y-paths, and no vertex can cut two internally disjoint x,y-paths. (x,y)>= (x,y). 2. We prove equality by induction on n(G).

17
**Theorem 4.2.17 (Menger Theorem)**

Basis Step: n(G)=2. xyE(G) yields (x,y)= (x,y)=0. Induction Step: n(G)>2. Let k= G(x,y). No minimum cut properly contains N(x) or N(y) since N(x) and N(y) are x,y-cuts. 3. Case 1: G has a minimum x,y-cut S other than N(x) or N(y). 4. Case 2: Every minimum x,y-cut is N(x) or N(y).

18
Theorem 5. For Case 1, let V1 be the set of vertices on x,S-path, and let V2 be the set of vertices on S,y-path. 6. SV1 and SV2 SV1V2. 7. If there exists v such that vV1V2–S, then combing x,v-portion of some x,S-path and v,y-portion of some S,y-path yields an x,y-path that avoids the x,y-cut S. It contradicts that S is a minimum x,y-cut. 8. This implies S=V1V2. S V1 V2 x y G v

19
Theorem 9. Form H1 by adding to G[V1] a vertex y’ with edges from S, and form H2 by adding to G[V2] a vertex x’ with edges from S. H2 x’ y H1 y’ x

20
Theorem 10. Every x,y-path in G starts with an x,S-path (contained in H1). Every x,y’cut in H1 is an x,y-cut in G. H1(x,y’)= k. 11. H2(x’,y)= k by the same argument in 10. 12. H1 and H2 are smaller than G since N(y) S and N(x) S. H1(x,y’)=k= H2(x’,y).

21
Theorem 13. S=V1V2. Deleting y’ from the k paths in H1 and x’ from the k paths in H2 yields the desired x,S-paths and S,y-paths in G that combine to form k internally disjoint x,y-paths in G.

22
Theorem 14. For Case 2, if there exists node uN(x)N(y), then S-u is x,y-cut in G-u. G-u(x,y)=k-1. G-u has k-1 internally disjoint x,y-paths by induction hypothesis. 15. Combining these k-1 x,y-path and the path x,u,y yields k internally disjoint x,y-paths in G.

23
Theorem 16. If there exists node v{x}N(x)N(y){y}, then S is minimum x,y-cut in G-v. (If there exists a x,y-cut, S’, in G-v whose size is smaller than |S|, then S’{v} is a x,y-cut in G. It is a contradiction.) G-v(x,y)=k. G-v has k internally disjoint x,y-paths by induction hypothesis. These are k internally disjoint x,y-paths in G.

24
Theorem 17. We may assume that N(x) and N(y) partition V(G)-{x,y}. 18. Let G’ be the bipartite graph with bipartition N(x), N(y) and edge set [N(x),N(y)]. 19. Every x,y-path in G uses some edge from N(x) to N(y). x,y-cuts in G are the vertex covers of G’. (G’)=k. G’ has a matching of size k by Theorem These k edges yield k internally disjoint x,y-paths of length 3.

25
Line Graph (Digraph) Line Graph (Digraph): The line graph (digraph) of a graph (digraph) G, written L(G), is the graph (digraph) whose vertices are the edges of G, with efE(L(G)) when e=uv and f=vw in G.

26
Theorem If x and y are distinct vertices of a graph or digraph G, then the minimum size of an x,y-disconnecting set of edges equals the maximum number of pairwise edge-disjoint x,y-paths. Proof. 1. Modify G to obtain G’ by adding two new vertices s, t and two new edges sx and yt. 2. Cleary, ’G(x,y)= ’G’(x,y) and ’G(x,y)= ’G’(x,y). a d f y x s c t b g e

27
Theorem 3. A x,y-path exists in G’ that traverses edges p, q, r if and only if a sx,yt-path exists in L(G’) that traverses vertices p, q, r .

28
Theorem 4. Edge-disjoint x,y-paths in G’ become internally disjoint sx,yt-paths in L(G’), and vice versa. ’G’(x,y)= L(G’)(sx,yt). 5. A set of edges disconnects y from x in G’ if and only if the corresponding vertices of L(G’) form an sx,yt-cut. ’G’(x,y)=L(G’)(sx,yt). 6. L(G’)(sx,yt)= L(G’)(sx,yt). ’G’(x,y)= ’G’(x,y). ’G(x,y)= ’G(x,y).

Similar presentations

© 2021 SlidePlayer.com Inc.

All rights reserved.

To make this website work, we log user data and share it with processors. To use this website, you must agree to our Privacy Policy, including cookie policy.

Ads by Google