7.02q Adjacency matrix: and weighted matrix representation

1

1. Draw a bipartite graph to represent the following adjacency matrix.

   	1	2	3	4	5
   A	0	0	0	0	1
   \(\boldsymbol { B }\)	0	0	0	1	1
   \(\boldsymbol { C }\)	0	1	0	1	1
   \(\boldsymbol { D }\)	0	0	0	1	1
   \(\boldsymbol { E }\)	1	1	1	0	1

2. If \(A , B , C , D\) and \(E\) represent five people and 1, 2, 3, 4 and 5 represent five tasks to which they are to be assigned, explain why a complete matching is impossible.
   (2 marks)

1 Six people, \(A , B , C , D , E\) and \(F\), are to be matched to six tasks, \(1,2,3,4,5\) and 6 .
The following adjacency matrix shows the possible matching of people to tasks.

1. Show this information on a bipartite graph.
2. Initially, \(A\) is matched to task 3, \(B\) to task 4, \(C\) to task 2 and \(E\) to task 5. From this initial matching, use the maximum matching algorithm to obtain a complete matching. List your complete matching.

1

1. Draw a bipartite graph representing the following adjacency matrix.

   	1	2	3	4	5	6
   \(\boldsymbol { A }\)	1	0	1	0	1	0
   B	0	1	0	1	0	0
   \(\boldsymbol { C }\)	0	1	0	0	0	1
   \(\boldsymbol { D }\)	0	0	0	1	0	0
   E	0	0	1	0	1	1
   \(\boldsymbol { F }\)	0	0	0	1	1	0

2. Initially, \(A\) is matched to \(3 , B\) is matched to \(4 , C\) is matched to 2 , and \(E\) is matched to 5 . Use the maximum matching algorithm, from this initial matching, to find a complete matching. List your complete matching.
   

1 Six people, \(A , B , C , D , E\) and \(F\), are to be allocated to six tasks, 1, 2, 3, 4, 5 and 6. The following adjacency matrix shows the tasks that each of the people is able to undertake.

1. Represent this information in a bipartite graph.
2. Initially, \(A\) is assigned to task 3, \(B\) to task 2, \(C\) to task 4 and \(D\) to task 5 . Use an algorithm from this initial matching to find a maximum matching, listing your alternating paths.

1 [Answer this question on the insert provided.]
The network below represents a system of pipelines through which fluid flows from \(S\) to \(T\). The capacities of the pipelines, in litres per second, are shown as weights on the arcs. \includegraphics[max width=\textwidth, alt={}, center]{0403a37e-46dd-4346-afc6-e48a34417c48-2_863_1201_486_477}

1. Write down the arcs from \(\{ S , A , C , E \}\) to \(\{ B , D , F , T \}\). Hence find the capacity of the cut that separates \(\{ S , A , C , E \}\) from \(\{ B , D , F , T \}\).
2. On the diagram in the insert show the excess capacities and potential backflows when 5 litres per second flow along SADT and 6 litres per second flow along SCFT.
3. Give a flow-augmenting path of capacity 2 . On the second diagram in the insert show the new capacities and potential backflows.
4. Use the maximum flow - minimum cut theorem to show that the maximum flow from \(S\) to \(T\) is 13 litres per second.
5. \(E B\) is replaced by a pipeline with capacity 2 litres per second from \(B\) to \(E\). Find the new maximum flow from \(S\) to \(T\). You should show the flow on the third diagram in the insert and explain how you know that this is a maximum.

4 The network represents a system of pipes through which fluid can flow from a source, \(S\), to a sink, \(T\). The weights on the arcs represent pipe capacities in gallons per minute. \includegraphics[max width=\textwidth, alt={}, center]{9057da95-c53a-416c-8340-c94aff366385-6_599_1580_402_280}

