Теорія графів: задачі з покроковими розв’язками

1Вершини, ребра та степені

Граф складається з вершин (точок) і ребер (ліній між двома вершинами). У простому графі немає петель і кратних ребер.

Степінь вершини — це кількість ребер, що в ній сходяться. Кожне ребро має два кінці, тож додає 1 до степеня кожного кінця. Звідси лема про рукостискання:

Два наслідки: сума степенів завжди парна, і кількість вершин з непарним степенем теж парна.

• Повний граф K_n з’єднує кожну пару: n(n − 1)/2 ребер.
• Повний дводольний граф K_m,n з’єднує кожну вершину однієї частини з кожною вершиною іншої: m·n ребер.
• k-регулярний граф на n вершинах має n·k/2 ребер.

Матриця суміжності має 1 на місці (i, j), коли i та j з’єднані. Для неорієнтованого графа вона симетрична, сума рядка — це степінь, а елемент (i, j) матриці Mᴸ рахує маршрути довжиною L з i до j.

2Ейлер і Гамільтон

Ейлерів цикл проходить кожне ребро рівно один раз і повертається до початку. Ейлерів шлях проходить кожне ребро один раз, але може закінчитися деінде. Для зв’язного графа:

• усі степені парні: ейлерів цикл існує;
• рівно два непарні степені: ейлерів шлях існує, від однієї непарної вершини до другої;
• більше двох непарних степенів: нічого з цього.

Гамільтонів цикл відвідує кожну вершину рівно один раз. Простого критерію за степенями для нього немає. У K_n існує (n − 1)!/2 різних гамільтонових циклів: зафіксуйте початок, впорядкуйте решту n − 1 вершин і поділіть на 2 через два напрямки.

3Дерева

Дерево — це зв’язний граф без циклів. Кожне дерево з n вершинами має рівно n − 1 ребро. Додавання будь-якого ребра створює цикл; вилучення будь-якого ребра розриває зв’язність.

Ліс із c дерев на n вершинах має n − c ребер. Зв’язний граф з m ребрами зберігає остовне дерево після вилучення m − n + 1 ребер.

Лема про рукостискання рахує листки: Σ deg = 2(n − 1). Коротка форма: L = 2 + Σ (d − 2) за вершинами зі степенем d ≥ 3. Дерево з двома вершинами степеня 3, а решта листки, має 2 + 1 + 1 = 4 листки.

4Дейкстра та мінімальні остовні дерева

Алгоритм Дейкстри знаходить найкоротші відстані від початкової вершини в графі з невід’ємними вагами.

1. Дайте початковій вершині відстань 0, а кожній іншій — ∞.
2. Зафіксуйте незафіксовану вершину з найменшою відстанню; тепер її відстань остаточна.
3. Для кожного сусіда v оновіть d(v) = min(d(v), d(u) + w(u, v)).
4. Повторюйте, доки цільову вершину не буде зафіксовано.

Мінімальне остовне дерево з’єднує всі вершини з найменшою сумарною вагою. Крускал сортує ребра від легких до важких і бере кожне, якщо воно не замикає цикл. Прім нарощує одне дерево від початкової вершини, щоразу додаючи найлегше ребро, що виходить з нього. Обидва алгоритми зупиняються після n − 1 ребер.

5Типові помилки

• Забути поділити суму степенів на 2, щоб отримати кількість ребер.
• Перевіряти наявність ейлерового циклу, не переконавшись, що граф зв’язний.
• Фіксувати вершину в алгоритмі Дейкстри, поки вона не має найменшої попередньої відстані.
• Брати n − 1 найлегших ребер, не перевіряючи циклів.
• Рахувати гамільтонові цикли в K_n як n! замість (n − 1)!/2.

6Як виглядають екзаменаційні запитання

• Легкий: степені та ребра. Ви користуєтеся лемою про рукостискання, рахуєте ребра в K_n, K_m,n, регулярних графах і деревах, читаєте матрицю суміжності або клікаєте вершину із заданим степенем.
• Середній: ейлерові шляхи та дерева. Ви визначаєте, чи має граф ейлерів цикл або шлях, рахуєте листки дерева, кількість ребер для вилучення до остовного дерева або гамільтонові цикли в K_n.
• Складний: найкоротші шляхи та остовні дерева. Ви виконуєте алгоритм Дейкстри, знаходите вершину, зафіксовану в заданому раунді, вагу мінімального остовного дерева, клікаєте ребро, яке наступним додасть Крускал чи Прім, або рахуєте маршрути за матрицею суміжності.