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

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

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

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

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

Варіант 1 #

Варіант 2 #

Варіант 3 #

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

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

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

Варіант 1 #

Варіант 2 #

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

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

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

Варіант 1 #

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

Варіант 2 #

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

Варіант 3 #

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

Варіант 4 #

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

Варіант 5 #

Вершини: $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$ або підписами; головне — щоб було видно, який колір має кожна вершина/ребро та до якого класу вона належить.

Practical/Practical4/3task.md · 6.7 KB · updated 2026-08-04 14:36