图论GraphTheorych4章节

1、1,Chapter 4 Connectivity and Paths,2,Loops are irrelevant for connection, so in this chapter we assume that our graphs and digraphs have no loops, especially when considering degree conditions. 4.1.1. Definition. A separating set or vertex cut of a graph G is a set SV(G) such that G - S has more than one component. The connectivity of G, written (G), is the minimum size of a vertex set S such that G - S is disconnected or has only one vertex. A graph G is k-connected if its connectivity is at le

2、ast k. 4.1.2. Example. Connectivity of Kn and Km,n,3,4.1.3. Example. The hypercube Qk. For k 2, the neighbors of one vertex in Qk form a separating set, so (Qk) k. To prove that (Qk) = k, we show that every vertex cut has size at least k. We use induction on k. Basis step: k0,1. For k 1, Qk is a clique with k+1 vertices and has connectivity k.,4,Induction step: k 2. By the induction hypothesis, (Qk-l) = k-1. Consider the description of Qk as two copies Q and Q of Qk-l plus a matching that joins

3、corresponding vertices in Q and Q . Let S be a vertex cut in Qk. If Q-S is connected and Q-S is connected, then Qk- S is also connected unless S contains at least one endpoint of every matched pair. This requires |S| 2k-l, but 2k-l k for k 2. Hence we may assume that Q-S is disconnected, which means that S has at least k - 1 vertices in Q, by the induction hypothesis. If S contains no vertices of Q, then Q - S is connected and all vertices of Q - S have neighbors in Q - S, so Qk - S is connected

4、. Hence S must also contain a vertex of Q. This yields |S| k, as desired.,5,4.1.4. Example. Harary graphs. Given 2 k n, place n vertices around a circle, equally spaced. If k is even, form Hk,n by making each vertex adjacent to the nearest k/2 vertices in each direction around the circle. If k is odd and n is even, form Hk,n by making each vertex adjacent to the nearest (k - 1) /2 vertices in each direction and to the diametrically opposite vertex. In each case, Hk,n is k-regular. The graphs H4,

5、8,and H5, 8 appear below.,6,When k and n are both odd, index the vertices by the integers modulo n. Construct Hk,n from Hk-l,n by adding the edges i i + (n - 1)/2 for 0 i (n - 1)/2. The graph H5, 9 appears below.,7,4.1.5. Theorem. (Harary 1962a) (H k ,n) = k, and hence the minimum number of edges in a k-connected graph on n vertices is kn/2. Hararys construction determines the degree conditions that allow a graph to be k-connected.,8,4.1.6. Remark. A direct proof of (G) k considers a vertex cut

6、S and proves that |S| k, or it considers a set S with fewer than k vertices and proves that G-S is connected. The indirect approach assumes a cut of size less than k and obtains a contradiction. The indirect proof may be easier to find, but the direct proof may be clearer to state. Note also that if k n (G) and G has a vertex cut of size less than k, then G has a vertex cut of size k - 1 (first delete the cut, then continue deleting vertices until k - 1 are gone, retaining a vertex in each of tw

7、o components). Finally, proving (G) = k also requires presenting a vertex cut of size k; this is usually the easy part.,9,4.1.7. Definition. A disconnecting set of edges is a set F E(G) such that G-F has more than one component. A graph is k-edge-connected if every disconnecting set has at least k edges. The edge-connectivity of G, written (G), is the minimum size of a disconnecting set (equivalently, the maximum k such that G is k-edge-connected).,10,4.1.7. Definition. Given S, T V(G), we write

8、 S, T for the set of edges having one endpoint in S and the other in T. An edge cut is an edge set of the form S, S , where S is a nonempty proper subset of V (G) and S denotes V (G) - S.,11,4.1.8. Remark. Disconnecting set vs. edge cut. Every edge cut is a disconnecting set, since G-S, S has no path from S to S . The converse is false, since a disconnecting set can have extra edges. Nevertheless, every minimal disconnecting set of edges is an edge cut (when n(G) 1). If G - F has more than one c

9、omponent for some F E(G), then for some component H of G - F we have deleted all edges with exactly one endpoint in H. Hence F contains the edge cut V(H), V(H), and F is not a minimal disconnecting set unless F = V(H), V(H).,12,4.1.9. Theorem. (Whitney 1932a) If G is a simple graph, then (G) (G) (G). Proof: The edges incident to a vertex v of minimum degree form an edge cut; hence (G) (G). It remains to show that (G) (G). We have observed that (G) n(G) - 1 (see Example 4.1.2). Consider a smallest edge cut S, S . If every vertex of S is adjacent to every vertex of S , then |S, S | = |S|S| n(G) - 1 (G), and the desired inequality holds.,13,Otherwise, we choose xS and y S with x y. Let T consist of all neighbors of x in S and all vertices of S - x with neighbors in S . Every x, y- path passes through T, so T is a separating set. Also, picking the edges from x to TS and one

《图论GraphTheorych4章节》由会员E****分享，可在线阅读，更多相关《图论GraphTheorych4章节》请在金锄头文库上搜索。