Вода, газ и электричество (головоломка)

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Классическая математическая головоломка[en], известная как вода, газ и электричество или задача о (трёх) ресурсах, а также задача о трёх коттеджах, может быть сформулирована следующим образом:

Пусть имеется три коттеджа на плоскости (или сфере) и к каждому нужно подвести газ, воду и электричество. Использовать третье измерение не разрешается, как и не разрешается использовать подачу ресурса из другого коттеджа. Есть ли способ осуществить эти девять подключений без скрещивания подводящих путей?

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

История[править | править вики-текст]

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

Решение[править | править вики-текст]

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

Ответ на головоломку — нет. Невозможно соединить три коттеджа с тремя различными ресурсами без скрещивания подводящих путей. Более общие вопросы могут иметь другой ответ.[3]

Задача принадлежит такой области математики, как топологическая теория графов[en], которая изучает вложение графов в поверхность. В более формальных терминах теории графов, задача спрашивает, является ли полный двудольный граф K3,3 планарным. Этот граф часто упоминается как граф ресурсов при ссылке на задачу.[4]. Также его называют графом Томсена.[5] Граф эквивалентен циркулянтному графу Ci6(1,3). Казимир Куратовский в 1930 году доказал, что K3,3 не планарен, а потому задача не имеет решения. Кулман, однако, отмечает: «Достаточно интересно, что Куратовский не опубликовал подробного доказательства непланарности K3,3».[2]

Одно из доказательств невозможности найти плоское вложение K3,3 использует разбор случаев, привлекая теорему Жордана. При разборе случаев рассматриваются различные возможности расположения вершин по отношению к циклам длины 4 и показывается, что они несовместимы с требованием планарности[6]. Также можно показать, что для любого двудольного планарного графа без мостов с n вершинами и m рёбрами m \le 2n - 4, если скомбинировать формулу Эйлера n - m + f = 2 (здесь f — число граней планарного графа) с наблюдением, что число граней не превышает половины числа рёбер (поскольку любая грань имеет не менее четырёх рёбер и каждое ребро принадлежит ровно двум граням). В графе ресурсов, m = 9 и 2n − 4 = 8, что нарушает неравенство, так что граф ресурсов не может быть планарным.

Две важные теоремы о планарных графах, а именно Теорема Куратовского[en] о том, что планарные графы — это в точности те графы, которые не содержат подразбиений ни K3,3, ни полного графа K5, и Теорема Вагнера[en] о том, что планарные графы — это в точности те графы, которые не содержат ни K3,3, ни полный граф K5 в качестве минора[en], содержат в себе этот результат.

Обобщения[править | править вики-текст]

Изображение K3,3 с единственным скрещиванием.

K3,3 является тороидальным, что означает, что его можно вложить в тор. В терминах трёх коттеджей это означает, что задачу можно решить, сделав две дырки на плоскости (или сфере) и соединив их трубой. Это меняет топологические свойства поверхности; используя трубу, мы можем подсоединить ресурсы ко всем коттеджам без скрещиваний. Эквивалентным утверждением является равенство рода[en] графа ресурсов единице, откуда следует, что он не может быть вложен в поверхность с родом меньше единицы. Поверхность с родом единица эквивалентна тору.

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

Другие теоретические свойства[править | править вики-текст]

Граф ресурсов K3,3 является, как и все другие полные двудольные графы, хорошо покрытым[en], что означает, что все наибольшие независимые множества в этом графе имеют один и тот же размер. В этом графе имеется только два наибольших независимых множества — это доли двудольного графа, и очевидно, что они равны. K3,3 — это один из семи 3-регулярных 3-связных хорошо покрытых графов[7].

Он также является ламановым, что означает, что он образует минимальную структурную жёсткость[en], когда он вкладывается в плоскость (с пересечениями). Это пример минимального ламанова графа, в то время как другой непланарный граф, K5, не является минимально жёстким.

Примечания[править | править вики-текст]

  1. Henry Dudeney Amusements in mathematics. — Thomas Nelson, 1917.
  2. 1 2 David Kullman The Utilities Problem // Mathematics Magazine. — 1979. — В. 5. — Т. 52. — С. 299-302.
  3. Gas Water Electric Puzzle
  4. Utility Graph
  5. W. G. Brown On graphs that do not contain a Thomsen graph // Canadian Mathematical Bulletin. — 1966. — Т. 9. — С. 281–285. — DOI:10.4153/CMB-1966-036-2.
  6. Richard J. Trudeau Introduction to Graph Theory. — Corrected, enlarged republication.. — New York: Dover Pub., 1993. — С. 68–70. — ISBN 978-0-486-67870-2.
  7. S. R. Campbell, M. N. Ellingham, Gordon F. Royle A characterisation of well-covered cubic graphs // Journal of Combinatorial Mathematics and Combinatorial Computing. — 1993. — Т. 13. — С. 193–212.

Ссылки[править | править вики-текст]