闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MTH3170 (3175) Network Mathematics (Advanced)

Assignment 2

1. (a) Prove that every graph G with n vertices and minimum degree 6(G) > is connected. [15 marks]

(b) Show that this result is best possible by ﬁnding, for every even integer n > 2, a discon- nected graph G on n vertices with minimum degree 6(G) = .

[5 marks]

2. For a tree T and positive integer k, let G(T, k) be the graph obtained from T by adding an edge vw whenever distT (v, w) ≤ k.

(a) Find a tree T with maximum degree 3, such that G(T, 2) is not 3-colourable.

[5 marks]

(b) Prove that G(T, 2) is 4-colourable, for every tree T with maximum degree 3.

[5 marks]

(d) Prove that G(T, 3) is 6-colourable, for every tree T with maximum degree 3.

[5 marks]

3. Which of the following graphs are planar? Explain your answer in full.

[20 marks]

(a)

(b)

4. A matching M in a graph G is maximal if M ∪{e} is not a matching for each edge e ∈ E(G)\M. Let Q be the 4-dimensional hypercube.

0111

1101

0101

0110

0011

0100

1010

0000

(a) Draw a maximal matching M in Q with exactly 6 edges.

[5 marks]

(b) Draw the flow network N associated with Q, and show the flow in N associated with M.

[5 marks]

(b), to compute a maximum flow in N. For each augmenting semi-path in N found by the algorithm, state the corresponding augmenting path with respect to the current matching. What is the value of a maximum flflow? What is a minimum cut?

[5 marks]

(d) Using the maximum flow in N found in part (c), determine a maximum matching in Q and draw it.

[5 marks]

5. (MTH3170 only)

Apply the algorithm presented in lectures to determine shortest paths from vertex r to every other vertex in the following edge-weighted graph. Show all steps.

[20 marks]

6. (MTH3175 only)

Let G be the intersection graph of a set of closed intervals in the real line. That is, V (G) = nX1 , . . . , Xn } where Xi = [Xi , ri] and XiXj e E(G) if and only if Xi ∩ Xj 0 and i j . Here [Xi , ri] is the closed interval nx e R : Xi ≤ x ≤ ri }. The following example shows the graph and the corresponding set of intervals.

(a) Prove that the chromatic number of such a graph G equals its clique number.

[10 marks]

(b) Let T be a tree and let T1 , . . . , Tn be subtrees of T. Let G be the intersection graph of T1 , . . . , Tn . That is, V (G) = nT1 , . . . , Tn } where TiTj e E(G) if and only if Ti ∩ Tj 0 and i j .