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

**Набути вправності у двох стандартних поданнях графа — рисунку та матриці
суміжності — і в розфарбуванні графів: обчисленні хроматичного числа $\chi(G)$ та
хроматичного класу (індексу) $\chi'(G)$.**

Виконавши роботу, студент повинен уміти:

- **читати матрицю суміжності** та **малювати** відповідний граф — розпізнаючи вже
  за самою матрицею, чи він **неорієнтований** (симетрична матриця), чи
  **орієнтований** (несиметрична), а також де в нього **петлі** (діагональні
  елементи) та **кратні ребра/дуги** (елементи, більші за $1$);
- рухатися у зворотному напрямі — **записувати матрицю суміжності** заданого графа —
  і зчитувати **степінь** кожної вершини (сума рядка) або, для орграфа, її
  **напівстепінь виходу** $\deg^{+}$ (сума рядка) та **напівстепінь заходу**
  $\deg^{-}$ (сума стовпця);
- знаходити **правильне розфарбування вершин** і **хроматичне число** $\chi(G)$,
  затискаючи його значення між **нижньою оцінкою через кліку** $\chi \ge \omega$ і
  **верхньою жадібною оцінкою** $\chi \le \Delta + 1$;
- знаходити **правильне розфарбування ребер** і **хроматичний клас** $\chi'(G)$,
  користуючись оцінкою $\chi' \ge \Delta$ та **теоремою Візінга**
  $\chi' \in \{\Delta,\ \Delta + 1\}$, щоб визначити, до якого класу — **I** чи
  **II** — належить граф;
- пояснювати, **чому** розфарбування важливе: складання розкладів, розподіл
  регістрів процесора та призначення радіочастот — це все задачі виду «пофарбувати
  так, щоб конфліктні об'єкти відрізнялися».

Заняття спирається на матеріал
[Лекції 7 «Графи: основні поняття»](../../Lectures/ODM-L07.md) (подання графів і
розфарбування). Уся потрібна теорія повторена, самодостатньо, у
[2method.md](2method.md); там само наведено **демонстраційний приклад** методу на
даних, відмінних від будь-якого варіанта.