Adjacency matrix interpretation

Questions requiring drawing a graph from an adjacency matrix or finding indegrees/outdegrees from a digraph matrix.

4 questions · Moderate -0.2

7.02b Graph terminology: tree, simple, connected, simply connected7.02g Eulerian graphs: vertex degrees and traversability
Sort by: Default | Easiest first | Hardest first
OCR Further Discrete AS 2023 June Q4
10 marks Standard +0.3
4 Graph G is a simply connected Eulerian graph with 4 vertices.
    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}
      ABCD
      A0101
      B0020
      C2101
      D0110
      \end{table}
    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.
OCR Further Discrete 2021 November Q2
8 marks Standard +0.3
2 A simply connected semi-Eulerian graph G has 6 vertices and 8 arcs. Two of the vertex degrees are 3 and 4.
    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
    JKLMN
    J01100
    K10100
    L10001
    M00211
    N01010
  3. Write down the indegree and the outdegree of each vertex of H .
    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.
OCR FD1 AS 2017 December Q16
Moderate -0.8
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
AQA Further AS Paper 2 Discrete 2021 June Q5
7 marks Moderate -0.8
An adjacency matrix for the simple graph \(G\) is shown below. \includegraphics{figure_5}
  1. Using the adjacency matrix, explain why \(G\) is not a complete graph. [2 marks]
  2. State, with a reason, whether \(G\) is Eulerian, semi-Eulerian or neither. [2 marks]
  3. Draw a graph that is the complement of \(G\) [3 marks]