Звʼязність графа, компоненти звʼязності; відстань між вершинами

📌 Про що ця тема

Тут перевіряють уміння працювати з графами: визначати, чи «розпадається» граф на окремі частини, рахувати компоненти звʼязності й знаходити найкоротшу відстань між вершинами. Ключові поняття — звʼязність, компонента звʼязності, відстань. Це база для задач на мережі, маршрути, соціальні звʼязки.

📖 Головне

• Граф — це множина вершин і ребер (звʼязків між парами вершин). Граф буває неорієнтований (ребра без напрямку) та орієнтований (дуги зі стрілками).

• Шлях (маршрут) між двома вершинами — послідовність ребер, що веде від однієї до іншої. Якщо такий маршрут існує, вершини вважають звʼязаними.

• Граф звʼязний, якщо з будь-якої вершини можна дійти до будь-якої іншої. Якщо хоч одна пара не зʼєднана — граф незвʼязний.

• Компонента звʼязності — максимальна група вершин, у якій усі попарно досяжні. Звʼязний граф має рівно 1 компоненту; незвʼязний — 2 і більше.

• Ізольована вершина (без ребер) — це окрема компонента сама по собі.

• Відстань між вершинами — кількість ребер у найкоротшому шляху між ними. Якщо шляху немає — відстань вважають нескінченною (∞).

• Якщо вершини в різних компонентах, відстань між ними нескінченна.

• Для пошуку компонент і найкоротших відстаней (у графі без ваг) використовують обхід: BFS (пошук у ширину) або DFS (пошук у глибину). BFS природно дає найкоротші відстані.

• У графі з n вершинами відстань між двома зʼєднаними вершинами не перевищує n−1.

🔢 Як це працює на прикладі

Нехай вершини 1,2,3,4,5,6 і ребра: 1–2, 2–3, 1–3, 4–5, 6 (ізольована).

• Крок 1. Починаємо з вершини 1, обходимо: 1→2→3. Усі досяжні між собою — це компонента {1,2,3}.

• Крок 2. Беремо вершину 4: 4→5. Компонента {4,5}.

• Крок 3. Вершина 6 без ребер — компонента {6}.

Отже компонент звʼязності 3, граф незвʼязний.

Відстань від 1 до 3: є ребро 1–3, тому відстань = 1 (а не 2 через вершину 2 — беремо найкоротший шлях). Відстань від 1 до 5 = ∞ (різні компоненти).

⚠️ Типові помилки

• Плутають відстань і довжину будь-якого маршруту: відстань — це ТІЛЬКИ найкоротший шлях, а не перший знайдений.

• Забувають ізольовані вершини — кожна з них окрема компонента, її теж рахують.

• Вважають граф звʼязним, якщо більшість вершин зʼєднані; достатньо однієї недосяжної вершини, щоб граф став незвʼязним.

• Рахують відстань у вершинах, а не в ребрах. Відстань — це кількість РЕБЕР (ребер завжди на 1 менше, ніж вершин у шляху).

• В орієнтованому графі забувають про напрямок: дуга a→b не дає шляху з b до a.

🎯 Що завчити напамʼять

• Звʼязний граф = 1 компонента; усі вершини взаємно досяжні.

• Відстань = кількість ребер у найкоротшому шляху; немає шляху → ∞.

• Ізольована вершина — окрема компонента.

• BFS дає найкоротші відстані в невагомому графі.

• Макс. відстань у звʼязному графі з n вершин ≤ n−1.

🧠 Перевір себе

1. Граф має вершини A,B,C,D і ребра A–B, C–D. Скільки компонент звʼязності?

2. Ребра: X–Y, Y–Z, X–Z. Яка відстань від X до Z?

3. Чи може звʼязний граф мати 2 компоненти?

4. Чому дорівнює відстань між вершинами з різних компонент?

Відповіді: 1—дві ({A,B} і {C,D}); 2—1 (пряме ребро X–Z); 3—ні, звʼязний граф має рівно 1 компоненту; 4—нескінченності (∞), шляху немає.