Q: Завдання Ейлера. Три сусіда посварилися. Всі три мають по колодязя. Чи можливо прокласти стежки від будинку кожного сусіда до кожного колодязя так, щоб ці стежки не перетиналися?
A: У двомірному просторі неможливо поєднати три колодязя стежками так, щоб вони не перетиналися.
Теорема має непросредственное ставлення до теорії графів. Рішень за 300 років, що минули з формулювання завдання про колодязі, знайшли не одне - ось пара:
1. полягає в розгляді трьох варіантів, які залишаються після проведення 8ми стежок.
Рішення: Позначимо вершини графа А, B, C, 1, 2, 3 відповідно трьом будиночків і криниць формулювання завдання, і доведемо, що дев'яту дорогу - ребро графа, не перетинаються інші ребра, провести неможливо.
Проведені в графі ребра А-1, А-2, A-3 і В-1, В-2, В-З (відповідні доріжках від будиночків А і В до всіх трьох криниць). Побудований таким чином граф розділив робочу площину на 3 області: X, У, Z. Вершина B, в залежності від її розташування на площині, потрапляє в одну з таких 3х областей. Якщо розглянути кожен з 3х випадків «попадання» вершини B в одну з областей X, Y, Z - то побачите, що всякий раз якась одна з вершин графа 1, 2 або 3 (або один з колодязів "сусідів") вийде недоступною для побудови дороги від вершини B (т. е. неможливо буде побудувати одне з ребер B1, B2 або B3. яка не перетнуло б уже наявні в графі ребра). Відповідно - відповідь - не можна.
2.основиваясь на співвідношенні того ж Ейлера для багатокутників
Рішення: Припустимо, що ці 9 стежок можна прокласти. Позначимо будиночки точками H1, H2, H3, колодязі - точками C1, C2, C3. Кожну точку-будинок з'єднаємо з кожною точкою-колодязем. Вийшли ребра (графа) в кількості дев'яти штук, які попарно не перетинаються. Такі ребра утворюють на розглянутій площині завдання багатокутник, поділений на менші багатокутники. Для такого розбиття має виконуватися відоме співвідношення Ейлера B - P + G = 1. Додаємо до досліджуваних граней ще одну - зовнішню частину площині щодо рассматріваемомого багатокутника. Тоді співвідношення Ейлера набуде вигляду B - P + G = 2, причому B = 6 і P = 9. Виходить, G = 5. Кожна з п'яти граней має принаймні чотири ребра, так як, за умовою задачі Ейлера, жодна з доріжок не повинна безпосередньо з'єднувати два колодязя або два будинки. Так як будь-який ребро лежить рівно в 2-х гранях, то кількість ребер графа має бути не менше 5 * 4/2 = 10. Це суперечить умові вихідної задачі, за яким їх число дорівнює дев'ять. Отримане протиріччя доводить, що відповідь в задачі про 3х колодязях Ейлера негативний.
Рішення "можна" виходить при переході в тривимірний простір, або при згадуванні того факту, що Земля - кругла, або "охолодження" високого рівня води в одному з колодязів і припущення що по льоду можна ходити, або при "будівництві" мостів, тунелів і т.п.