Chris Hanusa Nov 14, 2003 Math 381 – Homework 6 Answer Key

Question 1 – Consider the following transhipment-problem: A, B, C, D, E are the depots their supply is in the same order: 1/2, 1/3, 1/2, 1/3. The shops are U, T, V, X, Y, Z, and their demand is 1/3 (for each of them). The adjacency-matrix of the shipment-graph is below:

\begin{matrix}+ & U & T & V & X & Y & Z \\ A & 1 & 1 & 1 & 0 & 0 & 0 \\ B & 1 & 0 & 1 & 1 & 0 & 1 \\ C & 1 & 1 & 0 & 0 & 1 & 0 \\ D & 1 & 0 & 0 & 0 & 1 & 0 \\ E & 0 & 1 & 1 & 0 & 0 & 1 \end{matrix}

Find a transhipment which this setting admits, or find a cut which shows the problematic demands.

Answer [10 points] – Draw a graph of the adjacency matrix, and we get some intuition about how to proceed. X is only serviced by B, so all of its cargo must go along that route. Then V is only serviced by A, so A must send 1/3 to V, and it then has 1/6 left, which it can send to T, and similarly C can send 1/6 to T and 1/3 to Y, while D sends 1/3 to U, and E sends 1/3 to Z. The transhipment is: A → V: 1/3 A → T: 1/6 B → X: 1/3 C → Y: 1/3 C → T: 1/6 D → U: 1/3 E → Z: 1/3

All the demand is met, so this is a valid transhipment.

Question 2 – Consider the following bipartite graph, given by the adjacency matrix below:

\begin{matrix}+ & U & T & V & X & Y & Z \\ A & 0 & 1 & 0 & 1 & 0 & 0 \\ B & 1 & 1 & 0 & 1 & 0 & 1 \\ C & 0 & 1 & 1 & 0 & 0 & 0 \\ D & 1 & 0 & 1 & 1 & 0 & 1 \\ E & 0 & 0 & 1 & 0 & 1 & 1 \\ F & 0 & 0 & 1 & 0 & 1 & 0 \end{matrix}

Find a max matching in the given graph, using the flow technic learned in class. Give the min cut proving the maximality of your matching.

Answer [10 points] – To set this problem up as a network flow problem, we create a super source s and a super sink t, connecting s to each vertex A − F and connecting U − Z to t, each with capacity one. Then we connect A − F to U − Z using the adjacency data in the given matrix, and let those edges have capacity 1. Now we solve the network flow problem using methods from last homework. A possible solution is A − T, B − U, V − C, D − X, E − Z and F − Y.

Question 3 – Consider the Petersen graph. Paint one of its edges to red, all other edges are black. Find all different perfect matchings containing this red edge.

Answer [10 points] – Remember that the Petersen graph is extremely symmetric so it doesn’t matter which edge is chosen. Let’s pick an edge from the outer ring of vertices to the inner ring of vertices and label it red. Choosing this edge means its four adjacent edges can not be included in a matching, because each vertex has to have degree one. Remove these four edges. Choose an edge that is at a vertex that now has degree 2. Either this edge is in the matching or it is not. If you put it in the matching, you will see it forces three other edges to be included in its matching. If you do not put it in the matching, you can again use process of elimination to force four other edges into the matching. But in either case, you have no choice on which edges are included. Therefore in the unlabeled Petersen graph, there are only two matchings that contain the edge we’ve labeled red.

Question 4 – How many Hamiltonian cycles does the Petersen graph have?

Answer [10 points] – You can prove there are no Hamiltonian cycles in P using the process of elimination like problem 3, but here’s a slick proof. Assume there is a Hamiltonian cycle H in P. Since P is 3-regular, and any cycle is 2-regular, the complement of H in P is 1-regular. But a one regular graph is a perfect matching. In problem 3, we find all perfect matchings in P. But in each case, the complement of M is not a Hamiltonian cycle, so it could not have existed in the first place. Therefore there are no Hamiltonian cycles in P.