python代写-MAST30011
时间:2021-05-17
MAST30011 Graph Theory 2021 ASSIGNMENT 2 Due 13:00pm Friday 21 May 2021 1. Let G be the bipartite graph below and let M = {v1w1, v3w3, v4w4} be the matching in G as shown in green colour. (a) Grow a maximal alternating tree in G with respect to M with root v2. (b) Use this tree to obtain a matching in G with four edges. (c) Is it possible to find an augmenting path with respect to this new matching? If so give such a path and augment along it to obtain a matching with five edges. Otherwise give reasons why such an augmenting path does not exist. v1 v2 v3 v4 v5 w1 w2 w3 w4 w5 Figure 1: Question 1 2. Let M be a matching in a graph G, and let S be the set of vertices matched by M . Prove that there exists a maximum matching M∗ in G such that all vertices in S are matched by M∗. 3. Let N be the following network with source x and sink y as shown below. The arc capacities are shown beside each arc, and an initial flow is given in parentheses. (a) Starting from the given initial flow, apply the labelling algorithm to find a maximum flow in N . Show every stage of the algorithm, and in each iteration of the algorithm label all vertices that can be labelled and show how you obtain the labels of such vertices. State explicitly the value of the maximum flow found. (b) Give explicitly the minimum cut in N obtained from your results in (a). 1 aed 6 (4) b x y c 3 (3) 4 (3) 3 (1) 4 (1) 2 (1) 4 (0) 1 (1) 3 (0) 5 (0) 2 (1) Figure 2: Question 3 4. Recall that a nontrivial graph H is called k-connected if p(x, y) ≥ k for every pair of distinct vertices x, y of H. Using this definition, prove that for any `-connected graph G and any edge e of G, where ` ≥ 2, the edge-deletion subgraph G−e (which is obtained from G by deleting e) is (`− 1)-connected. 5. Let H be a spanning subgraph of a graph G. Which of the following statements are true? And which of them are false? For a true statement, briefly justify why it is true; for a false statement, give a counterexample to show it is false. (a) If H is Eulerian, then G is Eulerian. (b) If H is Hamiltonian, then G is Hamiltonian. (c) If H is tough, then G is tough. (d) If H is not tough, then G is not tough. 2 6. (a) Let G be the following plane pseudograph. Draw the dual of G. Give the degree of each face of G. (You may need to label the faces of G to facilitate your solution.) e1 e4 e3 e2 e6 e5 e7 e9 e8 Figure 3: Question 6 (b) Let Gn be the simple graph with vertex set {v1, v2, . . . , vn} and edge set {vivj : 1 ≤ i, j ≤ n, 1 ≤ |i− j| ≤ 3}, where n ≥ 3. By induction on n, prove that Gn is a maximal planar graph. 3












































































学霸联盟


essay、essay代写