CDM/Laboratory/Laboratory6/main
Raw

Laboratory Work 6 — Graph Theory Basics

Sixth laboratory work of Computer Discrete Mathematics. You implement the core operations on graphs: vertex degrees and the handshaking theorem, the adjacency and incidence matrices, path finding, subgraph testing, isomorphism, and the discovery of circuits, walks, and trails.

At a glance

Topic Graphs: degree, matrix representations, paths, subgraphs, isomorphism, circuits, walks & trails
Prerequisite lectures L10 — Graph theory (basics)
Deliverable Source code + report (see 5report.md)
Grading Banded: Easy 60–74 / Medium 75–89 / Hard 90–100 (see 4task.md)

Contents

# Part File
1 Objective 1purpose.md
2 Methodical guidelines (theory & algorithms) 2method.md
4 Task and order of execution 4task.md
5 Report contents 5report.md
6 Control questions 6questions.md

Conventions

  • Language — source code and the report are in English.
  • Implement it yourself — no built-in shortcuts. Do not call a library or built-in that performs the core task for you (e.g. no HashSet/set()/Set for sets, no library graph/relation type, no math.gcd, no eval). Build the mechanism from basic primitives — arrays/lists, loops, arithmetic, strings.
  • Deliverable — submit the source code and a report structured as in 5report.md; the code must reproduce the example outputs in 4task.md.
  • Self-contained theory — everything needed is in 2method.md; no external material is required.

Summary

A graph models a set of objects (vertices) and the connections between them (edges). This work covers the foundations: measuring how connected a vertex is (its degree) and the handshaking theorem that ties degrees to the number of edges; the two standard matrix encodings (adjacency and incidence); moving through a graph via walks, trails, paths, and circuits; and comparing graphs through the subgraph and isomorphism relations. The tasks are grouped into three difficulty bands.

Laboratory/Laboratory6/main.md · 2.3 KB · updated 2026-08-01 20:19