Вікіпедія

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

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

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

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

Історія ред.

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

Рішення ред.

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

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

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

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

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

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

Узагальнення ред.

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

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

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

Інші теоретичні властивості ред.

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

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

Див. також ред.

Примітки ред.

  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.

Посилання ред.

Отримано з https://uk.wikipedia.org/w/index.php?title=Вода,_газ_та_електрика&oldid=37388691