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:
[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:
[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