Практична робота 4. Теорія графів: подання та розфарбування #

Четверте практичне заняття курсу «Основи дискретної математики». Працюючи вручну, ви переходите від графа до його матриці суміжності й назад (для неорієнтованих і орієнтованих графів), а також розфарбовуєте графи — знаходите хроматичне число $\chi$ (за вершинами) та хроматичний клас (індекс) $\chi'$ (за ребрами).

Швидкий огляд #

Зміст #

Позначення та домовленості #

• Мова. Усі записи виконуються українською.
• Вручну. Читайте матрицю, малюйте граф і розфарбовуйте його безпосередньо; для кожної вершини (чи ребра) вказуйте її колір і клас (групу), до якого вона належить.
• Домовленість про матрицю суміжності. Елемент $a_{ij}$ — це кількість ребер (у неорієнтованому графі) або дуг (в орієнтованому) між вершинами $v_i$ та $v_j$. Діагональний елемент $a_{ii}$ — кількість петель при $v_i$ (кожну петлю на діагоналі рахуємо один раз). У степені вершини петля рахується двічі.
• Фіксовані позначення. $\deg(v)$ — степінь вершини; $\deg^{+}(v)$, $\deg^{-}(v)$ — напівстепені виходу та заходу (для орграфа); $\Delta(G)$ — максимальний степінь; $\omega(G)$ — розмір найбільшої кліки; $\chi(G)$ — хроматичне число; $\chi'(G)$ — хроматичний клас (індекс). Усі вони означені в 2method.md.
• Домашнє завдання за варіантом, розв’язків не наведено. Свій варіант кожної задачі студент визначає за номером $N$ у журналі та вказаною формулою; виконує лише свій варіант, якщо викладач не розпорядився інакше. Уся потрібна теорія та демонстраційний приклад методу (на інших даних) містяться в 2method.md, тож роботу можна виконати без сторонніх джерел.

Підсумок #

Граф можна зберігати як таблицю чисел — його матрицю суміжності — і за цією таблицею відновити рисунок; обидва подання рівносильні, а сама матриця миттєво показує, чи граф орієнтований (несиметрична матриця), чи має петлі (ненульова діагональ) та кратні ребра (елементи, більші за $1$). Друга тема — розфарбування: пофарбувати вершини так, щоб сусідні відрізнялися (найменша кількість кольорів — це хроматичне число $\chi$), або пофарбувати ребра так, щоб суміжні (спільні для однієї вершини) відрізнялися (найменша кількість — це хроматичний клас $\chi'$). Розфарбування перетворює реальні задачі про конфлікти — складання розкладів, розподіл регістрів, призначення частот — на одне запитання: скільки кольорів достатньо?, знизу обмежене найбільшою клікою та максимальним степенем, а для ребер — теоремою Візінга — звужене всього до двох можливих значень.

Practical/Practical4/main.md · 5.8 KB · updated 2026-08-04 14:33