Practical Work 5 — Graphs: Representation and Colouring #

Fifth practical class of Computer Discrete Mathematics. Working by hand, you move between a graph and its adjacency matrix (undirected and directed), and you colour graphs — finding the chromatic number $\chi$ (vertices) and the chromatic index $\chi'$ (edges).

At a glance #

Contents #

Conventions #

• Language — all work is written in English.
• By hand. Read each matrix, draw the graph, and colour it directly; show the colour of every vertex (or edge) and the group each belongs to.
• Adjacency-matrix convention. The entry $a_{ij}$ is the number of edges (undirected) or arcs (directed) between $v_i$ and $v_j$; a diagonal entry $a_{ii}$ is the number of loops at $v_i$. (Some texts, including L10, instead count each loop as $2$ on the diagonal; this worksheet counts loops once, matching its data.)
• Notation is fixed and self-contained. $\deg(v)$ is the degree; $\Delta(G)$ the maximum degree; $\omega(G)$ the largest clique; $\chi(G)$ the chromatic number and $\chi'(G)$ the chromatic index. All are defined in 2method.md.
• Every task has a full solution. 3classroom.md gives each task together with a complete worked answer, including the drawn graph and its colouring.

Summary #

A graph can be stored as a table of numbers — its adjacency matrix — and drawn back from that table; the two views are interchangeable, and the matrix instantly shows whether the graph is directed (asymmetric), has loops (non-zero diagonal), or parallel edges (entries above $1$). The second theme is colouring: paint the vertices so neighbours differ (the fewest colours is the chromatic number $\chi$), or the edges so those meeting at a vertex differ (the fewest is the chromatic index $\chi'$). Colouring turns real conflict problems — timetabling, register allocation, frequency assignment — into a single question, how few colours are enough?, bounded below by the biggest clique and the maximum degree and, for edges, pinned by Vizing’s theorem to just two possible values.

Practical/Practical5/main.md · 3.0 KB · updated 2026-07-31 21:51