Проблема с тремя утилитами
Классическая математическая головоломка , известная как задача трех коммунальных услуг или иногда воды, газа и электричества, требует проведения непересекающихся соединений между тремя домами и тремя коммунальными предприятиями на плоскости . Ставя ее в начале 20 века, Генри Дьюдени писал, что это уже старая проблема. Это неразрешимая головоломка : невозможно соединить все девять линий, не пересекаясь. Версии задачи на неплоских поверхностях, таких как тор или лента Мёбиуса , или которые позволяют соединениям проходить через другие дома или коммуникации, могут быть решены.
Эту головоломку можно формализовать как проблему топологической теории графов , задав вопрос, имеет ли полный двудольный граф с вершинами, представляющими дома и коммунальные услуги, и ребрами, представляющими их соединения, граф, вложенный в плоскость. Неразрешимость головоломки соответствует тому, что это не планарный граф . Известно несколько доказательств этой невозможности, и они составляют часть доказательства теоремы Куратовского, характеризующей планарные графы двумя запрещенными подграфами, одним из которых является . Задача минимизации числа пересечений на рисунках полных двудольных графов известна какЗадача Турана о кирпичном заводе и минимальное число переходов равно одному.
представляет собой граф с шестью вершинами и девятью ребрами, часто называемый графом полезности в связи с проблемой. [1] Его также называют графом Томсена в честь химика 19-го века Юлиуса Томсена . Это хорошо покрытый граф , наименьший кубический граф без треугольников и наименьший неплоский граф с минимальной жесткостью .
Обзор истории проблемы трех полезностей дан Куллманом (1979) . Он заявляет, что большинство опубликованных ссылок на проблему характеризуют ее как «очень древнюю». [2] В самой ранней публикации, найденной Куллманом, Генри Дудени ( 1917 ) называет это «водой, газом и электричеством». Однако Дудени заявляет, что проблема «стара как мир… намного старше электрического освещения или даже газа ». [3] Dudeney также публиковал ту же головоломку ранее, в журнале Strand Magazine в 1913 году. [4] Конкурирующее требование приоритета принадлежит Сэму Лойду ., которого его сын процитировал в посмертной биографии как опубликовавшего задачу в 1900 г. [5]
Еще одна ранняя версия задачи предполагает подключение трех домов к трем колодцам. [6] Это формулируется аналогично другой (и решаемой) головоломке, в которой также участвуют три дома и три фонтана, причем все три фонтана и один дом касаются прямоугольной стены; головоломка снова включает в себя создание непересекающихся соединений, но только между тремя обозначенными парами домов и колодцев или фонтанов, как в современных головоломках с числовыми связями . [7] Головоломка Лойда «Сварливые соседи» аналогичным образом включает в себя соединение трех домов с тремя воротами тремя непересекающимися путями (а не девятью, как в задаче об коммуникациях); один дом и трое ворот находятся на стене прямоугольного двора, в котором находятся два других дома. [8]
