Курсовая работа: Основи теорії графів. Властивості ойлерових та гамільтонових графів

Доведення.

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

А1

А0

Рис.2.11. Граф до теореми 2.5 [3]

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

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

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

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

Зауважимо, що описаний метод обходу графа може бути використаний для розв’язання задач , пов’язаних з пошуками маршрутів виходу з лабіринтів.

2.3 Приклади ойлерових графів

Приклад 2.1.Задача про призначення на посаду

Нехай є кілька рі?