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

«Вода, газ та електрика» («задача про три ресурси» або «задача про три котеджі») — класична математична головоломка, яка може бути сформульована таким чином:

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

Завдання ставиться як абстрактне і не має відношення до реальних інженерних мереж.

Історія

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

Рішення

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

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

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

У більш формальних термінах теорії графів задача зводиться до питання: «чи є повний двочастковий граф K_3,3 планарним?». Цей граф часто згадується як граф ресурсів[3] при посиланні на задачу. Також його називають графом Томсена.[4] Граф еквівалентний циркулянтному графу Ci₆ (1,3). Казимир Куратовський 1930 року довів, що K_3,3 НЕ планарний, а тому завдання не має рішення. Кулман, однак, зазначає: «Доволі цікаво, що Куратовський не опублікував докладного доведення непланарності [${\displaystyle K_{3,3}}$].»[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 є, як і всі інші повні двочасткові графи, добре покритим^[en], що означає, що всі найбільші незалежні множини у цьому графі мають один і той же розмір. У цьому графі є лише дві найбільші незалежні множини — це частини двочасткового графу, і очевидно, що вони рівні. K_3,3 — це один з семи 3-регулярних 3-зв'язкових добре покритих графів.[6]

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

Див. також

• Задача про три склянки
• Задача Турана про цегельний завод

Примітки

1. Dudeney, Henry (1917). Amusements in mathematics. Thomas Nelson.
2. Kullman, David (1979). "The Utilities Problem". Mathematics Magazine 52 (5). JSTOR 2689782.
3. Utility Graph [Архівовано 30 серпня 2018 у Wayback Machine.] from mathworld.wolfram.com
4. Brown, W. G. On graphs that do not contain a Thomsen graph. Canadian Mathematical Bulletin. Т. 9, № 0. с. 281—285. doi:10.4153/cmb-1966-036-2. Архів оригіналу за 20 квітня 2016. Процитовано 13 квітня 2016.
5. Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. ed.). New York: Dover Pub. ISBN 978-0-486-67870-2.. {{cite book}}: Перевірте значення |isbn=: недійсний символ (довідка)
6. Campbell, S. R.; Ellingham, M. N.; Royle, Gordon F. (1993), A characterisation of well-covered cubic graphs, Journal of Combinatorial Mathematics and Combinatorial Computing, 13: 193—212, MR 1220613.

Посилання

• Weisstein, Eric W. Utility graph(англ.) на сайті Wolfram MathWorld.
• The Utilities Puzzle [Архівовано 23 серпня 2018 у Wayback Machine.] explained and 'solved' at Archimedes-lab.org
• 3 Utilities Puzzle [Архівовано 29 серпня 2018 у Wayback Machine.] at cut-the-knot
• Jim Loy. Proof That the Impossible Puzzle is Impossible.