1. Objective / Мета роботи
Understand the basic notions of graph theory and implement the core operations on graphs — degrees, matrix representations, paths, and graph comparison.
By the end of the work the student should be able to:
- represent an undirected graph by its vertices and edges, and compute the degree of each vertex;
- verify the handshaking theorem — the sum of all degrees equals twice the number of edges;
- build the adjacency matrix and the incidence matrix of a graph;
- find a path between two vertices, and discover a circuit (closed trail);
- distinguish walks, trails, and paths, and enumerate them between two vertices;
- test whether one graph is a subgraph of another, and whether two graphs are isomorphic;
- reason about the time complexity of these operations.
The work establishes the vocabulary and representations of graph theory that the rest of the course — traversal, shortest paths, trees, and colourings — builds on.