Домики и колодцы
Задача о трёх домиках и трёх колодцах — классическая математическая головоломка: проложить от каждого из трёх колодцев к каждому из трёх домиков непересекающиеся тропинки. Формулировка задачи приписывается Эйлеру. В современной литературе иногда встречается в следующей форме: возможно ли к каждому из трёх домиков проложить без пересечений на плоскости трубы (рукава) от трёх источников — электроснабжения, газоснабжения и водоснабжения («вода, газ, электричество»).
Головоломка не имеет решения: топологическая теория графов, изучающая вложение графов в поверхности, даёт отрицательный ответ на вопрос о возможности изобразить соответствующий граф на плоскости без пересечений рёбер.
Полный двудольный граф [math]\displaystyle{ K_{3,3} }[/math], представляющий задачу, называют «домики и колодцы», «коммунальный граф» (англ. utility graph), граф Томсена[1].
Формализация
В терминах теории графов задача сводится к вопросу о планарности полного двудольного графа [math]\displaystyle{ K_{3,3} }[/math]. Этот граф эквивалентен циркулянтному графу [math]\displaystyle{ Ci_6(1,3) }[/math]. Казимир Куратовский в 1930 году доказал, что [math]\displaystyle{ K_{3,3} }[/math] непланарен, а потому задача не имеет решения[2].
Одно из доказательств невозможности найти плоское вложение [math]\displaystyle{ K_{3,3} }[/math] использует разбор случаев, привлекая теорему Жордана, рассматриваются различные возможности расположения вершин по отношению к циклам длины 4 и показывается, что они несовместимы с требованием планарности[3]. Также можно показать, что для любого двудольного планарного графа без мостов с [math]\displaystyle{ n }[/math] вершинами и [math]\displaystyle{ m }[/math] рёбрами [math]\displaystyle{ m \leqslant 2n - 4 }[/math], если скомбинировать формулу Эйлера [math]\displaystyle{ n - m + f = 2 }[/math] (здесь [math]\displaystyle{ f }[/math] — число граней планарного графа) с наблюдением, что число граней не превышает половины числа рёбер (поскольку любая грань имеет не менее четырёх рёбер и каждое ребро принадлежит ровно двум граням). При этом в графе [math]\displaystyle{ K_{3,3} }[/math]: [math]\displaystyle{ m = 9 }[/math] и [math]\displaystyle{ 2n - 4 = 8 }[/math], что нарушает неравенство, так что этот граф не может быть планарным.
Неразрешимость задачи непосредственно следует из каждой из следующих важных теорем о планарных графах: теоремы Куратовского, согласно которой планарные графы — это в точности те графы, которые не содержат подграфов, гомеоморфных [math]\displaystyle{ K_{3,3} }[/math] и полному графу [math]\displaystyle{ K_5 }[/math], и теоремы Вагнера о том, что планарные графы — это в точности те графы, которые не содержат ни [math]\displaystyle{ K_{3,3} }[/math], ни [math]\displaystyle{ K_5 }[/math] в качестве минора, содержат в себе этот результат.
Свойства K3,3
- Граф [math]\displaystyle{ K_{3,3} }[/math] является, как и все другие полные двудольные графы, хорошо покрытым, что означает, что все наибольшие независимые множества в этом графе имеют один и тот же размер. В этом графе имеется только два наибольших независимых множества — это доли двудольного графа, и очевидно, что они равны. [math]\displaystyle{ K_{3,3} }[/math] — это один из семи 3-регулярных 3-связных хорошо покрытых графов[4].
- Граф [math]\displaystyle{ K_{3,3} }[/math] является ламановым, что означает, что он образует минимальную структурную жёсткость, когда он вкладывается в плоскость (с пересечениями). Это пример минимального ламанова графа, в то время как другой непланарный граф [math]\displaystyle{ K_5 }[/math] не является минимально жёстким.
Вариации и обобщения
- [math]\displaystyle{ K_{3,3} }[/math] является тороидальным, что означает возможность вложить его в тор. Эквивалентным утверждением является равенство рода графа [math]\displaystyle{ K_{3,3} }[/math] единице, откуда следует, что он не может быть вложен в поверхность с родом меньше единицы. Поверхность с родом равным единице эквивалентна тору.
- В частности головоломка про домики и колодцы имеет решение на поверхности кружки (такие кружки даже можно увидеть в продаже).
- Проблема Заранкевича, также известная как задача о кирпичном заводе Пала Турана, задаёт более общий вопрос — найти формулу минимального числа скрещиваний в рисунке полного двудольного графа [math]\displaystyle{ K_{a,b} }[/math], зависящую от чисел [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math] двух долей графа. Граф [math]\displaystyle{ K_{3,3} }[/math] можно нарисовать всего с одним скрещиванием, но не с нулём, так что его число скрещиваний равно единице. Связана задача с тем, что во время войны Туран работал на кирпичном заводе, и от каждой печи к каждому складу была проведена узкоколейка. Вагонетки трудно толкать по скрещениям, отсюда и задача: как сделать, чтобы пересечений было поменьше.
Примечания
- ↑ 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.
- ↑ Результат является следствием более общего факта, установленного Куратовским — теоремы Куратовского; в русскоязычной литературе утверждается, что доказательство этого факта впервые найдено Понтрягиным в 1927 году, но не было своевременно опубликовано.
- ↑ Richard J. Trudeau. Introduction to Graph Theory. — Corrected, enlarged republication.. — New York: Dover Pub., 1993. — С. 68–70. — ISBN 978-0-486-67870-2.
- ↑ 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.
Ссылки
- 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 года.
 | Для улучшения этой статьи желательно: |