Exercise – MAX flow AppsSolutionSolutionExerciseExercise - solutionSolution – contd.Slide 7Some Fundamental TheoremsSlide 9Exercise-1Exercise -1 solutionExercise-2Exercise-2Exercise – MAX flow Apps•Consider a connected network with undirected links. We have two pieces of information about the network:–The network has 37 nodes.–It is impossible to disconnect the network by removing 2 or fewer links.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 2 links, then each node must have degree ≥3. Let us assume that the degree of each node is exactly 3. •Then, if we sum up the degrees, we get 3 * 37 = 111. •On the other hand, the sum of the degrees is twice the number of edges, since each edge contributes 2 to the sum (1 at each of its endpoints). •Thus, we get 111 = 2m, where m is the number of edges.Solution•Since m must be an integer, the equality111 = 2m cannot 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 ≠ 3. Since we cannot disconnect the network by removing 2 or fewer links, d ≤ 2 is impossible. This yields that this node must have degree at least 4.Exercise•Let G be a graph with λ(G) = k. Enlarge this graph by adding a new node u and connecting it to l ≥ k different old nodes v1, … vl that can be chosen arbitrarily from G. Let G’ denote the extended graph. Prove that λ(G’) ≥ k. Moreover, if l = k, then λ(G’) = k.Exercise - solution•Assume that λ(G’) < k. Then there is a cut C containing ≤k - 1 edges, such that their removal separates the nodes of G’ into two sets A,B with no connection to each other.• Let us call A the set that contains u. We observe that u cannot be alone in A, since then all its neighbors would be in B, which means all the l ≥ k edges adjacent to u would be in the cut, contradicting to |C| ≤ k - 1.Solution – contd.•If, however, u is not alone in A, then after removing u, we get a decomposition of the original nodes into two sets (A – {u} and B), such that they are separated by the cut C. Since |C| ≤ k - 1, this would contradict λ(G) = k. Therefore, we obtain that no cut of size ≤ k-1 can exist in G’, so λ(G’) ¸ k must hold. Moreover, if l = k, then the degree of u is k, implying λ(G’) ≤ k (see previous Exercise), so then λ(G’) = 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, then it is enough to make sure that the new node has degree ≥ k. –This will automatically guarantee ¸ k-connectivity of the extended graph. It does not matter to which old nodes is the new node connected, just it needs to be connected to at least k. If we keep adding more and more new nodes this way, with arbitrarily selected neighbors, then we can create large, messy graphs, such that their k-connectedness is still guaranteed. –It would be harder to see about them directly that they are k-connected, without this construction.Some Fundamental Theorems•A fundamental question is that how many disjoint paths (routes) can be guaranteed 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 of link failures. •A fundamental charaterization is provided by the following theorem.•Theorem 1 (Menger's Theorem) For any connected graph G the following hold:–For any two different nodes x, y the value of λ(x, y) is equal to the maximum number of edge-disjoing paths connecting x and y.–λ(G) is equal to the smallest value k with the property that between any two nodes there are at least k edge-disjoint paths.Exercise-1•Consider an optical network. Assume we know that this network cannot be disconnected by two link failures. •We want to select for any two nodes a primary route to carry the traffic between them. •Furthermore, we also want to select two backup routes for the same node pair, such that the backup routes are link disjoint from the primary route, and also from each other, to provide adequate protection whenever at most two links fail simultaneously. •Is it true that such a route system can always be selected under the given conditions?Exercise -1 solution•The answer is yes. •Since 2 link failures cannot disconnect the network, we have λ(G) ≥ 3, •Then, by Menger's Theorem, between any two nodes there is a route system that contains (at least) 3 link-disjoint routes.Exercise-2•In a network two disjoint sets of nodes, A and B are selected, •Each containing k nodes. We know that the network is k-connected. •Is it always possible to connect each node in A with a node in B, such that the connecting routes are link-disjoint, and, moreover, they do not share any end-nodes?Exercise-2•Yes. •Let us add a new node u and connect it to all nodes in A. •Similarly, add another new node v and connect it to all nodes in B. •The extended graph remains k-connected. •Then, by Menger's Theorem, there are k edge-disjoint paths connecting u and v. •The parts of these paths that fall in the original graph exactly satisfy the
View Full Document
Unlocking...