MMiDS 5.2: Self-Assessment Quiz

Which of the following is NOT a valid definition of an undirected graph?

• a) A pair \( G = (V, E) \), where \( V \) is the set of vertices and \( E \) is a set of unordered pairs of vertices.
• b) A collection of nodes connected by edges, where the edges have no direction.
• c) A pair \( G = (V, E) \), where \( V \) is the set of vertices and \( E \) is a set of ordered pairs of vertices.
• d) A mathematical structure used to model pairwise relations between objects.

Which of the following statements is TRUE about a path in a graph?

• a) A path must contain all the vertices of the graph.
• b) A path can visit the same vertex multiple times.
• c) A path must be a cycle.
• d) A path cannot have repeated edges.

What is the difference between a tree and a forest in graph theory?

• a) A tree is connected, while a forest is not.
• b) A tree has no cycles, while a forest can have cycles.
• c) A tree is a subgraph of a forest.
• d) A tree is a special type of forest with exactly one connected component.

In a graph, what does the equivalence relation \( \leftrightarrow \) signify?

• a) Two vertices are in the same connected component.
• b) Two vertices have the same degree.
• c) Two vertices are adjacent.
• d) Two vertices are part of a cycle.

In a directed graph, which of the following is true about the edges?

• a) Edges are unordered pairs of vertices
• b) Edges are ordered pairs of vertices
• c) Edges can only go in one direction between any two vertices
• d) Edges cannot form cycles

Consider the following graph:

What is the adjacency matrix of this graph?

• a) \( \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{bmatrix} \)
• b) \( \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \)
• c) \( \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix} \)
• d) \( \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix} \)

What is the Laplacian matrix of the graph in Q5?

• a) \( \begin{bmatrix} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \end{bmatrix} \)
• b) \( \begin{bmatrix} 1 & -1 & -1 \\ -1 & 1 & -1 \\ -1 & -1 & 1 \end{bmatrix} \)
• c) \( \begin{bmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{bmatrix} \)
• d) \( \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix} \)

Which of the following is NOT a property of the Laplacian matrix of a graph?

• a) It is symmetric
• b) It is positive semidefinite
• c) It is always invertible
• d) Its entries sum to zero in each row and column

Which matrix representation of a graph is typically symmetric?

• a) Adjacency matrix of an undirected graph.
• b) Incidence matrix of an undirected graph.
• c) Adjacency matrix of a directed graph.
• d) All of the above.

What characterizes a strongly connected directed graph?

• a) Any two vertices have at least one path connecting them in either direction.
• b) Every vertex has the same in-degree and out-degree.
• c) There are no directed cycles.
• d) The graph can be drawn without any edge crossings.

In a weighted graph, how is the degree of a vertex \( i \) defined?

• a) \( \delta(i) = \sum_{j:\{i,j\}\in E} 1 \)
• b) \( \delta(i) = \sum_{j:\{i,j\}\in E} w_{ij} \)
• c) \( \delta(i) = \sum_{j:(i,j)\in E} 1 \)
• d) \( \delta(i) = \sum_{j:(i,j)\in E} w_{ij} \)