Graph Connectivity and Minimum Cuts1 Basic ConceptsOften we want to find a minimum cut in the entire graph, not just between aspecified source and destination. The size of this minimum cut characterizesthe connectivity of the graph.Let us consider an undirected graph, which is also unweighted, that is, nocapacities assigned to the edges. If it models the topology of a network, thenthe size of the minimum cut tells us that minimum how many links haveto fail to disconnect the network (assuming, of course, that it was originallyconnected). This is the edge-connectivity. We can similarly define nodeconnectivity, as well. These connectivity values characterize the vulnerabilityof the network, that is, how easy it is to disconnect it. We mainly focus onthe (simpler) edge-connectivity. Therefore, often we just call it connectivity,for short.Definitions• Edge-connectivity between two nodes: λ(x, y) = minimum num-ber of edges that need to be deleted to disconnect nodes x 6= y.λ(x, y) is the size of a minimum cut between x and y.• Edge-connectivity (of the graph): λ(G) = minimum number ofedges that need to be deleted to disconnect G.λ(G) = minx,yλ(x, y).λ(G) is the size of a minimum cut.• Node-connectivity of the graph: κ(G) = minimum number ofnodes (vertices) that need to be deleted, such that the remaining graphis either disconnected, or has no edge at all.κ(G) is the size of a minimum vertex-cut.Naming convention: If a graph has λ(G) = k, we call it k-connected. Simi-larly, if κ(G) = k, then the graph is called k-node-connected. Occasionallywe also use the phrase that the graph is ≥k-connected, to express thatλ(G) ≥ k.Exercises1. Construct a graph with κ(G) = 2 and λ(G) = 3.2. Let δ(G) denote the minimum node degree in a graph G. Prove thatκ(G) ≤ λ(G) ≤ δ(G)holds for any graph G.Solution: If λ(G) = k, then G can be disconnected by removing kedges. Then by removing one end-node of each of these k edges, we canalso disconnect it, since removing a node always means also removingits adjacent edges. Therefore,κ(G) ≤ λ(G) (1)must hold. (Note that κ(G) < λ(G) can happen, as some of the end-points may coincide.) Regarding the minimum degree, it is clear that ifwe remove all the δ(G) edges that are adjacent to a node of minimumdegree, then it gets disconnected from the rest of the graph. Thus, weobtainλ(G) ≤ δ(G). (2)Inequalities (1) and (2) together imply the statement that we wantedto prove.3. Consider a connected network with undirected links. We have twopieces of information about the network:• The network has 37 nodes.• It is impossible to disconnect the network by removing 2 or fewerlinks.Justify wether the following statement is true or not:There must be a node with at least 4 links adjacent to it.Solution: If it is impossible to disconnect the network by removing 2links, then each node must have degree ≥ 3. Let us assume that thedegree of each node is exactly 3. Then, if we sum up the degrees, weget 3 × 37 = 111. On the other hand, the sum of the degrees is twicethe number of edges, since each edge contributes 2 to the sum (1 ateach of its endpoints). Thus, we get 111 = 2m, where m is the numberof edges. Since m must be an integer, the equality111 = 2mcannot hold, as the right-hand side is even, the left-hand side is odd.Thus, the assumption that all degrees are 3 leads to a contradiction.Therefore, there must be a node with degree d 6= 3. Since we cannotdisconnect the network by removing 2 or fewer links, d ≤ 2 is impossi-ble. This yields that this node must have degree at least 4.4. Let G be a graph with λ(G) = k. Enlarge this graph by adding a newnode u and connecting it to ` ≥ k different old nodes v1, . . . v`that canbe chosen arbitrarily from G. Let G0denote the extended graph. Provethat λ(G0) ≥ k. Moreover, if ` = k, then λ(G0) = k.Solution: Assume that λ(G0) < k. Then there is a cut C containing≤ k − 1 edges, such that their removal separates the nodes of G0intotwo sets A, B with no connection to each other. Let us call A the setthat contains u. We observe that u cannot be alone in A, since then allits neighbors would be in B, which means all the ` ≥ k edges adjacentto u would be in the cut, contradicting to |C| ≤ k − 1. If, however,u is not alone in A, then after removing u, we get a decomposition ofthe original nodes into two sets (A − {u} and B), such that they areseparated by the cut C. Since |C| ≤ k − 1, this would contradict toλ(G) = k. Therefore, we obtain that no cut of size ≤ k − 1 can existin G0, so λ(G0) ≥ k must hold. Moreover, if Moreover, if ` = k, thenthe degree of u is k, implying λ(G0) ≤ k (see Exercise 2 in Section 1),so then λ(G0) = k must hold.Comment: This exercise shows that if we add a new node to a k-connected graph, and want to preserve the level of connectivity, thenit is enough to make sure that the new node has degree ≥ k. This willautomatically guarantee ≥ k-connectivity of the extended graph.2 Some Fundamental TheoremsA fundamental question is that how many disjoint paths (routes) can beguaranteed between any two nodes. We focus here on the link-disjoint case.In a network topology this is important to ensure backup routes in case oflink failures. A fundamental charaterization is provided by the followingtheorem.Theorem 1 (Menger’s Theorem) For any connected graph G the followinghold:• For any two different nodes x, y the value of λ(x, y) is equal to themaximum number of edge-disjoing paths connecting x and y.• λ(G) is equal to the smallest value k with the property that between anytwo nodes there are at least k edge-disjoint paths.Exercises1. Consider an optical network. Assume we know that this network cannotbe disconnected by two link failures. We want to select for any twonodes a primary route to carry the traffic between them. Furthermore,we also want to select two backup routes for the same node pair, suchthat the backup routes are link disjoint from the primary route, andalso from each other, to provide adequate protection whenever at mosttwo links fail simultaneously. Is it true that such a route system canalways be selected under the given conditions?Solution: The answer is yes. Since 2 link failures cannot disconnectthe network, we have λ(G) ≥ 3. Then, by Menger’s Theorem, betweenany two nodes there is a route system that contains (at least) 3 link-disjoint routes.2. In a network two disjoint sets of nodes, A and B are selected,
View Full Document
Unlocking...