7.02k Digraphs: directed graphs, indegree and outdegree

3 Traffic flows in and out of a junction of three roads as shown in the diagram. \includegraphics[max width=\textwidth, alt={}, center]{839adc96-1bea-44ef-917e-f03e396a3061-3_296_337_333_863} Assuming that no traffic leaves the junction by the same road as it entered, then the digraph shows traffic flows across the junction. \includegraphics[max width=\textwidth, alt={}, center]{839adc96-1bea-44ef-917e-f03e396a3061-3_362_511_852_776}

1. Redraw the digraph to show that it is planar.
2. Draw a digraph to show the traffic flow across the junction of 4 roads, assuming that no traffic leaves the junction by the same road as it entered. \includegraphics[max width=\textwidth, alt={}, center]{839adc96-1bea-44ef-917e-f03e396a3061-3_366_366_1512_854}
   (Note that the resulting digraph is also planar, but you are not required to show this.)
3. The digraphs showing flows across the junctions omit an important aspect in their modelling of the road junctions. What is it that they omit?

4 Graph G is a simply connected Eulerian graph with 4 vertices.

1. 1. Explain why graph G cannot be a complete graph.
   2. Determine the number of arcs in graph G, explaining your reasoning.
   3. Show that graph G is a bipartite graph. Graph H is a digraph with 4 vertices and no undirected arcs. The adjacency matrix below shows the number of arcs that directly connect each pair of vertices in digraph H . From \begin{table}[h]
      \captionsetup{labelformat=empty} \caption{To}

      	A	B	C	D
      A	0	1	0	1
      B	0	0	2	0
      C	2	1	0	1
      D	0	1	1	0

      \end{table}
2. 1. Write down a feature of the adjacency matrix that shows that H has no loops.
   2. Find the number of \(\operatorname { arcs }\) in H .
   3. Draw a possible digraph H .
   4. Show that digraph H is semi-Eulerian by writing down a suitable trail.

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.

16
27
31 Initially bubble sort is used.

1. Record the list at the end of the first, second and third passes. You do not need to show the individual swaps in each pass. After the fourth pass the list is:
   23
   15
   16
   27
   31
   14
   12
   9
   4 The sorting is then continued using shuttle sort on this list.
2. Record the list at the end of each of the first, second and third passes of shuttle sort. You do not need to show the individual swaps in each pass.
3. How many passes through shuttle sort are needed to complete the sort? Explain your reasoning.
4. A digraph is represented by the adjacency matrix below. $$\begin{gathered} \\ \\ \\ \\ \\ \\ \text { from } \end{gathered} \begin{gathered} \\ \mathrm { A } \\ \mathrm {~B} \\ \mathrm { C } \end{gathered} \quad \quad \left( \begin{array} { c c c } 1 & \mathrm {~B} & \mathrm { C } \\ 1 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & 0 \end{array} \right)$$
   1. For each vertex, write down
      • the indegree,
      • the outdegree.
      • Explain how the indegrees and outdegrees show that the digraph is semi-Eulerian.
      • A graph is represented by the adjacency matrix below.
      $$\left. \begin{array} { c } \\ \mathrm { D } \\ \mathrm { E } \\ \mathrm {~F} \end{array} \quad \begin{array} { c c c } \mathrm { D } & \mathrm { E } & \mathrm {~F} \\ 2 & 1 & 0 \\ 1 & 0 & 2 \\ 0 & 2 & 0 \end{array} \right)$$ (a) Explain how the numerical entries in the matrix show that this can be drawn as an undirected graph.
      (b) Explain how the adjacency matrix shows that this graph is semi-Eulerian.
   2. By referring to the vertex degrees, explain why the loop from A to itself is shown as a 1 in the adjacency matrix in part (i) but the loop from \(D\) to itself is shown as 2 in the adjacency matrix in part (ii).
      1. List the 15 partitions of the set \(\{ \mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } \}\). Amy, Bao, Cal and Dana want to travel by taxi from a meeting to the railway station. They book taxis but only two taxis turn up. Each taxi must have a minimum of one passenger and can carry a maximum of four passengers. Dana jumps into one of the taxis.
      2. Find the number of ways that Amy, Bao and Cal can be split between the two taxis. Amy does not want to travel in the same taxi as Bao.
      3. Determine the number of ways that Amy, Bao and Cal can be split between taxis with this additional restriction. Six people want to travel by taxi from a hotel to the railway station using taxis. There must be a minimum of one passenger and a maximum of four passengers in each taxi. The taxis may be regarded as being indistinguishable.
      4. Calculate how many ways there are of splitting the six people between taxis. \section*{END OF QUESTION PAPER} \section*{OCR} Oxford Cambridge and RSA

1 The adjacency graph for a map has a vertex for each country. Two vertices are connected by an arc if the corresponding countries share a border.

1. Draw the adjacency graph for the following map of four countries. The graph is planar and you should draw it with no arcs crossing. \includegraphics[max width=\textwidth, alt={}, center]{e528b905-7419-44b6-b700-4c04ad96c816-2_531_1486_561_292}
2. Number the regions of your planar graph, including the outside region. Regarding the graph as a map, draw its adjacency graph.
3. Repeat parts (i) and (ii) for the following map. \includegraphics[max width=\textwidth, alt={}, center]{e528b905-7419-44b6-b700-4c04ad96c816-2_533_1484_1361_294}

6 A garden has seven statues \(A , B , C , D , E , F\) and \(G\), with paths connecting each pair of statues, either directly or indirectly. To provide better access to all the statues, some of the paths are being made wider.
6

1. State why six is the minimum number of paths that need to be made wider. 6
2. The table below shows the number of trees that need to be removed to make the path between adjacent statues wider. A dash in the table means that there is no direct path between the two statues.

   Statue	\(\boldsymbol { A }\)	\(\boldsymbol { B }\)	C	\(\boldsymbol { D }\)	\(E\)	\(F\)	\(G\)
   \(\boldsymbol { A }\)	-	4	7	-	-	-	-
   B	4	-	6	2	3	-	-
   C	7	6	-	-	3	-	4
   \(D\)	-	2	-	-	4	5	-
   \(E\)	-	3	3	4	-	3	7
   \(F\)	-	-	-	5	3	-	6
   G	-	-	4	-	7	6	-

   Find the minimum number of trees that need to be removed. Fully justify your answer.
   6
3. A landscaper identifies that two new wide paths could be constructed without removing any trees. However, there are only enough resources to build one new wide path. The new wide path could be between \(A\) and \(D\) or between \(A\) and \(F\).
   Explain clearly how the solution to part (b) can be adapted to find the new minimum number of trees that need to be removed.
   [0pt] [2 marks]