Ланцюги та цикли в графах

Рухаючись по ребрах графа G (X, U), можна переходити з вершини в вершину. Будь-яка послідовність ребер, що отримується при цьому, називається маршрутом. тобто послідовність (x0, x1) (x1, x2) ... (xn, xn -1), в якій будь-які два сусідніх ребра суміжні - маршрут.

Ланцюг - маршрут, в якому все ребра різні.

Простий ланцюг - ланцюг, в якій всі вершини різні.

Цикл - ланцюг, в якій збігаються початкова і кінцева вершини.

Дерево - зв'язний граф без циклів. У дереві будь-які дві вершини пов'язані єдиною ланцюгом. Дерево, побудоване на n вершинах, має n-1 ребер.

Ліс - сукупність дерев.

У графах виділяють два чудових циклу: Ейлером і гамільтонів.

Граф називаетсяейлеровим. якщо для будь-якої вершини графа знайдеться маршрут починається і закінчується в цій вершині і проходить через кожне ребро тільки один раз. Такий маршрут називається ейлеровим циклом.

Завдання виникла з такого прикладу. У XIII столітті жителі Кенігсберга, прогулюючись по мостам річки, Прегель намагалися вирішити задачу: чи можна обійти всі мости, проходячи по кожному з них тільки один раз (рис. 1.8)

Завдання полягає в наступному. здійснити прогулянку по місту таким чином, щоб, пройшовши рівно по одному разу за кожним мосту, повернутися в той же місце, звідки починалася прогулянка. Вирішуючи цю задачу, Ейлер зобразив Кенігсберг у вигляді графа, ототожнити його вершини з частинами міста, а ребра - з мостами, якими пов'язані ці частини.

Ейлера вдалося довести, що шуканого маршруту обходу міста не існує.

Відповідь може бути отриманий на основі наступної теореми.

Теорема. Граф є ейлеровим тоді і тільки тоді, коли ступеня всіх його вершин парні.

Як випливає з малюнка, у графа, що моделює схему мостів, все вершини мають непарну ступінь. Отже, ейлерова циклу в цьому графі не існує.

Приклад графа, що має Ейлером, цикл показаний на рис. 1.9.

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

У повному графі з числом вершин n »2 завжди існує гамільтонів цикл. Приклад такого циклу наведено на рис. 1.10 - (x1, x4) (x4, x2) (x2, x5) (x5, x3) (x3, x1).

Гамільтона графи застосовуються для моделювання багатьох практичних завдань, наприклад, служать моделлю при складанні розкладу руху поїздів. Основою всіх таких завдань служить класична задача комівояжера: комівояжер повинен здійснити поїздку по містах і повернутися назад, побувавши в кожному місті рівно один раз, звівши при цьому витрати на пересування до мінімуму.

Графічна модель завдання комівояжера складається з Гамільтона графа, вершини якого зображують міста, а ребра - зв'язуючі їх дороги. Крім того, кожне ребро оснащено вагою, що позначає транспортні витрати, необхідні для подорожі за відповідною дорозі, такі, як, наприклад, відстань між містами або час руху по дорозі. Для вирішення завдання необхідно знайти гамільтонів цикл мінімального загальної ваги.