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$. До якого класу за Візінгом він належить і чому двох кольорів для його ребер не досить?

Practical/Practical4/6questions.md · 3.7 KB · updated 2026-08-04 14:36