# 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)](../../Lectures/CDM-L10.md)
(representations §10.6 and colouring §10.12) and complements
[Lab 6](../../Laboratory/Laboratory6/main.md). All theory needed is
restated, self-contained, in [2method.md](2method.md).