Підручник з дискретної математики
Саме із завдань, поставлених та вирішених у цьому розділі, почалася теорія графів. Філософ Іммануїл Кант, гуляючи містом Кенігсбергу (зараз це місто називається Калінінград), поставив завдання (1736), відому в математиці як завдання про сім кенігсберзьких мостів: чи можна пройти по всіх цих мостах і при цьому повернутися у вихідну точку так, щоб по кожному мосту пройти лише один раз. Наш петербурзький знаменитий математик швейцарського походження Леонард Ейлер блискуче вирішив це завдання. На рис. 2 зображено схему семи мостів Кенігсберга (зауважимо, що зараз залишилося тільки два з них), а також мультиграф, що відповідає цій схемі (при побудові графа вважалося, що кожен берег річки та острова – це вершини графа, а мости – його ребра; видно, що в даному випадку ми отримали мультиграф без петель).
Відповідно до поставленої Кантом (і вирішеної Ейлером) завданням можна дати такі визначення:
Граф (або мультиграф без петель) називається ейлеровим, якщо існує цикл без повторення ребер (такий цикл називають ейлеровим), що обходить всі вершини графа. Граф називається напівейлеровим, якщо існує маршрут без повторення ребер (ейлерів шлях), що обходить всі ребра графа рівно один раз. На рис. 3 зображені: а – ейлерів граф, б – напівейлерів граф і в – граф, що не є ні ейлеровим, ні напівейлеровим (люди старшого покоління знають, що в школах раніше було багато загадок типу "чи можна намалювати цю фігуру не відриваючи ручку від паперу") що відповідає ейлерову або напівейлерову графу).
Теорема (Ейлер). Для того, щоб даний зв'язковий граф (не орграф, але, можливо, мультиграф без петель) був ейлеровим, необхідно і достатньо,щоб ступеня всіх вершин були парними. Даний зв'язковий граф буде напівейлеровим тоді і тільки тоді, коли ступені двох вершин будуть непарними, а ступеня інших вершин - парними.
Доказ цієї теореми почнемо з так званої леми про рукостискання. Назва цієї леми пов'язана з тим, що ця лема відповідає на наступне запитання: У Вас зібралися гості. Деякі з них вітаються один з одним за допомогою рукостискань. Які властивості має кількість таких людей? Відповідь дається наступною досить простою лемою.
Лемма про рукостискання. Число вершин у графі (або мультиграф без петель), що мають непарний ступінь, парне.
Доказ леми. Зауважимо, що сума ступенів усіх вершин у графі (або мультиграфі без петель) має бути парною. Це з того, що й узяти вершини, взагалі пов'язані друг з одним, то сума ступенів цих вершин дорівнює нулю. Додаючи будь-яке ребро, яке зв'язує дві вершини, збільшуємо суму всіх ступенів на 2 одиниці. Таким чином, сума всіх ступенів вершин парна. Видаляючи з цієї суми ступеня парних вершин, отримаємо, що сума ступенів непарних вершин має бути парною. Це означає, що саме число таких вершин має бути парним. Лемма доведена.
З погляду завдання про рукостискання це означає, що кількість гостей, які привіталися за руку непарне число разів, має бути парним. Перейдемо до доказу теореми Ейлера.
А) Нехай граф є ейлеровим. Тоді в ньому є ейлерів цикл, який повинен прийти в вершину по одному ребру і залишити його по іншому, так як кожне ребро має використовуватися лише один раз (тобто кожен "захід" у вершину і "вихід" з неї дає 2 ступені вершини). Таким чином, сума ступенів усіх вершин має бути парною (і дорівнює подвоєному числу"заходів" в цю вершину при обході ейлерового циклу).
Б) Нехай у даному зв'язному графі (або мультиграф без петель) ступінь будь-якої вершини парна (тобто ступінь більше або дорівнює 2, так як нульовий ступінь призводить до незв'язного графу). Доведемо, що в ньому є цикл ейлерів. Доказ проведемо індукцією за кількістю вершин. У випадку, коли в зв'язному графі всього 2 вершини і обидві вони мають парний ступінь (у цьому випадку маємо мультиграф, один з яких зображений на рис. 4), ясно, що в цьому випадку є цикл ейлерів (за будь-якого парного ступеня цих двох вершин ).
Припустимо, що наше твердження є правильним для всіх зв'язкових графів, число вершин в яких строго менше п, і доведемо його для графа, що має п вершин.
Зауважимо, що у лемі 1 у цьому графі є контур (ступінь всіх вершин більший або дорівнює 2). Якщо цей контур містить усі ребра, цей контур сам є ейлеровим циклом (а граф эйлеровым). Видалимо всі ці ребра з графа і ті вершини, які після видалення ребер стали мати нульовий ступінь. Тоді отримаємо новий граф (який може бути незв'язним), але в цьому новому графі всі вершини обов'язково мають парний ступінь (оскільки при видаленні ребер контуру ступінь кожної вершини, що входить до цього контуру, зменшується на 2). Новий граф розпадається на "компоненти зв'язності", кожна з яких повинна мати загальну вершину з віддаленим контуром (інакше початковий граф не був би зв'язковим), ступеня всіх вершин кожної компоненти зв'язності парні і число вершин в ній строго менше п, тобто. Індукційне припущення ця компонента має ейлерів цикл. Тепер можемо побудувати ейлерів цикл у даному графі так. Обходимо послідовно ребра віддаленого контуру. Якщо ми прийшли у вершину, загальну для контуру і якийсь компонент зв'язності, тообходимо по ейлерову циклу цю компоненту, повертаємося у вершину контуру і йдемо по цьому контуру далі. Тим самим усі ребра будуть пройдені і кожне лише один раз (все це схематично зображено на рис. 5: спочатку починаємо обходити контур АВСDEА. Пройшовши ребро АВ, проходимо "верхній" граф, потім повертаємося в т. В і далі йдемо по ребру АС, обходимо "правий" граф і т. д.). Твердження Б доведено.
В) Нехай тепер граф напівейлерів. Це означає, що він має ейлерів шлях, що починається в одній вершині і закінчується в іншій. Видно, що обидві ці вершини повинні мати непарний ступінь, а ступінь інших парний.
Г) Назад. Нехай у зв'язному графі вершини до і р мають непарний ступінь, інші вершини – парну. Тоді можливі 2 випадки: ці вершини пов'язані ребром чи пов'язані. У першому випадку видалимо це ребро, а в другому додамо. В обох випадках ступінь усіх вершин стане парним. Зауважимо, що у разі видалення ребра, новий граф може стати незв'язним і мати 2 компоненти зв'язності (у цьому випадку ребро, що видаляється, було мостом), кожна з яких або весь новий граф має ейлерів цикл. Тепер якщо новий граф має ейлерів цикл, то почнемо (і закінчимо його) у вершині з непарним ступенем і далі додамо ребро або видалимо його. В обох випадках отримаємо ейлерів шлях. Якщо новий граф має 2 компоненти зв'язності, то, пройшовши одну з них за ейлеровим циклом, починаючи і закінчуючи у вершині (яка в початковому графі мала непарний ступінь), потім додамо віддалене ребро (міст), пройдемо його, потрапимо в іншу вершину, яка раніше мала непарну ступінь, і пройдемо другу компоненту зв'язності за ейлеровим циклом. У всіх розібраних випадках отримаємо ейлерів шлях, який почався в одній з вершин з непарним ступенем і закінчився в іншій. Теорему доведено.
Зауважимо, що всі 4 вершини мультиграфа (рис. 2), що відповідає мостам Кенігсберга, мають ступінь 3. Тому ейлерів цикл або шлях неможливий.
Примітка. Якщо граф (або мультиграф без петель) містить 2k вершин непарного ступеня, його можна розбити на k напівейлерових графів (тобто намалювати k розчерками пера). Доказ аналогічний доказу теореми Ейлера.
Є простий алгоритм (так званий алгоритм Флері) для знаходження ейлерового циклу (звичайно, якщо цей цикл існує), який полягає в наступному: починаємо з будь-якої вершини і "прати" пройдені ребра. При цьому мостом (перешийку) проходимо тільки, якщо немає інших можливостей.
Очевидно, що для того, щоб побудувати ейлерів шлях достатньо використовувати алгоритм Флері, який треба почати з вершини, що має непарний ступінь.
Нехай є деякий граф (зв'язковий), ребрам якого приписані деякі числа, звані терезами ребер (часто, але не завжди!, У додатках вага ребра – це його довжина). Потрібно знайти такий цикл, при якому кожне ребро проходить принаймні один раз і сумарна вага всіх ребер, що увійшли до циклу, мінімальна. Зауважимо, що якщо граф є ейлеровим, то будь-який ейлер цикл вирішує поставлене завдання (для ейлерова графа ваги ролі не грають).
Це завдання має багато додатків, наприклад, поливання вулиць однією машиною (тут ребра графа – дороги, а перехрестя – вершини; ваги – це довжини доріг), а також збір сміття, доставка пошти або навіть найкращий маршрут для огляду музею або прибирання приміщень та коридорів у великих установах.
Коротко розглянемо проблему, пов'язану з можливим обходом усіх вершин у графі: чи існує в даному (зв'язковому) графі цикл (або маршрут), що обходить кожну вершину (крім першої) лише одинразів. Якщо такий цикл (маршрут) існує (у разі такий цикл буде контуром, а маршрут – шляхом), то граф називається гамільтоновим (напівамільтоновим), і відповідний цикл (шлях) також називають гамільтоновим циклом (шляхом).
На рис. 6 зображені гамільтонів, напівгамільтонів та не гамільтонів графи.
Незважаючи на подібність постановки завдань для гамільтонових графів із ейлеровими, “доброго” рішення для гамільтонових графів немає. Взагалі, про гамільтонові графи відомо дуже мало. Здебільшого – це теореми типу “якщо у графі достатньо ребер, він гамільтонів”. Зрозуміло, що теореми такого типу не можуть дати критерію гамільтонова графа (рис. 6, а), оскільки в графах такого типу вершин може бути дуже багато, а ребер порівняно мало).
Наведемо без доказу найвідомішу теорему.
Теорема (Дірак, 1952). Якщо зв'язному графі з п вершинами (при nі3) ступеня всіх вершин більше або рівні п/2, то граф гамільтонів.