Домики и колодцы

Задача о трёх домиках и трёх колодцах — классическая математическая головоломка: проложить от каждого из трёх колодцев к каждому из трёх домиков непересекающиеся тропинки. Формулировка задачи приписывается Эйлеру. В современной литературе иногда встречается в следующей форме: возможно ли к каждому из трёх домиков проложить без пересечений на плоскости трубы (рукава) от трёх источников — теплоснабжения, газоснабжения и водоснабжения («вода, газ, теплоэнергия»).

Головоломка не имеет решения: топологическая теория графов, изучающая вложение графов в поверхности, даёт отрицательный ответ на вопрос о возможности изобразить соответствующий граф на плоскости без пересечений рёбер.

Полный двудольный граф $K_{3,3}$, представляющий задачу, называют «домики и колодцы», «коммунальный граф» (англ. utility graph), граф Томсена.

Формализация

Граф $K_{3,3}$

В терминах теории графов задача сводится к вопросу о планарности полного двудольного графа $K_{3,3}$. Этот граф эквивалентен циркулянтному графу $Ci_{6}(1,3)$. Казимир Куратовский в 1930 году доказал, что $K_{3,3}$ непланарен, а потому задача не имеет решения.

Одно из доказательств невозможности найти плоское вложение $K_{3,3}$ использует разбор случаев, привлекая теорему Жордана, рассматриваются различные возможности расположения вершин по отношению к циклам длины 4 и показывается, что они несовместимы с требованием планарности. Также можно показать, что для любого двудольного планарного графа без мостов с $n$ вершинами и $m$ рёбрами $m\leqslant 2n-4$, если скомбинировать формулу Эйлера $n-m+f=2$ (здесь $f$ — число граней планарного графа) с наблюдением, что число граней не превышает половины числа рёбер (поскольку любая грань имеет не менее четырёх рёбер и каждое ребро принадлежит ровно двум граням). При этом в графе $K_{3,3}$: $m=9$ и $2n-4=8$, что нарушает неравенство, так что этот граф не может быть планарным.

Неразрешимость задачи непосредственно следует из каждой из следующих важных теорем о планарных графах: теоремы Куратовского, согласно которой планарные графы — это в точности те графы, которые не содержат подграфов, гомеоморфных $K_{3,3}$ и полному графу $K_{5}$, и теоремы Вагнера о том, что планарные графы — это в точности те графы, которые не содержат ни $K_{3,3}$, ни $K_{5}$ в качестве минора, содержат в себе этот результат.

Свойства K_3,3

• Граф $K_{3,3}$ является, как и все другие полные двудольные графы, хорошо покрытым, что означает, что все наибольшие независимые множества в этом графе имеют один и тот же размер. В этом графе имеется только два наибольших независимых множества — это доли двудольного графа, и очевидно, что они равны. $K_{3,3}$ — это один из семи 3-регулярных 3-связных хорошо покрытых графов.

• Граф $K_{3,3}$ является ламановым, что означает, что он образует минимальную структурную жёсткость, когда он вкладывается в плоскость (с пересечениями). Это пример минимального ламанова графа, в то время как другой непланарный граф $K_{5}$ не является минимально жёстким.

Вариации и обобщения

Изображение $K_{3,3}$ на торе.

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

• $K_{3,3}$ является тороидальным, что означает возможность вложить его в тор. Эквивалентным утверждением является равенство рода графа $K_{3,3}$ единице, откуда следует, что он не может быть вложен в поверхность с родом меньше единицы. Поверхность с родом равным единице эквивалентна тору.
  • В частности головоломка про домики и колодцы имеет решение на поверхности кружки (такие кружки даже можно увидеть в продаже).

• Проблема Заранкевича, также известная как задача о кирпичном заводе Пала Турана, задаёт более общий вопрос — найти формулу минимального числа скрещиваний в рисунке полного двудольного графа $K_{a,b}$, зависящую от чисел $a$ и $b$ двух долей графа. Граф $K_{3,3}$ можно нарисовать всего с одним скрещиванием, но не с нулём, так что его число скрещиваний равно единице. Связана задача с тем, что во время войны Туран работал на кирпичном заводе, и от каждой печи к каждому складу была проведена узкоколейка. Вагонетки трудно толкать по скрещениям, отсюда и задача: как сделать, чтобы пересечений было поменьше.

Ссылки

• Weisstein, Eric W. Utility graph (англ.) на сайте Wolfram MathWorld.
• The Utilities Puzzle // Archimedes-lab.org
• 3 Utilities Puzzle // cut-the-knot
• Jim Loy. Proof That the Impossible Puzzle is Impossible. Архивировано 20 января 2007 года.