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

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

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

| | |
|---|---|
| **Тема** | Матриця суміжності (неорієнтована / орієнтована, петлі, кратні ребра); побудова графа за матрицею; правильне розфарбування вершин і ребер; хроматичне число та хроматичний клас; класи за Візінгом |
| **Передумова** | [Лекція 7. Графи: основні поняття](../../Lectures/ODM-L07.md) — подання графів і розфарбування |
| **Формат** | **Домашнє завдання за варіантом**, виконується вручну (олівець і папір). Розв'язків не наведено |
| **Що здати** | Акуратно зображені графи (Задачі 1–2) та знайдені $\chi$, $\chi'$ із обґрунтуванням (Задача 3) — див. [3task.md](3task.md) |

## Зміст

| # | Частина | Файл |
|:--:|---|---|
| 1 | Мета роботи | [1purpose.md](1purpose.md) |
| 2 | Методичні вказівки (самодостатня теорія + приклад) | [2method.md](2method.md) |
| 3 | **Завдання за варіантами** (без розв'язків) | [3task.md](3task.md) |
| 6 | Контрольні запитання | [6questions.md](6questions.md) |

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

- **Мова.** Усі записи виконуються **українською**.
- **Вручну.** Читайте матрицю, малюйте граф і розфарбовуйте його безпосередньо;
  для кожної вершини (чи ребра) вказуйте її колір і клас (групу), до якого вона
  належить.
- **Домовленість про матрицю суміжності.** Елемент $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](2method.md).
- **Домашнє завдання за варіантом, розв'язків не наведено.** Свій варіант кожної
  задачі студент визначає за номером $N$ у журналі та вказаною формулою; виконує
  **лише свій** варіант, якщо викладач не розпорядився інакше. Уся потрібна теорія
  та **демонстраційний приклад методу** (на інших даних) містяться в
  [2method.md](2method.md), тож роботу можна виконати без сторонніх джерел.

## Підсумок

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