Теорія графів
ВСТУП
Спробуйте намалювати „заклеєний конверт” одним розчерком пера, тобто не відриваючи ручки від паперу й не проводячи двічі один і той самий відрізок. Такого роду запитання з давніх-давен цікавили математиків.
Зрозуміло, часто трапляється, що потреби практики підштовхують розвиток математики. Яскраві приклади цього – теорії, створені М. Келдишем для авіаконструкторів. Досить часто поняття математики виникали з необхідності – так було з векторами, логарифмами, тригонометрією... Проте, нерідко математика є відірваною від реального життя, а тоді раптом виявляється, що в хащі неправдоподібності її все таки не занесло. Хрестоматійним прикладом є вчення про графи.
Декілька століть тому математиків, які досліджували дану проблему називали диваками і мрійниками. А сьогодні сучасні досягнення теорії графів використовуються у різних галузях знань, що підкреслює наукову та практичну значимість цієї проблеми.
В наш час теорія графів є дуже актуальною. Вона використовується у багатьох сферах людського життя для опису взаємозв’яків між об’єктами, процесами чи подіями. Граф – це досить чітка модель для вивчення окремих явищ навколишньої дійсності. Тому темою моєї дипломної роботи є «Графи, деякі їх застосування та методика вивчення у шкільному курсі математики», адже теорія графів має не тільки наукову, а й практичну цінність. Останнім часом зв’язані з графами методи досліджень використовуються не тільки в математиці, але і у фізиці, хімії, біології, географії та інших науках.
Отже, об’єктом дослідження в даній дипломній роботі виступає теорія графів, основні теореми теорії графів та їх застосування при розв’язуванні задач.
Метою мого дослідження було ознайомитися з історією виникнення теорії графів, дати основні означення та теореми графів та показати їх роль для сучасної науки і техніки.
Предметом дослідження є застосування теорії графів при розв’язанні завдань різних видів, вивчення елементів теорії графів у загальноосвітній школі, а саме на спецкурсах з математики у 10-11-х класах.
Дослідженням теорії графів займалися багато науковців сучасності, серед них: кандидат фізико-математичних наук, професор Р.М. Трохимчук, доктор фізико-математичних наук, професор Сущанський В.І., кандидат фізико-математичних наук, доцент Шевченко В.П., кандидат фізико-математичних наук Зиков А. А., кандидат фізико-математичних наук Берж К., кандидат фізико-математичних наук Оре О..
РОЗДІЛ І. ВВЕДЕННЯ В ТЕОРІЮ ГРАФІВ
1.1 Основні поняття та означення
Граф - фігура, що складається з точок (вершин) і відрізків, що сполучають деякі з цих вершин. Сполучаючі відрізки можуть бути прямолінійними або криволінійними; вони називаються ребрами графа.
Основні елементи геометричних фігур, які застосовуються у теорії графів наведені на рис.1. та складаються з вершин графу, ребер графу та дуг графу.
Сполучення цих елементів визначає поняття: неорієнтований граф, орієнтований граф та змішаний граф.
Рис.1.1. Основні елементи графу (вершина, ребро, дуга)
Неорієнтований граф (неограф) — це граф (рис.1.2), для кожного ребра якого несуттєвий порядок двох його кінцевих вершин.
Рис.1.2. Неорієнтований граф (вершини та ребра)
Орієнтований граф (орграф) — це граф, для кожного ребра якого істотний порядок двох його кінцевих вершин. Орграф представлений на рис.1.3, ребра орграфа іноді називають дугами.
Рис. 1.3. Орієнтований граф
Рис. 1.4. Змішаний граф
Змішаний граф (рис.1.4) – це граф, що містить як орієнтовані, так і неорієнтовані ребра.
Кожної з перерахованих видів графа може містити одне або кілька ребер, у яких обидва кінці сходяться в одній вершині, такі ребра називаються петлями (рис.1.5).
Рис. 1.5. Змішаний граф з петлями
Рис. 1.6. Загальний випадок графа
У загальному випадку множина ребер може складатися із трьох непересічних підмножин: підмножини ланок, підмножини дуг і підмножини петель (рис.1.6).
Рис.1.7. Сутність геометричної конфігурації графа, в якому всі вершини можна обійти за маршрутом без перетинання ребер графу.
Наочно граф можна уявляти як геометричну конфігурацію ( див. рис.1.7), яка складається з точок (вершин графу 1,2,3,4,5,6) і ребер (ліній або відрізків №1(1-3), №2(3-4), №3(4-5), №4(3-5), №5(2-3), №6(2-5), №7(5-6), №8(6-2), №9(2-1), які сполучають деякі точки (вершини) за вибраним алгоритмом обходу вершин графу).
Дамо формальне математичне означення графа.
Нехай – деяка скінченна множина (множина вершин), – множина всіх невпорядкованих пар елементів (ребер або дуг графу) з множини вершин, .
Означення 1.1
Граф – пара множин. Множина – це множина вершин, множина, – це множина ребер. Якщо , то ми говоримо, що ребро сполучає вершину з вершиною ; інша термінологія – ребро і вершини та – інцидентні.
Означення 1.2.
Граф називається повним, якщо , тобто граф складається з максимально можливої кількості ребер, які попарно з’єднують точки його вершин (див.рис.1.8). Якщо множина містить вершин, то, очевидно , число ребер повного графа дорівнює .
Рис.1.8. Приклади повних графів
Означення 1.3.
Граф називається порожнім, якщо , тобто граф не має ребер (див.рис.1.9).
Рис.1.9. Приклад побудови 3-х вершинного графу з різною кількістю ребер (заповнення графу від «порожнього» до «повного»)
Природно виникає питання: скільки є різних графів з множиною вершин , якщо . Для цього доведемо наступну теорему.
Теорема 1.1.
Число усіх різних графів з вершинами дорівнює:
Доведення. Справді, граф повністю визначено, якщо вказано множину , яка є підмножиною . Множина містить елементів, тому число усіх її підмножин дорівнює .
Означення 1.4.
Вершини та графа інцидентні, якщо .
Означення 1.5.
Степенем вершини графа називається число вершин , які інцидентні вершині ( число відрізків, які виходять з вершини ) – див.рис.1.10.
Рис.1.10. Визначення степенів вершин графу по кількості ребер, що виходять із вершин
Означення 1.6.
Якщо , то вершина називається кінцевою вершиною графа . Якщо , то вершини називається ізольованою(див рис. 1.11)
Рис.1.11. Визначення кінцевих та ізольованих вершин графа
1.2 Історія теорії графів
Теорія графів багаторазово перевидається різними авторами при вирішенні різних прикладних завдань.
1. Задача про Кенігсберські мости. Обійти всі чотири частини суші, пройшовши по кожному мосту один раз, і повернутися у вихідну точку (рис. 1.12). Це завдання було вирішене Ейлером в 1736році.
Рис. 1.12. Ілюстрація до задачі про Кенігсберські мости
2. Задача про три будинки і три криниці. Є три будинки і три криниці. Провести від кожного будинку до кожного колодязя стежку так, щоб стежки не перетиналися (рис. 1.13). Це завдання було вирішене Куратовським в 1930 році.
Рис.1.13. Ілюстрація до задачі про три будинки і три криниці
3. Завдання
про чотири кольори. Будь-яку
карту на площині розфарбувати чотирма
кольорами так, щоб ніякі
дві сусідні області не були зафарбовані
одним кольором (рис. 1.14).
.
Рис. 1.14. Ілюстрація до задачі про чотири кольори
1.3 Операції над графами
Введемо наступні операції над графами:
1. Граф G(X,W) є сумою (об’єднанням) графів G (X1 , W1), ... , G(Xk , Wk), якщо , X= , W=.
Ця сума називається прямою, якщо X i X j=, ij.
2. Граф G(X,W) називається зв’язним, якщо будь-які дві вершини xi та xj (xi X, xj X) сполучені ланцюгом з початком в xi і кінцем в xj. З симетрії випливає, що в цьому випадку і вершина xj сполучена з вершиною xi.
3. Перетином і різницею графів G (X1, W1) і G (X2 , W2) з однаковими множинами вершин називаються графи G’( X, W1W2) і G”(X , W1 \W2) відповідно; позначаються G’ =G1 G2 і G1 \ G2 = G”.
4. Доповненням графа G(X,W) називається граф = (X , M2 \ W ); отже, граф має ту саму множину вершин X, що й граф G, а будь-які дві вершини графа , суміжні тоді і тільки тоді, коли вони несуміжні в G.
5. Граф G(X,W) називається двочастковим, якщо існує таке розбиття множини його вершин X на дві підмножини (частки) X1 і X2, що кінці будь-якого ребра графа G належать різним часткам.
6. Двочастковий граф називається повним двочастковим графом, якщо будь-які дві його вершини, що належать різним часткам, є суміжними. Повний двочастковий граф, частки якого X1 і X2 складаються з n і m вершин відповідно, позначається Kn, m.
7. Операція вилучення вершини x із графа G(X,W) полягає у вилученні з множини X елемента x , а з множини W – усіх ребер, інцидентних x.
8. Операція вилучення ребра w з графа G(X,W) полягає у вилученні елемента w з множини W . При цьому всі вершини зберігаються.
РОЗДІЛ ІІ. Застосування теорії графів до розв’язування задач
2.1 Задача про призначення на посаду
Нехай є кілька різних вакантних посад і група людей, які бажають їх зайняти, причому кожен із претендентів достатньо кваліфікований для кількох, але не для всіх наявних посад.
Чи можна кожному з цих людей надати одну з тих посад, які йому підходять?
Ми можемо знову проілюструвати цю задачу за допомогою деякого графа, що в даному випадку виглядає особливо. Як уже сказано, є певна група людей, яку ми позначимо як М і деяка множина посад Р. Будуємо граф, проводячи ребра(М,Р), що з’єднує кожну людину М з тими посадами Р, які він може зайняти. На цьому графі не буде ребер, що з’єднують між собою дві вершини М чи Р, тому такий граф має вигляд: (мал. 2.1)
мал. 2.1
Завжди знайти підходяще місце для кожного претендента ми не можемо: для цього необхідно, щоб посад було не менше ніж претендентів. Але цього недостатньо.
Нехай, наприклад, група претендентів складається з двох столярів і людини, яка може працювати і столяром і сантехніком, і для них є чотири посади: одне місце столяра і три місця сантехніка. Тоді, очевидно, один столяр залишиться без роботи, хоча в даному випадку місць більше ніж претендентів, і хоча серед претендентів є люди що можуть працювати на двох посадах.
Припустимо, що загальна кількість претендентів - N. Для розв’язання задачі повинна виконуватись наступна умова:
Яку б групу із k чоловік, k=1,2,...,N, ми не взяли, повинно бути принаймні k посад, кожну з яких може займати хоча б один із наших претендентів.
Наприклад, якщо одна з осіб є столяром, а друга - одночасно і столяром, і сантехніком, і якщо є два місця сантехніка, то наша умова виконується при k=2, але не виконується при k=1; тому вказані люди не можуть одночасно влаштуватися на роботу.
Виділену умову ми коротко назвемо умовою різноманітності.
Висновок: вищенаведена задача може використовуватись працівниками служби зайнятості для правильного розміщення працівників на посади.
2.2 Інші формулювання
Ця задача про встановлення на графі деякої відповідності між його вершинами може мати і багато інших формулювань.
Припустимо, наприклад, що у нас є група із k хлопців і k дівчат. Дехто з них уже знайомі між собою, і виникає питання: в якому випадку можна розбити цих молодих людей на пари для танців так, щоб всі хлопці танцювали зі знайомими дівчатами?
Можна також змінити цю задачу: в маленькому селі є однакова кількість дорослих хлопців і дівчат; звичаєм не допускається, щоб хлопець одружувався на близькій родичці - сестрі, названій сестрі або двоюрідній сестрі. За якої умови для хлопця знайдеться наречена з цього села? Знову ми можемо розв’язати цю задачу за допомогою дводольного графа - в цьому випадку його вершини будуть з’єднані ребрами лише тоді, коли відповідні люди не є родичами.
А ось іще один варіант цієї задачі. В деякій школі є кілька гуртків: C1,C2,…,CN. Кожен із цих гуртків повинен мати старосту.
Для того щоб виключити перевантаження учнів, була поставлена умова, щоб жоден учень не був старостою більш, ніж одного гуртка. За якої умови це можливо?
Зрозуміло, що це можливо не завжди; якщо кількість гуртків в порівняно невеликій школі дужу велика, то це неможливо.
Щоб розв’язати цю задачу, ми знову звернемось до дводольного графа.
В цьому випадку одна множина вершин графа складатиметься із N гуртків, а інша множина вершин P - це множина всіх учнів школи. Ми проводимо ребро від гуртка С1 до учня р в тому випадку, якщо р є членом С1. При цьому умова різноманітності перетворюється в наступне: кожна група із k гуртків (при k = 1, 2,..., N) повинна включати щонайменше k різних учнів. Згідно вище вказаному - це та умова за якої гуртки можуть мати різних старост.
Якщо кількість гуртків занадто велика, не завжди легко довести справедливість умови різноманітності. Тому поставимо питання так: Чи можна вказати яке-небудь просте правило формування гуртків, що гарантує можливість вибору для них різних старост?
Це дійсно можливо. Для того щоб показати, що ми маємо на увазі, припустимо, що кожен гурток складається принаймні з п’яти учнів. Тоді на відповідному графі із кожної вершини множини С буде виходити принаймні 5 ребер. Для групи із k гуртків буде не менше 5k ребер, що виходять із відповідних вершин С до вершин із Р (мал. 2.2, де k = 4).
мал. 2.2
Тепер, якщо нам буде потрібно, щоб кожен учень брав участь не більше, ніж в п’яти гуртках, це означатиме, що ребра від k гуртків повинні йти принаймні до k вершин із Р, і, відповідно, умова різноманітності буде виконана.
Ці думки є повністю загальними, тож ми можемо сформулювати наступний результат.
Потрібно, щоб в кожному гуртку брало участь принаймні t учнів і щоб, окрім того, жоден учень не брав участь більше ніж в t гуртках. Тоді завжди можна знайти для цих гуртків різних старост.
Висновок: ця задача допоможе керівникам дитячих закладів при організації гурткової роботи.
2.3 Спортивні змагання
У всіх змаганнях доводиться стикатися з питанням про те, яким чином об'єднувати в пари окремих учасників. Іноді завдання виявляється простим: наприклад, якщо після кожного туру всі переможені вибувають із гри, то з учасників, що залишилися, утворюються нові пари, причому можливо, що один з них виявиться вільним від гри.
Це завдання дещо складніше
у разі "кругового турніру",
подібного до звичних шахових
турнірів. Тут кожен з учасників
повинен грати з кожним іншим,
і важливо заздалегідь
Цю ситуацію знову зручно змалювати за допомогою графа. Припустимо, що є N гравців, так що кожен з них грає N - 1 ігор з рештою учасників. Кожна гра як і раніше представляється ребром (A, B), що сполучає двох гравців – дві вершини A і В графа. Вся сукупність ігор представиться таким повним графом, що має N вершин, на малюнку2.3 зображено такий граф для N=6.
B кожному турі гравці якось об'єднуються в пари. Припустимо поки, що N парне, і це можна зробити. На графі таке об'єднання в пари відповідає вибору ½N несуміжних ребер – поодинці для кожної з N вершин. Для наступного туру можна вибрати нову множину ½N ребер і так далі до тих пір, поки всі ігри не будуть зіграні. На мал. 2.3 ребра помічені таким чином: ті, на яких стоїть число 1, відносяться до пар, що зустрічаються в першому турі, ті на яких стоїть цифра 2 - до пар, що зустрічаються в другому турі, і так далі.
мал. 2.3
При великій кількості гравців фактичне складання такої таблиці для всіх турів відразу стає досить трудомістким, якщо не вказаний який-небудь систематичний метод. Багато довідників по проведенню турнірів містять просторові таблиці. Об'єднання гравців в пари для різних кількостей гравців (N=6, 8, 10, 12 і т.д.). При складанні таблиці досить припускати як і раніше, що кількість гравців N парна. Якщо вона виявиться непарною, то завжди можна додати фіктивного гравця F, домовившись, що той, хто повинен грати з F, в цьому турі вільний від гри.
Опишемо простий і цілком загальний метод побудови турнірної таблиці для парної кількості гравців N. Позначимо гравців числами 1, 2,..., N і запишемо ці числа в їх природному порядку в першому рядку квадратної таблиці. B наступному рядку цієї таблиці ми хочемо поставити номери суперників цих гравців в першому турі матчу. Аналогічно в третьому рядку ми випишемо номери суперників тих же гравців 1,2..., N в другому турі і т. д. – до тих пір, поки всі гравці не зіграють один з одним. Ясно, що наша таблиця має бути такою, щоб всі можливі пари гравців зустрілися в ній в точності по одному разу.
Спосіб зробити це показаний в таблиці на мал. 2.4.
мал. 2.4
Щоб встановити суперника j-го гравця в k-м турі, досить поглянути на перетин j-го стовпця і (k + 1) - го рядка цієї таблиці.
Таблиця влаштована таким чином.
У першому рядку, як вже було сказано, перераховані гравці від 1 до N; ці ж числа ми поставили і в першому стовпці. Тепер на N - 1, що залишилися, місць кожного рядка ми ставимо числа від 2 до N в циклічному порядку по вибуванню. Перші ½N рядків починаються з парних чисел 2,4..., N і виглядають так:
Решта рядків починається з непарних чисел 3,5..., N - 1 і мають вигляд
Відмітимо, що в цій таблиці відсутнє число 1; з іншого боку, оскільки ніхто не грає проти самого себе, те число, що стоїть зверху стовпця, ніколи не повинне в цьому стовпці повторюватися. Ми усунемо обидва недоліки, якщо замінимо всі числа, що стоять на головній діагоналі, одиницями, як показано на мал 2.3. Тепер кожен гравець знайде під своїм номером номери гравців, з якими він грає в різних турах. Наприклад, гравець 4 грає з гравцем N - 1 в першому турі, з гравцем 2 в другому турі, з гравцем 1 в третьому турі, з гравцем 6 в четвертому турі і так далі і, нарешті, з гравцем N - 3 в (N - 1) - му турі.
Висновок: розв’язавши цю задачу, стає зрозуміло, що тепер організаторам спортивних змагань буде набагато простіше працювати, звісно, якщо вони прочитають та застосують подібний матеріал до вказаного.
2.4 Задача про сполучення міст
Зупинимося на задачі про засоби
сполучення, поставивши її спочатку формі
B тому окремому випадку, коли є всього три міста A, B, C, досить побудувати одну із ліній АВС, АСВ, ВАС, причому, якщо ВС - найдорожча лінія, то саме її і треба виключити, побудувавши дорогу ВАС.
Розглянемо тепер загальний випадок. Граф найбільш дешевої сполучаючої мережі має бути деревом, оскільки якби він містив цикл, можна було б видалити одну з ланок цього циклу і міста все ще залишилися б сполученими. Отже, для сполучення n міст потрібно побудувати n - 1 доріг.
Ми покажемо, що мережу мінімальної вартості можна побудувати, користуючись наступним простим правилом економічності. Перш за все, сполучаємо два міста з найбільш дешевою сполучаючою ланкою S1. На кожному з наступних кроків додаємо найдешевшу з ланок S, при приєднанні якої до вже побудованих ребер не утворюється ніякого циклу; якщо є декілька ланок однієї і тієї ж вартості, вибираємо будь-яке, з них.
Кожне дерево Т, побудоване таким чином, ми називатимемо економічним деревом. Його вартість дорівнює сумі вартостей окремих ланок:
с(Т) = с(S1) + с(S2) +... + с(Sn-1).
Нам треба довести, що жодне інше дерево В, що сполучає ті ж вершини, не може виявитись дешевше за економічне дерево Т. Нехай В - найдешевше дерево, що сполучає наші вершини, а Т - будь-яке економічне дерево. Припустимо, що ребра S1, S2... економічного дерева Т занумеровані в тому порядку, в якому вони приєднувалися при побудові Т. Якщо найдешевше дерево В не збігається з Т, то Т має щонайменше одне ребро,що не належить В. Нехай S1= (A, В) - перше таке ребро, і нехай Р(А, В) - ланцюг графа В, що сполучає вершини A і B (мал. 2.5).
мал. 2.5
Якщо ребро S1 додати до В, то граф В+S1 міститиме цикл С= S1+Р(А, В); а оскільки Т не має циклів, то цикл С повинен містити принаймні одне ребро, що не належить Т. Видаливши це ребро S1, ми отримаємо дерево
В’=В+S1 - S1’
з тією ж кількістю вершин, що і В, причому його вартість дорівнює
C(В’) =c(В) +с(S1) - с(S1’)
Оскільки В має найменшу можливу вартість, то
с(S1) ≥с(S1).
Але ребро було ланкою найменшої вартості, при додаванні якого до S2..., Sn-1 не виходить циклів.
Оскільки при додаванні ребра S1’ до цих ребер ми теж не отримаємо ніякого циклу, то
с(S1) = с(S1’),
і, отже, В’ теж має мінімальну вартість:
c(В) = c(В’).
Таким чином, ми знайшли інше дерево В’ мінімальної вартості, що має з економічним деревом Т на одне спільне ребро більше, ніж В. Ми можемо повторювати цю операцію до тих пір, поки остаточно не отримаємо сполучаюче дерево мінімальної вартості, яке співпадає з Т. Таким чином, Т, а також всі інші економічні дерева, дійсно мають мінімальну вартість.
Висновок: такі задачі спростять роботу будь-якому планувальнику, допоможуть вберегти скарбницю певної держави від надлишкових витрат, знайшовши найдешевший варіант сполучення міст комунікаціями.
2.5 Односторонній рух
Карта будь-якої мережі доріг або вулиць дає нам дещо спеціальний, але наочний приклад графа. На сучасному плані міста мають бути показані не тільки відносне розташування вулиць і їх перетину, але також і те, на яких вулицях є двосторонній потік транспорту, а на яких односторонній рух, причому в останньому випадку повинно бути вказано і напрям руху. При цьому знову виходить орієнтований або, частіше, змішаний граф, якщо односторонній рух встановлений не на всіх вулицях міста.
Втім, в попередньому випадку можна зробити граф орієнтованим за допомогою прийому, який часто використовується в теорії графів і полягає в заміні кожного неорієнтованого ребра двома орієнтованими ребрами, що сполучають ті ж самі вершини що мають протилежні напрями.
При розгляді одностороннього руху в місті виникають питання, цікаві і для загальної теорії графів.
Припустимо, що в місті вирішено ввести нові правила руху, згідно з яким рух по кожній вулиці стає одностороннім. Це було б, звичайно, неприйнятно, якби виявилось, що при цьому не завжди можна проїхати з одного місця в інше.
Запитується, за якої умови вулиці міста можна орієнтувати так, щоб з будь-якого пункту можна було проїхати в будь-який інший, не порушуючи правил руху по вулицях.
Відповідне завдання на мові теорії графів формулюється таким чином: за якої умови ребра графа G можна орієнтувати так, щоб для будь-якої пари його вершин знайшлася та вершина, що сполучає їх орієнтований ланцюг?
Ясно, що такий граф має бути зв'язним. Проте цього недостатньо.
Ребро S=(A, В) графа ми називатимемо зв'язуючим ребром, або перешийком, якщо воно є єдиним шляхом від A до B або назад.
Зв'язуюче ребро ділить всі вершини графа на дві множини: ті, в які можна прийти з A, не проходячи по ребру S, і ті, в які можна прийти з B, не проходячи по S. Граф в цьому випадку складається з двох частин G1 і G2 сполучених тільки ребром S (мал. 2.6 ).
мал. 2.6
На карті міста зв'язуюче ребро - єдина магістраль, що сполучає окремі частини міста. Воно може бути єдиним мостом через річку або єдиним залізничним тунелем. Ясно, що якби на такій магістралі було встановлено односторонній рух, то з однієї частини міста в іншу не було б проїзду.
Раніше ми називали кінцевим ребpом таке ребро S - (А, В), один з кінців якого, наприклад A, не належить ніякому іншому ребру графа (мал. 2.7).
мал. 2.7
Таке ребро теж повинне розглядатися як зв'язуюче, оскільки, окрім S, немає шляху, який сполучає A з B.
Можна вважати, що граф G1 (мал. 2.6) наче "стягнутий" в одну вершину A. На плані міста кінцеве ребро відповідає глухому куту; на якому теж не можна встановити односторонній рух, не блокуючи цим в'їзд в A або виїзд з A.
Якщо ребро S1= (А1, В1) Не є таким, що зв'язує, то знайдеться і інший шлях, що сполучає, А1 і В1 і що не проходить по S1 (мал. 2.8).
мал. 2.8
Тому таке ребро S1 називається циклічним ребром. Отже, на графі є ребра двох типів - циклічні і зв'язуючі.
Тепер ми можемо довести наступну теорему.
ТЕОРЕМА. Якщо G - неорієнтований зв'язний граф, то завжди можна так орієнтувати циклічні ребра з G, залишивши зв'язуючі ребра неорієнтованими, щоб будь-яку пару вершин цього графа можна було з'єднати орієнтованим ланцюгом.
Для плану міста це твердження можна сформулювати таким чином: якщо залишити двосторонній рух тільки на мостах (за умови, що даний міст є єдиним мостом через річку) і на глухих кутах, то на решті всіх вулиць можна встановити односторонній рух так, щоб транспорт забезпечував зв'язок всіх частин міста.
Ми можемо довести цю теорему, вказавши спосіб відповідного орієнтування графа. Почнемо з того, що виберемо в G довільне ребро S= (А,B). Якщо S - зв'язуюче ребро, воно залишиться двостороннім; і тоді можна буде перейти від В до А і назад уподовж S (мал. 2.9).
мал. 2.9
Якщо S - циклічне ребро, то воно входить в деякий цикл С і тоді на всіх ребрах циклу С можна встановити циклічну орієнтацію; ясно, що з будь-якої вершини G можна перейти до будь-якої іншої, прямуючи вказаним на ребрах напрямом (мал. 2.10).
мал. 2.10
Цей процес можна продовжити. Припустимо, що ми вже орієнтували деяку частину H даного графа так, що з будь-якої вершини графа H можна пройти в будь-яку іншу його вершину з дотриманням правил одностороннього руху. Оскільки граф G є зв'язним, то або N збігається з усім графом G, або знайдеться ребро S = (А, В), що "торкається" Н, тобто таке, що воно не належить H, але одна з його вершин, скажемо A, належить Н.
Якщо S - зв'язуюче ребро АВ, то, як ми вже умовилися, воно залишається двостороннім. Тоді для будь-якої вершини X графа H можна знайти орієнтований ланцюг R, що сполучає X з A, а, значить (через ребро S), і з B. Назад, від вершини B через ребро S можна перейти до A, а потім - по орієнтованому ланцюгу Z - від А до X (мал. 2.11).