1. Calculate the capacity of the cut that separates \(\{ S , A , C , D \}\) from \(\{ B , E , F , T \}\).
2. Explain why the arcs \(A C\) and \(A D\) cannot both be full to capacity and why the arcs \(D F\) and \(E F\) cannot both be full to capacity.
3. Draw a diagram to show a flow in which as much as possible flows through vertex \(E\) but none flows through vertex \(A\) and none flows through vertex \(D\). State the maximum flow through vertex \(E\). An engineer wants to find a flow augmenting route to improve the flow from part (iii).
4. (a) Explain why there can be no flow augmenting route that passes through vertex \(A\) but not through vertex \(D\).
   (b) Write down a flow augmenting route that passes through vertex \(D\) but not through vertex \(A\). State the maximum by which the flow can be augmented.
5. Prove that the augmented flow in part (iv)(b) is the maximum flow.
6. A vertex restriction means that the flow through \(E\) can no longer be at its maximum rate. By how much can the flow through \(E\) be reduced without reducing the maximum flow from \(S\) to \(T\) ? Explain your reasoning. The pipe represented by the arc \(B E\) becomes blocked and cannot be used.
7. Draw a diagram to show that, even when the flow through \(E\) is reduced as in part (vi), the same maximum flow from \(S\) to \(T\) is still possible.

5 The network represents a simplified map of a town centre. On certain days, large numbers of visitors need to travel through the town centre, from \(S\) to \(T\). The arcs represent roads and the weights show the maximum number of visitors per hour who can use each road. To find the maximum rate at which visitors can travel through the town centre without any of them being delayed, the problem is modelled as a maximum flow problem. \includegraphics[max width=\textwidth, alt={}, center]{76486ad4-c00e-4e0b-9527-6f13f9222dbb-6_837_1317_523_413}

1. Calculate the capacity of the cut that separates \(\{ S , A , C , G \}\) from \(\{ B , D , E , F , T \}\).
2. Explain why neither arc \(S A\) nor arc \(E T\) can be full to capacity. Also explain why the arcs \(A C\) and \(B C\) cannot simultaneously be full to capacity.
3. Show a flow of 3300 people per hour, and find a cut of capacity 3300 . The direction of flow in \(B C\) is reversed.
4. Show the excess capacities and potential backflows when there is no flow.
5. Without obscuring your answer to part (iv), augment the labels to show a flow of 2000 people per hour along \(S B E T\).
6. Write down further flow augmenting routes and augment the labels, without obscuring your previous answers, to find the maximum flow from \(S\) to \(T\).
7. Show the maximum flow and explain how you know that this flow is maximal.

5 The network represents a system of pipes through which fluid can flow. The weights on the arcs show the lower and upper capacities for the pipes, in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{661c776a-9c9f-485f-b0fd-f58651e3e065-6_577_1182_351_443}

1. Identify the source and explain how you know that the sink is at \(G\).
2. Calculate the capacity of the cut that separates \(\{ A , B , C , D , E , F \}\) from \(\{ G , H , I , J , K , L \}\).
3. Assuming that a feasible flow exists, explain why arc \(J G\) must be at its lower capacity. Write down the flows in arcs \(H K\) and \(I L\).
4. Assuming that a feasible flow exists, explain why arc HI must be at its upper capacity. Write down the flows in arcs \(E H\) and \(C B\).
5. Show a flow of 10 litres per second through the system.
6. Using your flows from part (v), label the arrows on the diagram to show the excess capacities and the potential backflows.
7. Write down a flow augmenting path from your diagram in part (vi), but do not update the excess capacities and the potential backflows. Hence show a maximum flow through the system, and state how you know that the flow is maximal.

2 A simply connected semi-Eulerian graph G has 6 vertices and 8 arcs. Two of the vertex degrees are 3 and 4.

1. 1. Determine the minimum possible vertex degree.
   2. Determine the maximum possible vertex degree.
2. Write down the two possible degree sequences (ordered lists of vertex degrees). The adjacency matrix for a digraph H is given below.

   \multirow{7}{*}{From}	\multirow{2}{*}{}	To
   		J	K	L	M	N
   	J	0	1	1	0	0
   	K	1	0	1	0	0
   	L	1	0	0	0	1
   	M	0	0	2	1	1
   	N	0	1	0	1	0

