Основи теорії графів. Властивості ойлерових та гамільтонових графів (стр. 4 из 8)

Рис. 2.1. Схема мостів в Кенігзберзі [11]

Чотири частини міста зображені літерами

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

Рис. 2.2. Граф «Кенігзберзьких мостів» в ломи головці Ойлера

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

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

Це дало початок системному математичному підходу до побудови та вивчення властивості графів.

2.2 Основні поняття та означення ойлерових графів

Означення 2.1

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

Рис.2.3. Структура вершин та ребер в неорієнтованому ойлеровому графі (* - означено точку входу ойлерового ланцюга - циклу)

Означення 2.2

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

Рис.2.4. Структура вершин та ребер в неорієнтованому напівойлеровому графі (* - означено точку початку та кінця ойлерового ланцюгу)

Рис.2.5. Приклад неойлерового графу

Дослідивши структуру неойлерового графу, наведеного на рис.2.5, розг-лянемо необхідні і достатні умови для того, щоб граф був ойлеровим. Доведемо лему, яка далі буде грати істотну роль.

Лема 2.1

Якщо степінь кожної вершини графа

не менше двох , то граф містить цикл.

Доведення. Якщо в графі є петлі або кратні дуги, то твердження леми оче-видне. Тому надалі будемо припускати , що

є простим графом. Нехай – довільна вершина графа . Побудуємо по індукції маршрут

обираючи вершину

, суміжну з , а при обираючи вершину , суміж-ну з і відмінну від (існування такої вершини випливає з умови леми). Оскільки має скінченне число вершин, то врешті-решт ми прийдемо до вершини , з якої вийшли. Отримаємо цикл

Лема доведена.

Теорема 2.1 Для зв’язного графа

наступні умови еквівалентні:

1.

- ойлерів граф;

2. кожна вершина

має парний степінь;

3. множину ребер графа

можна розбити на прості цикли.

Доведення.

Нехай - ойлерів цикл графа . Будемо рухатись по циклу . Проходження кожної вершини збільшує степінь кожної вершини на 2, і оскільки кожне ребро входить в рівно раз , то будь-яка вершина має парний степінь .

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

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

З теореми 2.1 випливає наступна теорема.

Теорема 2.2. Зв’язний граф є ойлеровим тоді і тільки тоді, коли кожна його вершина має парний степінь.

.

Рис.2.6. Приклад ойлерового графу в теоремі 2.2

Доведення. Граф зображений на рисунку 2.6. є ойлеровим, оскільки

1. Степінь вершин А, F, D, C, Q= 4(парні);

2. Степінь вершин B, E = 2(парні);

3. Множина ребер цього графа є об’ єднання двох простих циклів

і .

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

Рис. 2.7. Приклад напівойлерового графу до теореми 2.3

Доведення. Граф зображений на рисунку 2.7. є нпівойлеровим, оскільки

1. Степінь вершин А, F, C= 4(парні);

2. Степінь вершин B = 2(парна);

3. Степінь вершин E,D = 3(непарна);

4. Ось один з можливих варіантів обходу

. Початковою точкою маршрута є точка , а кінцевою є точка .

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

Зауважимо , що згідно з «лемою про рукостискання» - число вершин непарного степеня є парним.