# 2. Methodical guidelines / Методичні вказівки

This section is **self-contained**: it develops the theory of the work's theme —
the basics of graph theory — together with algorithms for the tasks in
[4task.md](4task.md). No outside material is required.

## 2.1 Graphs

An (undirected) **graph** is a pair $G = (V, E)$ where $V$ is a set of
**vertices** and $E$ is a set of **edges**, each edge an unordered pair
$\{u, v\}$ of distinct vertices. Two vertices joined by an edge are **adjacent**;
an edge and each of its endpoints are **incident**. We assume **simple** graphs:
no loops and no repeated edges.

## 2.2 Degree and the handshaking theorem

The **degree** $\deg(v)$ of a vertex is the number of edges incident to it.
Because each edge contributes to the degree of exactly two vertices, summing all
degrees counts every edge twice — the **handshaking theorem**:

$$\sum_{v \in V} \deg(v) = 2\,|E|.$$

For the 4-cycle on $\{1,2,3,4\}$ with edges $(1,2),(2,3),(3,4),(4,1)$, every
vertex has degree $2$, so the sum is $8 = 2 \cdot 4$. A corollary: the number of
vertices of odd degree is always even.

![A sample graph illustrating the handshaking theorem: its six edges make the vertex degrees sum to 12 = 2·6 = 2|E|](img/handshaking.png)

## 2.3 Matrix representations

Fix an ordering of the $n$ vertices (and, for incidence, the $m$ edges).

The **adjacency matrix** $A$ is $n \times n$ with $A[i][j] = 1$ when vertices
$i, j$ are adjacent and $0$ otherwise. For an undirected graph it is symmetric.
For $V = \{1,2,3\}$, $E = \{(1,2),(2,3)\}$:

```text
      1  2  3
  1 [ 0  1  0 ]
  2 [ 1  0  1 ]
  3 [ 0  1  0 ]
```

![A sample symmetric adjacency matrix (five-vertex graph): a 1 wherever two vertices are adjacent](img/adj_matrix.png)

The **incidence matrix** $M$ is $n \times m$ (vertices $\times$ edges) with
$M[v][e] = 1$ when vertex $v$ is an endpoint of edge $e$. For $V = \{A,B,C\}$,
$E = \{e_1 = (A,B),\ e_2 = (B,C)\}$:

```text
       e1 e2
  A [  1  0 ]
  B [  1  1 ]
  C [  0  1 ]
```

Each column of an incidence matrix has exactly two $1$s (its edge's endpoints).

## 2.4 Walks, trails, paths, and circuits

A **walk** is an alternating sequence of vertices and edges
$v_0, e_1, v_1, \dots, e_k, v_k$ where each $e_i = \{v_{i-1}, v_i\}$. Refinements:

- a **trail** is a walk with **no repeated edge**;
- a **path** is a walk with **no repeated vertex** (hence no repeated edge);
- a **circuit** (closed trail) is a trail with $v_0 = v_k$; a **cycle** is a path
  that returns to its start.

The number of *walks* between two vertices is generally **infinite** (edges may be
reused), so in practice one enumerates **trails** or **simple paths**, which are
finite. For $E = \{(1,2),(2,3),(3,4),(4,1)\}$, the sequence $1 \to 2 \to 3 \to 4$
is a path, and $A \to B \to C \to D \to A$ (on the analogous 4-cycle) is a
circuit.

## 2.5 Subgraphs and isomorphism

$H = (V', E')$ is a **subgraph** of $G = (V, E)$ if $V' \subseteq V$,
$E' \subseteq E$, and every edge of $E'$ joins two vertices of $V'$.

Two graphs $G_1, G_2$ are **isomorphic** if there is a bijection
$f : V_1 \to V_2$ that preserves adjacency: $\{u,v\} \in E_1 \iff
\{f(u), f(v)\} \in E_2$. Isomorphic graphs must agree on all **invariants** —
the number of vertices, the number of edges, and the sorted **degree sequence** —
so checking those first quickly rejects most non-isomorphic pairs; a full test
then searches for a valid bijection.

![Two four-cycle graphs with the same structure under a vertex relabelling, hence isomorphic](img/isomorphism.png)

## 2.6 Algorithms

```text
function degree(V, E, v):
    d ← 0
    for each edge {a, b} in E:
        if a == v or b == v: d ← d + 1
    return d

function adjacencyMatrix(V, E):          # V indexed 0..n-1
    A ← n×n matrix filled with 0
    for each edge {u, v} in E:
        A[idx(u)][idx(v)] ← 1
        A[idx(v)][idx(u)] ← 1
    return A

function incidenceMatrix(V, E):          # n vertices, m edges
    M ← n×m matrix filled with 0
    for j, edge {u, v} in E:             # j = 0 .. m-1
        M[idx(u)][j] ← 1
        M[idx(v)][j] ← 1
    return M

function findPath(V, E, start, goal, visited):   # depth-first search
    add start to visited
    if start == goal: return [start]
    for each w adjacent to start:
        if w not in visited:
            sub ← findPath(V, E, w, goal, visited)
            if sub ≠ null: return [start] + sub
    return null

function findCircuit(V, E):              # a closed trail via DFS back-edge
    depth-first search from each vertex, recording the current trail;
    if an edge leads back to a vertex already on the trail, the segment
    from that vertex to the current one, plus the closing edge, is a circuit.
```

**Subgraph test:** confirm $V' \subseteq V$ and, for every edge in $E'$, that the
edge is in $E$ and both endpoints are in $V'$.

**Isomorphism test:** reject immediately if $|V_1|\neq|V_2|$, $|E_1|\neq|E_2|$, or
the sorted degree sequences differ; otherwise search for an adjacency-preserving
bijection by backtracking (matching vertices of equal degree).

## 2.7 Complexity

With $n = |V|$ and $m = |E|$: `degree` is $O(m)$; building either matrix is
$O(n^2)$ (to initialise) plus $O(m)$; `findPath` (DFS) visits each vertex and edge
once, $O(n + m)$. Enumerating **all** simple paths or trails is exponential in the
worst case, and graph **isomorphism** has no known polynomial-time algorithm —
the invariant checks above keep the typical case fast.