# 6. Контрольні запитання

## Матриці суміжності

1. Дайте означення **матриці суміжності** графа. Що означає елемент $a_{ij}$, коли
   він дорівнює $0$, коли $1$, а коли $3$?
2. Як **лише за матрицею** визначити, орієнтований граф чи неорієнтований? Де в
   матриці «сидять» **петлі**?
3. Для **неорієнтованого** графа: як зчитати $\deg(v_i)$ з матриці й чому до суми
   рядка треба ще раз додати діагональний елемент $a_{ii}$?
4. Для **орграфа**: яка сума дає **напівстепінь виходу** $\deg^{+}(v_i)$, а яка —
   **напівстепінь заходу** $\deg^{-}(v_i)$? Чому $\sum_v \deg^{+}(v) = \sum_v
   \deg^{-}(v)$?
5. Сформулюйте **лему про рукостискання**. Як за її допомогою перевірити правильність
   зчитаних степенів неорієнтованого графа?
6. Запишіть матрицю суміжності циклу $A\!-\!B\!-\!C\!-\!D\!-\!A$, а потім додайте
   петлю при $A$ та друге ребро $B\!=\!C$; покажіть, як кожна зміна впливає на
   матрицю.
7. Намалюйте неорієнтований граф за матрицею
   $\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 2 \\ 1 & 2 & 1 \end{pmatrix}$
   (вершини $x, y, z$) і вкажіть степінь кожної вершини.

## Розфарбування вершин і хроматичне число

8. Дайте означення **правильного розфарбування вершин** і **хроматичного числа**
   $\chi(G)$. Чому кратні ребра не змінюють $\chi$, а петля робить правильне
   розфарбування неможливим?
9. Сформулюйте **нижню оцінку через кліку** та **верхню жадібну оцінку** для $\chi$.
   Чому дорівнює $\chi(K_n)$?
10. Доведіть, що $\chi(G) \le 2$ **тоді й лише тоді**, коли $G$ **двочастковий**,
    тобто не має циклу непарної довжини. Чому дорівнюють $\chi(C_{2k})$ і
    $\chi(C_{2k+1})$?
11. Щоб показати, що $\chi(G) = 3$, треба обґрунтувати **дві** речі — які саме? (Саме
    так розв'язують Задачу 3.)

## Розфарбування ребер і хроматичний клас

12. Дайте означення **правильного розфарбування ребер** і **хроматичного класу**
    (індексу) $\chi'(G)$. Чому кожен клас одного кольору є **паруванням**?
13. Сформулюйте **теорему Візінга**. Що означають **клас I** та **клас II**? Наведіть
    приклад графа кожного класу.
14. Чому для будь-якого графа $\chi'(G) \ge \Delta(G)$? Наведіть **лічильну оцінку**
    $\chi' \ge \lceil |E| / \lfloor n/2 \rfloor \rceil$ і поясніть, коли вона змушує
    $\chi'$ перевищити $\Delta$.
15. Непарний цикл $C_5$ має $\Delta = 2$, проте $\chi'(C_5) = 3$. До якого класу за
    Візінгом він належить і чому двох кольорів для його ребер не досить?