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

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

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

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

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

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

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

Свойства K _3,3

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

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

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

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

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

Примечания

Ссылки

• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .
• //
• // cut-the-knot
• Jim Loy. Proof That the Impossible Puzzle is Impossible. 20 января 2007 года.