# 4. Task and order of execution / Завдання та порядок виконання

> **Source of tasks.** The nine tasks below are taken **exactly** from the
> assignment. Implement the described behaviour; the input/output examples are
> authoritative. Graphs are undirected.

## Order of execution

The tasks are grouped into three difficulty bands. Implement them in order and
test each against its example; your score corresponds to the band of tasks you
complete correctly.

## Easy tasks (60–74 points)

### Task 1 — Degree Calculator
**Objective:** Write a program that calculates the degree of each vertex in a
graph.
- **Input:** Vertices = `{A, B, C}`, Edges = `{(A, B), (B, C), (C, A)}`
- **Output:** Degree of A: `2`; Degree of B: `2`; Degree of C: `2`

### Task 2 — Adjacency Matrix Builder
**Objective:** Implement a program to create the adjacency matrix of a graph.
- **Input:** Vertices = `{1, 2, 3}`, Edges = `{(1, 2), (2, 3)}`
- **Output — Adjacency Matrix:**

```text
[0, 1, 0]
[1, 0, 1]
[0, 1, 0]
```

### Task 3 — Path Finder
**Objective:** Create a program to find a path between two vertices in a graph.
- **Input:** Vertices = `{1, 2, 3, 4}`, Edges = `{(1, 2), (2, 3), (3, 4)}`;
  Start Vertex: `1`; End Vertex: `4`
- **Output:** Path: `1 -> 2 -> 3 -> 4`

## Medium tasks (75–89 points)

### Task 4 — Subgraph Identifier
**Objective:** Write a program that determines if a given graph is a subgraph of
another.
- **Input:** Main Graph: Vertices = `{A, B, C, D}`, Edges = `{(A, B), (B, C), (C, D)}`;
  Subgraph: Vertices = `{B, C}`, Edges = `{(B, C)}`
- **Output:** Is Subgraph: `True`

### Task 5 — Sum of Degrees Checker
**Objective:** Implement a program to verify the Sum of Degrees of Vertices
Theorem in a graph.
- **Input:** Vertices = `{1, 2, 3, 4}`, Edges = `{(1, 2), (2, 3), (3, 4), (4, 1)}`
- **Output:** Sum of Degrees: `8` (which is twice the number of edges);
  Theorem Verified: `True`

### Task 6 — Incidence Matrix Generator
**Objective:** Create a program that generates the incidence matrix of a graph.
- **Input:** Vertices = `{A, B, C}`, Edges = `{(A, B), (B, C)}`
- **Output — Incidence Matrix:**

```text
[1, 0]
[1, 1]
[0, 1]
```

## Hard tasks (90–100 points)

### Task 7 — Graph Isomorphism Tester
**Objective:** Write a program that tests if two graphs are isomorphic.
- **Input:** Graph 1: Vertices = `{1, 2, 3}`, Edges = `{(1, 2), (2, 3)}`;
  Graph 2: Vertices = `{A, B, C}`, Edges = `{(A, B), (B, C)}`
- **Output:** Are Isomorphic: `True`

### Task 8 — Circuit Finder
**Objective:** Implement a program to find a circuit in a graph.
- **Input:** Vertices = `{A, B, C, D}`, Edges = `{(A, B), (B, C), (C, D), (D, A)}`
- **Output:** Circuit: `A -> B -> C -> D -> A`

### Task 9 — Walks and Trails Analyzer
**Objective:** Create a program that identifies all **trails** (walks with no
repeated edge) between two vertices in a graph. Enumerating all *walks* is
impossible — there are infinitely many, since edges may be reused — so the finite
trails (and the simple paths among them) are what is listed.
- **Input:** Vertices = `{1, 2, 3, 4}`, Edges = `{(1, 2), (2, 3), (3, 1), (3, 4)}`;
  Start Vertex: `1`; End Vertex: `4`
- **Output:** Trails: `1 -> 2 -> 3 -> 4`, `1 -> 3 -> 4`