ірників математичних задач з розважальною математики містять задачі про лабіринти. Лабіринт складається з коридорів і їх перехресть. Отже, він може бути зображений графом, в якому ребра відповідають коридорах, а вершини - перехресті.
ейлеровимі графом повинен бути і план огляду будь-якої виставки, де уздовж приміщень виставки потрібно розставити покажчики обходу таким шляхом, щоб кожен експонат був оглянутий рівно один раз.
Рис.2.10 Застосування апарату ейлеровимі циклів при вирішенні завдань маршрут виставки »
Припустимо, що експонати розташовані обабіч шляху, що проходить по території виставки. Виявляється, що тоді, яким би не був відповідний граф (був би він тільки зв'язаним), можна провести відвідувача так, щоб кожен шлях був пройдений двічі - по одному разу в кожному напрямку (см.ріс.2.10).
Теорема 2.5. У зв'язкового графі існує орієнтований цикл, який проходить через ребро по одному разу в кожному з двох напрямків.
Доказ. Сформулюємо загальне правило побудови ланцюга, яке проходить уздовж всіх ребер графа в точності по одному разу в кожному напрямку. Почнемо з довільною вершини і пройдемо уздовж, зазначивши це ребро маленькою стрілкою в точці, яка показує обраний напрям. Потім переходимо послідовно до інших вершин. Одну й ту ж вершину можна відвідувати кілька разів. Кожен раз, потрапивши в якусь вершину, ми будемо ставити на відповідному ребрі стрілку вказує напрямок прибуття. Крім того, потрапляючи в якусь вершину вперше, ми відзначимо вхідне ребро, щоб потім його можна було відрізнити від інших.
рис.2.11. Граф до теореми 2.5.
Виходячи з вершини, ми завжди будемо вибирати ще невикористане напрямок: або ребро, по якому ми зовсім не проходили, або ребро позначено стрілкою, яка вказує на те, що ми на ньому вже були. Домовимося також, що тільки тоді, коли у нас немає вибору, ми використовуємо для виходу ребро, яке вперше відвідали.
Будемо продовжувати шлях до тих пір, коли це взагалі можливо. У кожній вершині є однакове число можливостей для входу і для виходу. Тому рух може закінчитися тільки в точці. Залишається перевірити, що у всіх вершинах всі ребра будуть пройдені в обох напрямках.
Для точки ясно- всі ребра, вихідні, будуть використані, оскільки в іншому випадку ми могли б рухатися далі; всі ребра, що входять, також будуть використані, тому що їх число дорівнює числу ребер, які виходять. Зокрема, ребро буде пройдено в обох напрямках. Але це означає, що всі ребра, які інцидентні, також будуть пройдені в обох напрямках. Колишнє ребро, яке входить в, повинно використовуватися для виходу тільки в останню чергу. Теж саме міркування можна застосуванням до наступному ребру і наступної вершини і так далі.
Отже, у всіх вершинах, які будуть досягнуті, всі ребра виявляться пройденими в обох напрямках. Оскільки наш граф є зв'язним, це означає, що він буде повністю пройденим.
Зауважимо, що описаний метод обходу графа може бути використаний для вирішення завдань, пов'язаних з пошуками маршрутів виходу з лабіринтів.
2.3 Приклади ейлеровимі графів
Приклад 2.1.Задача про призначення на посаду.
Нехай є кілька різних вакантних посад і група людей, бажаючих їх зайняти, причому кожен з претендентів достатньо кваліфікований для кількох, але не для всіх наявних посад.
Чи можна кожному з цих людей надати одну з тих посад, які йому підходять?
Ми можемо знову проілюструвати цю задачу за допомогою деякого графа, в даному випадку виглядає особливо. Як уже сказано, є певна група людей, яку ми позначимо як М і деяка безліч посад, Р. Будуємо граф, проводячи ребра (м, р), що з'єднують кожної людини м з тими посадами р, які він може зайняти. На цьому графі НЕ БУДЕ ребер, що з'єднують між собою дві вершини м або р, тому такий граф має вигляд, наведений на рис.2.12:
Рис.2.12 Граф для вирішення завдання про призначення на посаду
Завжди знайти підходяще місце для кожного претендента ми не можемо: для цього необхідно, щоб посад було не менше претендентів. Але цього недостатньо.
Нехай, наприклад, група претендентів складається з двох столярів і людину, яка може працювати і столяром і сантехніком, і для них чотири посади: одне місце столяра і три місця сантехніка. Тоді, очевидно, столяр залишиться без роботи, хоча в даному випадку місць більше претендентів, і хоча серед претендентів є люди які можуть працювати на двох посадах.
Припустимо, що загальна кількість претендентів - N. Для виконання завдання повинна виконуватися наступне умови:
Яку б групу з k людина, k=1,2, ..., N, ми не прийняли, повинно бути принаймні k посад, кожну з яких може займати хоча б один з наших претендентів.
