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 «Графи: основні поняття» (подання графів і розфарбування). Уся потрібна теорія повторена, самодостатньо, у 2method.md; там само наведено демонстраційний приклад методу на даних, відмінних від будь-якого варіанта.

Practical/Practical4/1purpose.md · 2.9 KB · updated 2026-08-04 14:34