3. Write down the indegree and the outdegree of each vertex of H .
4. 1. Use the indegrees and outdegrees to determine whether graph H is Eulerian.
   2. Use the adjacency matrix to determine whether graph H is simply connected.

5. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 3 shows the possible allocations of six people, Amelia, Charlie, Ellie, Gemma, Jimmy and Saskia, to six tasks, 1, 2, 3, 4, 5 and 6.
Figure 4 shows an initial matching.

1. Use the maximum matching algorithm once to find an improved matching. You must state the alternating path used and your improved matching.
2. Explain why a complete matching is not possible. After training, Jimmy can be assigned to tasks 4 or 5 and Ellie to tasks 2, 3, 5 or 6.
3. Starting with your current maximal matching, use the maximum matching algorithm to obtain a complete matching. You must state the alternating path used and your final matching.

6. (a) Define the term 'cut' as it applies to a directed network.
(2) \begin{figure}[h] \end{figure} Figure 6 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.
(b) Complete the labelling procedure on Diagram 2 in your answer book by entering values along CE, EG, HT and GT.
(c) Find the maximum flow through the network. You must list each flow-augmenting route you use together with its flow.
(d) Show a maximal flow pattern on Diagram 3 in your answer book.
(e) State the value of the maximum flow through the network.
(f) Prove that your flow is maximal.

4. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six people, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , to six tasks, 1, 2, 3, 4, 5 and 6.
Figure 2 shows an initial matching.

1. Starting from this initial matching, use the maximum matching algorithm to find an improved matching. You must list the alternating path used, and your improved matching.
2. Explain why it is not possible to find a complete matching. D now has task 2 added to their possible allocation.
3. Using the improved matching found in part (a) as the new initial matching, use the maximum matching algorithm to find a complete matching. You must list the alternating path used and your complete matching.
   (3)

1. \begin{figure}[h] \end{figure} Figure 1 shows the possible allocation of six people, Alice (A), Brian (B), Christine (C), David (D), Elizabeth (E) and Freddy (F), to six tasks, 1, 2, 3, 4, 5 and 6. An initial matching is Alice to task 1, Christine to task 3, David to task 4 and Elizabeth to task 5.

1. Show this initial matching on Diagram 1 in the answer book.
   (1)
2. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. List clearly the alternating paths that you use, and give your final matching.
   (5)

5 Consider the problem given below: $$\begin{array} { l l } \text { Minimise } & 4 \mathrm { AB } + 7 \mathrm { AC } + 8 \mathrm { BD } + 5 \mathrm { CD } + 5 \mathrm { CE } + 6 \mathrm { DF } + 3 \mathrm { EF } \\ \text { subject to } & \mathrm { AB } , \mathrm { AC } , \mathrm { BD } , \mathrm { CD } , \mathrm { CE } , \mathrm { DF } \text { and } \mathrm { EF } \text { are each either } 0 \text { or } 1 \\ & \mathrm { AB } + \mathrm { AC } + \mathrm { BD } + \mathrm { CD } + \mathrm { CE } + \mathrm { DF } + \mathrm { EF } = 5 \\ & \mathrm { AB } + \mathrm { AC } \geqslant 1 , \quad \mathrm { AB } + \mathrm { BD } \geqslant 1 , \quad \mathrm { AC } + \mathrm { CD } + \mathrm { CE } \geqslant 1 , \\ & \mathrm { BD } + \mathrm { CD } + \mathrm { DF } \geqslant 1 , \quad \mathrm { CE } + \mathrm { EF } \geqslant 1 , \quad \mathrm { DF } + \mathrm { EF } \geqslant 1 \end{array}$$

