Маршрути, ланцюги, цикли у графах

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

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

📖 Головне

• Граф — це множина вершин і ребер (звʼязків між парами вершин). Позначають G(V, E), де V — вершини, E — ребра.

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

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

• Маршрут — послідовність вершин і ребер, де кожне наступне ребро починається там, де закінчилось попереднє. Вершини й ребра можуть повторюватися.

• Ланцюг (простий шлях) — маршрут, у якому ребра НЕ повторюються. Простий ланцюг — не повторюються й вершини.

• Цикл — замкнений маршрут, що починається й закінчується в одній вершині, а ребра не повторюються. Простий цикл — не повторюються проміжні вершини.

• Довжина маршруту — кількість ребер у ньому (або сума ваг для зваженого графа).

• Граф звʼязний, якщо між будь-якими двома вершинами існує маршрут.

• Зважений граф — ребрам приписані числа (ваги): відстань, вартість, час.

• Найкоротший шлях — маршрут з найменшою сумою ваг; шукають алгоритмами (напр., хвильовим або Дейкстри).

• Способи задання графа: малюнок, список ребер, матриця суміжності (клітинка = чи є ребро), матриця інцидентності.

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

Граф з вершинами A, B, C, D і ребрами: A–B, B–C, C–D, D–A, A–C.

• Маршрут A–B–C–A–D: довжина 4, вершина A повторюється → це просто маршрут.

• Ланцюг A–B–C–D: ребра не повторюються, вершини не повторюються → простий ланцюг довжиною 3.

• Цикл A–B–C–A: повертається в A, ребра AB, BC, CA різні → простий цикл довжиною 3.

• Степінь вершини A = 3 (ребра до B, D, C). Сума всіх степенів = 2·5 = 10 (бо 5 ребер).

Найкоротший шлях від A до C: напряму ребром A–C (довжина 1), а не через B (довжина 2).

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

• Плутають ланцюг і цикл: цикл обовʼязково замкнений (старт = фініш), ланцюг — ні.

• Вважають, що в маршруті нічого не можна повторювати — насправді в маршруті можна, обмеження дають слова «простий» чи «ланцюг/цикл».

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

• Забувають, що в орграфі напрям важливий: ребро A→B не дозволяє рух B→A.

• Для зваженого графа беруть маршрут з найменшою кількістю ребер замість найменшої суми ваг.

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

• Довжина = кількість ребер (у зваженому — сума ваг).

• Сума степенів вершин = 2 · (кількість ребер).

• Ланцюг — ребра не повторюються; цикл — замкнений, ребра не повторюються.

• Простий = і вершини не повторюються.

• Звʼязний граф — є маршрут між будь-якою парою вершин.

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

1. Чим відрізняється простий ланцюг від простого циклу?

2. У графі 6 ребер. Чому дорівнює сума степенів усіх вершин?

3. Маршрут A–B–C–B–D: це ланцюг? Чому?

4. Що означає «граф звʼязний»?

Відповіді: 1—простий цикл замкнений (старт = фініш), простий ланцюг — ні, але обидва без повторення вершин/ребер; 2—2·6 = 12; 3—ні, бо повторюється ребро B–C (вершина B теж), ребра в ланцюзі повторюватись не можуть; 4—між будь-якими двома вершинами існує маршрут.