1. Objective / Мета роботи #

Gain fluency in the two standard descriptions of a graph — the picture and the adjacency matrix — and in colouring graphs: computing the chromatic number $\chi(G)$ and the chromatic index $\chi'(G)$.

By the end of the class the student should be able to:

• read an adjacency matrix and draw the corresponding graph — recognising from the matrix alone whether it is undirected (symmetric) or directed (asymmetric), and where it has loops (diagonal entries) or parallel edges/arcs (entries greater than $1$);
• go the other way — write the adjacency matrix of a given graph — and read off each vertex’s degree (row sum) or, for a digraph, its out-degree (row sum) and in-degree (column sum);
• find a proper vertex colouring and the chromatic number $\chi(G)$, using the clique lower bound $\chi\ge\omega$ and the greedy upper bound $\chi\le\Delta+1$ to trap the value;
• find a proper edge colouring and the chromatic index $\chi'(G)$, using $\chi'\ge\Delta$ and Vizing’s theorem $\chi'\in\{\Delta,\Delta+1\}$ to decide whether the graph is class 1 or class 2;
• explain why colouring matters — scheduling, register allocation, and frequency assignment are all “colour so that conflicting things differ”.

The class consolidates Lecture 10 — Graph theory (basics) (representations §10.6 and colouring §10.12) and complements Lab 6. All theory needed is restated, self-contained, in 2method.md.

Practical/Practical5/1purpose.md · 1.6 KB · updated 2026-07-31 21:51