1. Explain why this is not a standard LP formulation that could be set up as a Simplex tabulation. The variables \(\mathrm { AB } , \mathrm { AC } , \ldots\) correspond to arcs in a network. The weight on each arc is the coefficient of the corresponding variable in the objective function.
2. Draw the network on the vertices in the Printed Answer Booklet. A variable that takes the value 1 corresponds to an arc that is used in the solution and a variable with the value 0 corresponds to an arc that is not used in the solution.
3. Explain what is ensured by the constraint \(\mathrm { AB } + \mathrm { AC } \geqslant 1\). Julie claims that the solution to the problem will give the minimum spanning tree for the network.
4. Find the minimum spanning tree for the network.
   • State the algorithm you have used.
   • Show your method clearly.
   • Draw the tree.
   • State the total weight of the tree.
   • Find the solution to the problem given at the start of the question.
   • You do not need to use a formal method.
   • Draw the arcs in the solution.
   • State the minimum value of the objective function.
   Kim has a different network, exactly one of the arcs in this network is a directed arc.
   Kim wants to find a minimum weight set of arcs such that it is possible to get from any vertex to any other vertex.
5. Explain why, if Kim's problem has a solution, the directed arc cannot be part of it.

3. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six workers, Charlotte (C), Eleanor (E), Harry (H), Matt (M), Rachel (R) and Simon (S) to six tasks, 1, 2, 3, 4, 5 and 6. Figure 2 shows an initial matching.

1. List an alternating path, starting at H and ending at 4 . Use your path to find an improved matching. List your improved matching.
2. Explain why it is not possible to find a complete matching. Simon (S) now has task 3 added to his possible allocation.
3. Taking the improved matching found in (a) as the new initial matching, use the maximum matching algorithm to find a complete matching. List clearly the alternating path you use and your complete matching.
   (3)

1

1. Draw a bipartite graph representing the following adjacency matrix.
   (2 marks)

   	\(\boldsymbol { U }\)	\(V\)	\(\boldsymbol { W }\)	\(\boldsymbol { X }\)	\(\boldsymbol { Y }\)	\(\boldsymbol { Z }\)
   \(\boldsymbol { A }\)	1	0	1	0	1	0
   \(\boldsymbol { B }\)	0	1	0	1	0	0
   \(\boldsymbol { C }\)	0	1	0	0	0	1
   \(\boldsymbol { D }\)	0	0	0	1	0	0
   \(\boldsymbol { E }\)	0	0	1	0	1	1
   \(\boldsymbol { F }\)	0	0	0	1	1	0

2. Given that initially \(A\) is matched to \(W , B\) is matched to \(X , C\) is matched to \(V\), and \(E\) is matched to \(Y\), use the alternating path algorithm, from this initial matching, to find a complete matching. List your complete matching.

2 Five people \(A , B , C , D\) and \(E\) are to be matched to five tasks \(R , S , T , U\) and \(V\).
The table shows the tasks that each person is able to undertake.

1. Show this information on a bipartite graph.
2. Initially, \(A\) is matched to task \(V , B\) to task \(R , C\) to task \(T\), and \(E\) to task \(U\). Demonstrate, by using an alternating path from this initial matching, how each person can be matched to a task.

1 Five people, \(A , B , C , D\) and \(E\), are to be matched to five tasks, \(J , K , L , M\) and \(N\). The table shows the tasks that each person is able to undertake.

1. Show this information on a bipartite graph.
2. Initially, \(A\) is matched to task \(N , B\) to task \(J , C\) to task \(L\), and \(E\) to task \(M\). Complete the alternating path \(D - M \ldots\), from this initial matching, to demonstrate how each person can be matched to a task.
   (3 marks)

4 The connected planar graph \(P\) has the adjacency matrix 4

1. Draw \(P\) 4
2. Using Euler's formula for connected planar graphs, show that \(P\) has exactly 5 faces. 4
3. Ore's theorem states that a simple graph with \(n\) vertices is Hamiltonian if, for every pair of vertices \(X\) and \(Y\) which are not adjacent, $$\text { degree of } X + \text { degree of } Y \geq n$$ where \(n \geq 3\) Using Ore's theorem, prove that the graph \(P\) is Hamiltonian.
   Fully justify your answer.

