DP Math AI · HL · Geometry and Trigonometry · Updated

AHL 3.15—Adjacency matrices and tables

Get started
Free preview 2/16
  1. Question 1

    A simple undirected graph has 4 vertices with edges –, –, –, –. What is the sum of the entries in row 2 of the adjacency matrix?
    No clue? Show me the answer
    Correct answerCorrect!Incorrect
    A3

    Step-by-step walkthrough

    Choose a solution method

    Method #1Worked solution

    Step 1: Vertex 2's edges

    Vertex 2 is connected to vertices , , and according to the edge list.

    Step 2: Row sum rule

    The sum of row in an adjacency matrix equals the degree of vertex , i.e. the number of edges incident to it.

    Step 3: Count edges at vertex 2

    Vertex 2 has edges to , , and , giving degree .

    Step 4: Conclusion

    The row sum for vertex 2 is .

    Method #2Why the others are wrong

    Step 1: Option A: 2

    This undercounts by missing one of the three edges connected to vertex 2.

    Step 2: Option C: 4

    This overcounts, perhaps by double-counting an edge or including a non-existent self-loop.

    Step 3: Option D: 1

    This only counts one edge, ignoring that vertex 2 has three connections.

    Step 4: Correct count

    Only correctly reflects the three edges –, –, –.

  2. Question 2

    An undirected simple graph has vertices , , with edges – and – only. Which matrix is the correct adjacency matrix (order )?
    No clue? Show me the answer
    Correct answerCorrect!Incorrect
    B

    Step-by-step walkthrough

    Choose a solution method

    Method #1Worked solution

    Step 1: List edges

    The graph has edges – and – only, with no edge between and .

    Step 2: Symmetric entries

    Since the graph is undirected, place in both / and /.

    Step 3: Fill remaining entries

    The and entries are since there's no edge; diagonal is for a simple graph.

    Step 4: Final matrix

    This gives .

    Method #2Why the others are wrong

    Step 1: Option B

    This incorrectly includes an edge between and , which does not exist.

    Step 2: Option C

    This has non-zero diagonal entries, implying self-loops which aren't present in a simple graph.

    Step 3: Option D

    This is not symmetric, treating the graph as directed when it is undirected.

    Step 4: Correct choice

    Option A correctly represents only the two existing edges symmetrically.

Free preview

14 more questions in this topic

Checking your topic access