Вода, газ та електрика

Генрі Дьюдені стверджував, що завдання старе, «багато старше електричного освітлення, або навіть газу».[1] Огляд історії завдання дав Кулман (англ. Kullman), який стверджує, що більшість публікацій посилаються на задачу як на «дуже давню».[2]

Граф ресурсів, він же граф Томсена або K_3,3

У заданих параметрах задача не має рішення  — не існує способу поєднати три котеджі з трьома різними ресурсами без схрещування підвідних шляхів. Більш загальні питання можуть мати іншу відповідь.

Завдання належить такій області математики, як топологічна теорія графів, яка вивчає вкладення графів в поверхні.

У більш формальних термінах теорії графів задача зводиться до питання: «чи є повний дводольний граф K_3,3 планарним?». Цей граф часто згадується як граф ресурсів[3] при посиланні на задачу. Також його називають графом Томсена.[4] Граф еквівалентний циркулянтному графу Ci₆ (1,3). Казимир Куратовський 1930 року довів, що K_3,3 НЕ планарний, а тому завдання не має рішення. Кулман, однак, зазначає: «Достатньо цікаво, що Куратовським не було опубліковано докладного доказу непланарності K.»[2]

Один із доказів неможливості знайти пласке вкладення K_3,3 розглядає деякі випадки, спираючись на теорему Жордана. Розглядаються різні можливості розташування вершин, відносно циклів довжини 4 і відображає, що вони несумісні з вимогою планарності.[5] Можливо також довести, що для будь-якого двочасткового планарного графу без мостів, який має n вершин і m ребер ${\displaystyle m\leqslant 2n-4}$, якщо скомбінувати формулу Ейлера (тут f — число граней планарного графу) зі спостереженням, що число граней не перевищує половини числа ребер (оскільки будь грань має не менше чотирьох ребер та кожне ребро належить рівно двом граням). У графі ресурсів, m= 9 і 2n-4 = 8, що порушує нерівність, так що граф ресурсів не може бути планарним.

Неможливість розв'язання задачі також виходить з двох важливих теорем про планарність графів, а саме з теореми Куратовського про те, що планарні графи — це в точності ті графи, які не містять підрозбиттів ні K_3,3, ні повного графу K₅, і з теореми Вагнера про те, що планарні графи — це в точності ті графи, які не містять ні K_3,3, ні повний граф K₅ як мінор графу.

Зображення K_3,3 з єдиним схрещуванням.

K_3,3 є тороідальним, що означає, що його можна вкласти в тор. У термінах трьох котеджів це означає, що завдання можна вирішити, зробивши дві дірки на площині (або сфері) та з'єднавши їх трубою. Це змінює топологічні властивості поверхні; використовуючи трубу, ми можемо під'єднати ресурси до всіх котеджів без схрещувань. Еквівалентним твердженням є рівність роду графу ресурсів одиниці, звідки випливає, що він не може бути вкладений в поверхню з родом менше одиниці. Поверхня з родом одиниця еквівалентна тору.

«Завдання про цегельний завод» Пала Турана задає більш загальне питання — знайти формулу мінімального числа схрещувань в малюнку повного дводольного графу K_a,b в термінах числа вершин a і b дводольного графу. Граф ресурсів K_3,3 можна намалювати з одним схрещуванням, але не з нулем, так що його число схрещувань дорівнює одиниці. Тороідальне вкладення графу K_3,3 можна отримати, провівши одне з перехресних ребер через трубу, як описано вище.

Граф ресурсів K_3,3 є, як і всі інші повні дводольні графи, добре покритим, що означає, що всі найбільші незалежні множини у цьому графі мають один і той же розмір. У цьому графі є лише дві найбільші незалежні множини — це частини дводольного графу, і очевидно, що вони рівні. K_3,3 — це один з семи 3-регулярних 3-зв'язкових добре покритих графів.[6]

Він також є графом Ламана, що означає, що він утворює мінімальну структурну жорсткість, коли він вкладається в площину (з перетинами). Це приклад мінімального графу Ламана, в той час як інший не планарний граф, K₅, не є мінімально жорстким.

• Задача про три склянки

• Weisstein, Eric W. Utility graph(англ.) на сайті Wolfram MathWorld.
• The Utilities Puzzle explained and 'solved' at Archimedes-lab.org
• 3 Utilities Puzzle at cut-the-knot
• Jim Loy. Proof That the Impossible Puzzle is Impossible.