6. Control questions and tasks / Контрольні запитання і завдання #

Graphs and degree #

1. Define a graph, and the terms adjacent and incident. What makes a graph simple?
2. Define the degree of a vertex. State the handshaking theorem and explain why it holds.
3. Why must the number of vertices of odd degree be even?

Representations #

4. Define the adjacency matrix. Why is it symmetric for an undirected graph? Write it for $V = \{1,2,3\}$, $E = \{(1,2),(2,3)\}$.
5. Define the incidence matrix. How many $1$s are in each column, and why? Write it for $V = \{A,B,C\}$, $E = \{(A,B),(B,C)\}$.

Walks, paths, subgraphs, isomorphism #

6. Distinguish a walk, a trail, a path, and a circuit. Why can the number of walks between two vertices be infinite?
7. When is $H$ a subgraph of $G$? Give the conditions on its vertices and edges.
8. Define graph isomorphism. Name three invariants that isomorphic graphs must share, and explain how they help reject a non-isomorphic pair quickly.

Implementation and complexity #

9. Describe how depth-first search finds a path between two vertices. What is its time complexity in terms of $|V|$ and $|E|$?
10. Why is enumerating all simple paths, or testing isomorphism, expensive in the worst case?

Tasks by hand #

11. For $V = \{1,2,3,4\}$, $E = \{(1,2),(2,3),(3,4),(4,1),(1,3)\}$, compute the degree of every vertex and verify the handshaking theorem.
12. Write the adjacency matrix of the graph in question 11.
13. List two distinct simple paths from vertex $1$ to vertex $4$ in that graph.

Laboratory/Laboratory6/6questions.md · 1.6 KB · updated 2026-07-31 21:14