# 3. Завдання за варіантами

> **Домашнє завдання.** Свій варіант кожної задачі визначте за номером $N$ у журналі
> та формулою, вказаною поряд із задачею; виконуйте **лише свій** варіант, якщо
> викладач не розпорядився інакше. **Розв'язків і відповідей тут не наведено** — уся
> потрібна теорія та зразок методу є в [2method.md](2method.md). Домовленість про
> матрицю суміжності (діагональ — петлі, елементи $>1$ — кратні ребра/дуги) —
> у [main.md](main.md).

## Задача 1. Неорієнтовані графи за матрицями суміжності

**Варіант:** $\;N \bmod 3 + 1\;$ (де $N$ — номер за журналом).

Для свого варіанта: **зобразіть** неорієнтований граф за поданою матрицею, окремо
позначивши **петлі** (діагональ) і **кратні ребра** (елементи, більші за $1$), та
**зчитайте степінь** кожної вершини із сум рядків.

### Варіант 1

| | $A$ | $B$ | $C$ | $D$ |
|:--:|:--:|:--:|:--:|:--:|
| $A$ | 0 | 1 | 0 | 1 |
| $B$ | 1 | 0 | 1 | 0 |
| $C$ | 0 | 1 | 0 | 1 |
| $D$ | 1 | 0 | 1 | 0 |

### Варіант 2

| | $A$ | $B$ | $C$ | $D$ |
|:--:|:--:|:--:|:--:|:--:|
| $A$ | 1 | 0 | 1 | 1 |
| $B$ | 0 | 0 | 1 | 1 |
| $C$ | 1 | 1 | 0 | 1 |
| $D$ | 1 | 1 | 1 | 1 |

### Варіант 3

| | $A$ | $B$ | $C$ | $D$ |
|:--:|:--:|:--:|:--:|:--:|
| $A$ | 1 | 2 | 0 | 1 |
| $B$ | 2 | 0 | 3 | 0 |
| $C$ | 0 | 3 | 1 | 1 |
| $D$ | 1 | 0 | 1 | 0 |

## Задача 2. Орієнтовані графи за матрицями суміжності

**Варіант:** $\;N \bmod 2 + 1\;$ (де $N$ — номер за журналом).

Для свого варіанта: **зобразіть** орієнтований граф за поданою матрицею (рядок —
початок дуги, стовпець — кінець), позначивши **петлі** та **кратні дуги**, і
**зчитайте** напівстепінь виходу $\deg^{+}$ (сума рядка) та напівстепінь заходу
$\deg^{-}$ (сума стовпця) для кожної вершини.

### Варіант 1

| | $A$ | $B$ | $C$ | $D$ |
|:--:|:--:|:--:|:--:|:--:|
| $A$ | 0 | 0 | 1 | 1 |
| $B$ | 0 | 0 | 1 | 0 |
| $C$ | 1 | 1 | 0 | 1 |
| $D$ | 1 | 1 | 1 | 0 |

### Варіант 2

| | $A$ | $B$ | $C$ | $D$ |
|:--:|:--:|:--:|:--:|:--:|
| $A$ | 0 | 2 | 3 | 0 |
| $B$ | 1 | 2 | 2 | 1 |
| $C$ | 2 | 1 | 1 | 0 |
| $D$ | 1 | 0 | 0 | 2 |

## Задача 3. Хроматичне число та хроматичний клас

**Варіант:** $\;N \bmod 5 + 1\;$ (де $N$ — номер за журналом).

Для графа свого варіанта визначте **хроматичне число** $\chi$ (розфарбування вершин)
та **хроматичний клас** $\chi'$ (розфарбування ребер). Для кожної з двох величин
**обґрунтуйте** відповідь двома кроками (див. [2method.md](2method.md), §2.5–2.6):
наведіть саме розфарбування потрібною кількістю кольорів **і** причину, чому меншого
не досягти (кліка — для $\chi$; максимальний степінь $\Delta$ або лічильна оцінка —
для $\chi'$). Додатково зазначте, до якого **класу за Візінгом** — **I** ($\chi' =
\Delta$) чи **II** ($\chi' = \Delta + 1$) — належить граф. Під кожним рисунком
наведено список ребер для однозначного прочитання.

### Варіант 1

![Граф варіанта 1: п'ять вершин a, b, c, d, e, з'єднаних у цикл](img/p4_var1.png)

Вершини: $a, b, c, d, e$. Ребра: $ab,\ bc,\ cd,\ de,\ ea$.

### Варіант 2

![Граф варіанта 2: квадрат a-b-c-d із трикутною «покрівлею» на вершинах c, d, e](img/p4_var2.png)

Вершини: $a, b, c, d, e$. Ребра: $ab,\ bc,\ cd,\ da,\ ce,\ de$.

### Варіант 3

![Граф варіанта 3: дві вершини a, b ліворуч, з'єднані з трьома вершинами c, d, e праворуч](img/p4_var3.png)

Вершини: $a, b, c, d, e$. Ребра: $ac,\ ad,\ ae,\ bc,\ bd,\ be$.

### Варіант 4

![Граф варіанта 4: центральна вершина f, з'єднана з усіма вершинами п'ятикутника a, b, c, d, e](img/p4_var4.png)

Вершини: $a, b, c, d, e, f$. Ребра: $ab,\ bc,\ cd,\ de,\ ea,\ fa,\ fb,\ fc,\ fd,\ fe$.

### Варіант 5

![Граф варіанта 5: п'ять вершин a, b, c, d, e, кожна з'єднана з кожною](img/p4_var5.png)

Вершини: $a, b, c, d, e$. Ребра: $ab,\ ac,\ ad,\ ae,\ bc,\ bd,\ be,\ cd,\ ce,\ de$.

## Що і як здати

- **Задачі 1–2.** Для свого варіанта — акуратний рисунок графа (петлі та кратні
  ребра/дуги позначено окремо) і таблиця степенів: $\deg(v)$ для неорієнтованого
  графа; $\deg^{+}(v)$ та $\deg^{-}(v)$ — для орієнтованого. Обов'язково перевірте
  степені за сумами рядків (і стовпців — для орграфа) та, для неорієнтованого графа,
  за лемою про рукостискання $\sum_v \deg(v) = 2|E|$.
- **Задача 3.** Значення $\chi$ і $\chi'$ із **повним обґрунтуванням** (оцінка знизу
  + явне розфарбування зверху) та зазначенням класу за Візінгом. Наведіть саме
  розфарбування: колір кожної вершини (для $\chi$) і колір кожного ребра (для
  $\chi'$), згрупувавши однокольорові у класи.
- **Оформлення.** Кольори можна замінювати номерами $1, 2, 3, \dots$ або підписами;
  головне — щоб було видно, який колір має кожна вершина/ребро та до якого класу
  вона належить.