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

Теорія графів з'явилася, коли математик Леонард Ейлер працював над подібними шляхами.

Ейлер написав статтю про сім мостів Кенігсберга, в якій довів, що неможливо пройти через міський перехід через кожен міст рівно один раз.

Натисніть на карту проблеми нижче, щоб дізнатися більше про неї.

Доказ:

Підрахунок всіх кінців всіх ребер дає те ж число, що і підсумовування всіх ступенів всіх вузлів, згоден?

Оскільки кожне ребро має 2 кінці, загальна кількість кінців усіх ребер має бути парною. (Додавання парних чисел дає парне число.)

Щоб скласти ступені всіх вузлів, потрібно скласти парні градуси, що дає парне число, і скласти непарні градуси.

Якби існувало непарне число вузлів непарного ступеня, то ця сума була б непарною, а потім парним + непарним = непарним, тому загальна кількість ступенів була б непарною. Але вона дорівнює загальній кількості всіх кінців всіх ребер і є парною. Тому кількість вузлів непарного ступеня не може бути непарним, воно повинно бути парним.

Наприклад, 1 є непарним числом, тому не існує графіка лише з 1 вузлом непарного степеня.

Якщо вузол має парний ступінь, тобто 2, 4, 6,... Ребра приєднуються до вузла, потім, коли ви прибуваєте до цього вузла, залишається непарне число невикористаних ребер, яке більше нуля, так що можна буде покинути цей вузол і піти далі. Якщо ступінь непарна, тобто 1, 3, 5,.. Ребра прикріплюються, то потрібно або почати шлях з цього вузла, або шлях закінчиться на цьому вузлі. Оскільки контур має лише 2 кінці, може бути лише 2 вузли з непарним степенем. Тому:

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

Щоб перевірити, чи є ребро мостом, потрібно почати з одного кінця ребра і відвідати всі сусідні вузли, всіх сусідів і так далі. Якщо один не потрапляє на іншу сторону краю, то ребро є містком. Такий повноцінний пошук всіх сусідів обходиться не дуже дорого. Але якщо це потрібно зробити до перетину кожного краю, то загальні зусилля великі. Повний алгоритм називається алгоритмом Флері, починаючи з 1883 року.

Більш ефективним алгоритмом є алгоритм Ієрхольцера (1873).

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

1) Після видалення всіх використовуваних ребер ступінь залишилися незадіяних ребер рівна для всіх вузлів.

Чому?

2) Повинен бути хоча б один вузол з використаними і невикористовуваними суміжними ребрами.

Чому?

Через 1) можна знайти цикл невикористовуваних ребер, починаючи і закінчуючи в цьому вузлі. Тому що 2) цей цикл може бути включений в перший шлях/цикл, коли він досягає цього вузла. Це вкладення циклів поки що невикористаних ребер повторюється доти, доки не будуть використані всі ребра, і тому ми маємо ейлерівський шлях або ейлерівський цикл, який використовує всі ребра.

Яка ціна цієї швидшої версії?

Приклад:

     2   4  
    / \ / \ 
   1---3---5

Нехай перший цикл буде 1-3-2-1. Вузол 3 зустрічається в цьому циклі і в невикористаному циклі 3-4-5-3. Вставляємо його в перший цикл і отримуємо цикл 1-3-4-5-3-2-1. Більше немає невикористаних ребер, тому алгоритм закінчується тут, ми знайшли цикл Ейлера.

Як можна вставити цикл за допомогою нашого інтерфейсу?

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