Задача про сім кенігсберзьких мостів

Люди, що жили у XVIII столітті в місті Кенігсберзі, довго розв'язували одну загадку: містом тече річка Прегола, яка утворює два острови. Через цю річку на острови ведуть загалом сім мостів. Чи можна під час однієї недільної прогулянки пройти всіма мостами, але кожним рівно один раз? Подивімося, як мости стояли через річку:

Чи можна почати прогулянку десь у певному місці й пройти всіма мостами рівно по одному разу? Можемо спробувати: почнемо внизу ліворуч і підемо вгору, а потім поступово праворуч, ось так:

Бачимо, що ми пройшли шість із семи мостів, один міст ми оминули. Можна спробувати інший шлях…

Знову пройдено лише шість із семи мостів нашого Кенігсберга. Схоже на те, що за одну прогулянку пройти кожним мостом рівно один раз неможливо. Одного дня на цю проблему натрапив відомий математик Леонард Ейлер. Що там відомий — Ейлер був справжньою легендою математики, на його честь навіть названо число Ейлера. Ейлер вирішив, що цю загадку розгризе. Почав із того, що позначив окремі острови, або частини міста, до яких і з яких вели мости:

Ейлер міркував так: якщо на якийсь острів веде парна кількість мостів, ми можемо пройти всіма цими мостами за одну прогулянку, де б не почали. Простіше кажучи, одним мостом на острів приходимо, другим ідемо — кількість мостів, якими ще треба пройти, зменшилася на два. Щоб прийти одним мостом на острів і піти другим, потрібні два мости. Якщо на острів веде шість мостів, ми відвідаємо острів тричі. Наприклад, уявімо, що на острів B ведуть чотири мости, ось так:

Тоді за одну недільну прогулянку ми можемо пройти всіма мостами, де б не почали. Спробуй! На рисунку позначено один із шляхів. Тепер уявімо, що на острів B веде ще один міст з острова D:

Бачимо, що шлях, який ми обрали, не дає змоги пройти всіма мостами рівно по одному разу. Довелося б якимось мостом повернутися на острів B, а потім перейти на острів D. Але можна обрати інший шлях. Можемо почати прогулянку на острові B, і тоді вдасться пройти всіма мостами рівно по одному разу:

Прогулянку ми почали на острові B, пішли вгору на територію A, потім мостом назад на B, на територію C, знову на острів B і нарешті на острів D. Отже, якщо почати з острова, до якого веде непарна кількість мостів, можна пройти всіма його мостами рівно по одному разу. Або можна піти зовсім навпаки — почати на острові D, а закінчити на острові B.

Так Ейлер помітив, що для проходу всіма мостами рівно по одному разу має виконуватися одна з умов: або на всіх островах парна кількість мостів, або є два острови з непарною кількістю мостів — на одному з них з непарною кількістю мостів ми починаємо, а на другому закінчуємо. Усі інші острови мають мати парну кількість мостів. Якщо подивитися на початкові сім мостів у Кенігсберзі:

то бачимо, що на кожному острові непарна кількість мостів! Острів A має 3, B має 5, C має 3 і D теж має 3. Тому загадка не має розв'язку — пройти всіма сімома мостами рівно по одному разу за одну недільну прогулянку неможливо. Якби зруйнувати будь-який із мостів, загадка раптом отримала б розв'язок. Зруйнуймо, наприклад, один із мостів між островами B і C:

Бачимо, що в острова B одразу стало 4 мости, а в острова C — два мости. В островів A і D кількість мостів не змінилася. Тепер маємо два острови з парною кількістю мостів і два острови з непарною. Якщо почати прогулянку на одному з островів, що мають непарну кількість мостів, вдасться пройти всіма мостами рівно по одному разу. На рисунку ми почали на острові A, а закінчили на острові D.

Так Леонард Ейлер розв'язав ще одну славетну математичну задачу і, по суті, заклав основи того, що нині називають теорією графів, а на його честь граф, у якому можна пройти всіма ребрами рівно по одному разу, мовою теорії графів називають ейлеровим графом.