Graph Representation Quiz (AQA CS A-level)

Which of the following is not a way to represent a graph?

• Adjacency matrix

• Incidence matrix

• Edge list

• Bar chart

Explain the adjacency matrix representation of a graph.

• The adjacency matrix is a 1D array representing the vertices of a graph

• The adjacency matrix is a type of graph that only has one vertex

• The adjacency matrix is a data structure used for storing strings in a graph

• The adjacency matrix representation of a graph is a 2D array where each cell a[i][j] represents the presence of an edge between vertices i and j.

Describe the adjacency list representation of a graph.

• An adjacency list representation of a graph is a tree structure with nodes representing the vertices and edges representing the connections.

• An adjacency list representation of a graph is a single list containing all the vertices in the graph.

• An adjacency list representation of a graph is a collection of lists or arrays, where each list represents a vertex and contains the vertices adjacent to it.

• An adjacency list representation of a graph is a grid of numbers representing the connections between vertices.

What are the advantages of using an adjacency list over an adjacency matrix?

• Adjacency list requires more space for sparse graphs

• Adjacency list requires less space for sparse graphs, allows for efficient iteration through the neighbors of a vertex, and is more efficient for adding or removing edges.

• Adjacency list does not allow for efficient iteration through the neighbors of a vertex

• Adjacency list is less efficient for adding or removing edges

How can a graph be represented using an adjacency matrix?

• By listing all the vertices in the graph along with their corresponding edges.

• By using a matrix to represent the connections between vertices and edges.

• By listing all the edges in the graph without their corresponding vertices.

• By listing all the edges in the graph along with their corresponding vertices.

Oliver, Isabella, and Oscar are working on a project to create a social network for their school. They decide to represent the connections between students using a graph. Can you explain how they would use an incidence matrix to represent this graph?

• The matrix represents the number of edges incident to each vertex.

• Each entry in the matrix is 2 if the vertex is incident to the edge, and 0 otherwise.

• The matrix only contains 1s and 0s with no specific pattern.

• Each entry in the matrix is 1 if the vertex is incident to the edge, and 0 otherwise.

What is a weighted graph and how is it represented?

• Stack or queue

• Adjacency list or adjacency matrix

• Binary tree or AVL tree

• Bar graph or pie chart

Discuss the use of an adjacency matrix in representing a weighted graph.

• It is used to represent the number of vertices in a graph.

• It is used to represent the weights of edges between vertices in a graph.

• It is used to represent the colors of vertices in a graph.

• It is used to represent the names of vertices in a graph.

Explain the concept of a sparse graph and how it affects graph representation.

• It affects graph representation by requiring a less efficient data structure to store the graph.

• A sparse graph has no impact on graph representation.

• A sparse graph has the same number of edges as the maximum possible edges.

• A sparse graph is a graph in which the number of edges is much less than the maximum possible edges. It affects graph representation by requiring a more efficient data structure to store the graph, such as an adjacency list instead of an adjacency matrix.

Compare and contrast the different graph representations in terms of space and time complexity.

• Both representations have different space and time complexities.

• Graph representations do not have any space or time complexities.

• Both representations have the same space and time complexities.

• There is no difference in space and time complexities between the different graph representations.