\includegraphics{figure_1} A taxi firm has six taxis \(A\), \(B\), \(C\), \(D\), \(E\) and \(F\), available for six journeys, 1, 2, 3, 4, 5 and 6, which are booked for 9 a.m. tomorrow. The bipartite graph shown in Figure 1 shows the possible matchings. Initially \(A\), \(B\), \(C\) and \(D\) are matched to 5, 2, 3 and 6 respectively, as indicated in Figure 2.

1. Explain why it is necessary to perform the maximum matching algorithm twice in order to try to obtain a complete matching. [1]
2. Use the maximum matching algorithm twice to obtain a complete matching. List clearly the alternating paths you use. [6]

\includegraphics{figure_1} \includegraphics{figure_2} Figure 1 shows the possible allocations of five people, Ellen, George, Jo, Lydia and Yi Wen to five tasks, 1, 2, 3, 4 and 5. Figure 2 shows an initial matching.

1. Find an alternating path linking George with 5. List the resulting improved matching this gives. (3)
2. Explain why it is not possible to find a complete matching. (1)

George now has task 2 added to his possible allocation.

1. Using the improved matching found in part (a) as the new initial matching, find an alternating path linking Yi Wen with task 1 to find a complete matching. List the complete matching. (3)

(Total 7 marks)

Six workers \(A\), \(B\), \(C\), \(D\), \(E\) and \(F\) are to be matched to six tasks 1, 2, 3, 4, 5 and 6. The table below shows the tasks that each worker is able to do.

Worker	Tasks
A	2, 3, 5
B	1, 3, 4, 5
C	2
D	3, 6
E	2, 4, 5
F	1

A bipartite graph showing this information is drawn in the answer booklet. Initially, \(A\), \(B\), \(D\) and \(E\) are allocated to tasks 2, 1, 3 and 5 respectively. Starting from the given initial matching, use the matching improvement algorithm to find a complete matching, showing your alternating paths clearly. [5]

Six people, \(A\), \(B\), \(C\), \(D\), \(E\) and \(F\), are to be allocated to six tasks, 1, 2, 3, 4, 5 and 6. The following bipartite graph shows the tasks that each of the people is able to undertake. \includegraphics{figure_1}

1. Represent this information in an adjacency matrix. [2]
2. Initially, \(B\) is assigned to task 5, \(D\) to task 2, \(E\) to task 4 and \(F\) to task 3. Demonstrate, by using an algorithm from this initial matching, how each person can be allocated to a task. [5]

A planar graph \(G\) is described by the adjacency matrix below. $$\begin{pmatrix} 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}$$

1. Draw the graph \(G\). [1]
2. Use Euler's formula to verify that there are four regions. Identify each region by listing the vertices that define it. [3]
3. Explain why graph \(G\) cannot have a Hamiltonian cycle that includes the edge \(AB\). Deduce how many Hamiltonian cycles graph \(G\) has. [4]

A colouring algorithm is given below. STEP 1: Choose a vertex, colour this vertex using colour 1. STEP 2: If all vertices are coloured, STOP. Otherwise use colour 2 to colour all uncoloured vertices for which there is an edge that joins that vertex to a vertex of colour 1. STEP 3: If all vertices are coloured, STOP. Otherwise use colour 1 to colour all uncoloured vertices for which there is an edge that joins that vertex to a vertex of colour 2. STEP 4: Go back to STEP 2.

1. Apply this algorithm to graph \(G\), starting at \(E\). Explain how the colouring shows you that graph \(G\) is not bipartite. [2]

By removing just one edge from graph \(G\) it is possible to make a bipartite graph.

1. Identify which edge needs to be removed and write down the two sets of vertices that form the bipartite graph. [2]

Graph \(G\) is augmented by the addition of a vertex \(X\) joined to each of \(A\), \(B\), \(C\), \(D\), \(E\) and \(F\).

1. Apply Kuratowski's theorem to a contraction of the augmented graph to explain how you know that the augmented graph has thickness 2. [4]