Graphs study guide

1. Start with the model

When given a scenario, identify what the objects are and what relationships connect them. The objects become vertices or nodes, while the relationships become edges or arcs. State this explicitly. For example, in a road-map model, locations can be vertices and roads can be edges. If the question instead describes one-way travel, the edges should be directed because the connection has a specified direction.

Do not choose a graph type from the nouns alone. Examine the relationship. If a connection is intended to work in both directions, use an undirected graph. If the connection from one vertex to another is different from the reverse connection, use a directed graph. If a value such as a distance, time or cost is attached to a connection, explain that the graph is weighted and that the value is stored with the edge.

2. Reason about direction

For an undirected graph, a connection between A and B represents the relationship in both directions. In an adjacency matrix, the entries for the A-to-B and B-to-A positions represent the same undirected connection. In an adjacency list, A appears in B's neighbouring connections and B appears in A's neighbouring connections.

For a directed graph, an edge from A to B only represents movement or association from A to B. The reverse edge must be represented separately if it exists. Therefore, an adjacency matrix can have different information at row A, column B and row B, column A. An adjacency list records the destination of each outgoing edge for the relevant source vertex.

3. Compare the representations rather than merely defining them

An adjacency matrix is a two-dimensional representation indexed by a source vertex and a destination vertex. It provides a location for every possible pair, so it is useful when the required reasoning concerns whether a particular pair has a connection or what value that connection has. Its table also makes the distinction between directed and undirected relationships visible through the relevant row-column positions.

An adjacency list groups information by vertex. It is useful when the reasoning concerns the neighbours or outgoing connections of one chosen vertex. It records the actual connections in each list rather than presenting a separate table position for every possible pair. The trade-off is that finding a particular connection may involve examining the appropriate list.

A strong comparison should mention both the structure and the consequence. For example: an adjacency matrix stores graph information in a row-and-column table, including positions for pairs with no edge; an adjacency list stores each vertex's connected vertices, so it focuses on recorded connections but may require a search within a list for a specific pair.

4. Worked reasoning approach

For any graph question, use this sequence:

1. Name the vertices and explain what each represents.
2. Name the edges and explain what each relationship represents.
3. Decide whether the graph is directed, undirected, weighted or a combination.
4. If weighted, identify what each edge value means.
5. Select an adjacency matrix or adjacency list.
6. Explain how one example connection would appear in that representation.
7. Justify the choice in relation to the information that must be inspected.

For example, suppose vertices represent locations and an edge value represents distance. If travel is possible in both directions, describe an undirected weighted graph. In a matrix, the row and column for each location identify a distance entry for a connected pair. In a list, each location has neighbouring locations together with their distances. If the travel is one-way, describe a directed weighted graph instead and do not assume that the reverse distance or reverse edge exists.

5. Self-check questions

• Can you define graph, vertex, node, edge and arc accurately?
• Can you distinguish a directed graph from an undirected graph using the meaning of an edge?
• Can you explain why a graph with distances on its connections is weighted?
• Can you describe what rows and columns represent in an adjacency matrix?
• Can you describe what is stored for each vertex in an adjacency list?
• Can you explain why the two directions of a directed connection must be considered separately?
• Can you compare the representations using a specific operation rather than saying only that one is a table and one is a list?

In an exam answer, avoid isolated definitions when the question gives a scenario. Link each term to the scenario and explain how the chosen representation records the relationships.