Классическая математическая головоломка , известная как задача трех коммунальных услуг или иногда воды, газа и электричества, требует провести непересекающиеся соединения между тремя домами и тремя коммунальными предприятиями на плоскости . Ставя эту проблему в начале 20 века, Генри Дюдени писал, что это уже старая проблема. Это неразрешимая головоломка : невозможно соединить все девять линий, не пересекая их. Могут быть решены версии проблемы на неплоских поверхностях, таких как тор или лента Мёбиуса , или которые позволяют соединениям проходить через другие дома или инженерные коммуникации.
Эту головоломку можно формализовать как задачу топологической теории графов, задав вопрос, имеет ли полный двудольный граф , вершины которого представляют дома и коммунальные услуги, а ребра — их соединения, граф, вложенный в плоскость. Невозможность головоломки соответствует тому факту, что граф не является плоским . Известны многочисленные доказательства этой невозможности, которые составляют часть доказательства теоремы Куратовского , характеризующей плоские графы двумя запрещенными подграфами, один из которых равен . Вопрос о минимизации количества пересечений на рисунках полных двудольных графов известен как задача кирпичной фабрики Турана , а минимальное количество пересечений равно одному.
— это граф с шестью вершинами и девятью ребрами, который применительно к задаче часто называют графом полезности . [1] Его также называют графиком Томсена в честь химика 19-го века Юлиуса Томсена . Это хорошо покрытый граф , наименьший кубический граф без треугольников и наименьший непланарный минимально жесткий граф .
Обзор истории проблемы трех полезностей дан Куллманом (1979). Он утверждает, что большинство опубликованных упоминаний о проблеме характеризуют ее как «очень древнюю». [2] В самой ранней публикации, найденной Куллманом, Генри Дьюдени (1917) называет это «водой, газом и электричеством». Однако Дьюдени утверждает, что проблема «стара, как мир... намного старше, чем электрическое освещение или даже газ ». [3] Дюдени также опубликовал ту же головоломку ранее, в журнале The Strand Magazine в 1913 году. [4] Конкурирующее право на приоритет принадлежит Сэму Лойду , которого его сын цитирует в посмертной биографии как опубликовавшего задачу в 1900 году. [ 3] 5]
Другая ранняя версия проблемы предполагает подключение трех домов к трем колодцам. [6] Это формулируется аналогично другой (и разрешимой) головоломке, в которой также участвуют три дома и три фонтана, причем все три фонтана и один дом касаются прямоугольной стены; головоломка снова включает в себя создание непересекающихся связей, но только между тремя назначенными парами домов и колодцами или фонтанами, как в современных головоломках с числовыми связями . [7] Загадка Лойда «Ссорливые соседи» также предполагает соединение трех домов с тремя воротами тремя непересекающимися дорожками (а не девятью, как в задаче об коммунальных услугах); один дом и трое ворот находятся на стене прямоугольного двора, внутри которого находятся два других дома. [8]
Как и в задаче трех полезностей, граф появляется в публикациях конца 19-го и начала 20-го веков как в ранних исследованиях структурной жесткости [9] [10] , так и в химической теории графов , где Юлиус Томсен предложил его в 1886 году для тогда еще неопределенная структура бензола . [11] В честь работы Томсена его иногда называют графом Томсена. [12]
Задачу трех полезностей можно сформулировать следующим образом:
Предположим, что каждый из трех домов необходимо подключить к компаниям по водоснабжению, газу и электричеству, используя отдельную линию от каждого дома к каждой компании. Есть ли способ сделать все девять соединений так, чтобы ни одна из линий не пересекала друг друга?
Проблема представляет собой абстрактную математическую головоломку, которая накладывает ограничения, которых не было бы в практической инженерной ситуации. Его математическая формализация является частью области топологической теории графов , которая изучает встраивание графов на поверхности . Важная часть головоломки, хотя она часто не указывается явно в неформальных формулировках головоломки, заключается в том, что дома, компании и линии должны быть размещены на двумерной поверхности с топологией плоскости , и что линиям не разрешается проходить через другие здания; иногда это достигается путем показа рисунков домов и компаний и просьбы нарисовать связи в виде линий на одном и том же рисунке. [13] [14]
В более формальных терминах теории графов проблема заключается в том, является ли полный двудольный граф плоским . Этот граф имеет шесть вершин в двух подмножествах по три: по одной вершине для каждого дома и по одной для каждого коммунального предприятия. Он имеет девять ребер: по одному ребру для каждой пары дома с полезностью или, говоря более абстрактно, по одному ребру для каждой пары вершин в одном подмножестве и вершины в другом подмножестве. Планарные графы — это графы, которые можно нарисовать без пересечений на плоскости, и если бы такой рисунок можно было найти, он решил бы загадку трех полезностей. [13] [14]
Как это обычно представляется (на плоской двухмерной плоскости), решение головоломки полезности — «нет»: невозможно выполнить все девять соединений без пересечения ни одной линии друг с другом. Другими словами, граф не является плоским. Казимеж Куратовский заявил в 1930 году, что задача неплоская, [15] из чего следует, что задача не имеет решения. Куллман (1979), однако, утверждает, что «достаточно интересно, что Куратовский не опубликовал подробного доказательства того, что [ ] непланарно». [2]
Одно из доказательств невозможности нахождения плоского вложения использует анализ случаев, включающий теорему Жордана о кривой . [16] В этом решении рассматриваются различные возможности расположения вершин относительно 4-циклов графа и показано, что все они несовместимы с плоским вложением. [17]
Альтернативно, можно показать, что любой двудольный планарный граф без мостов с вершинами и ребрами имеет свойство, комбинируя формулу Эйлера (где – количество граней плоского вложения) с наблюдением, что число граней не превышает половины числа ребра (вершины вокруг каждой грани должны чередоваться между домами и коммуникациями, поэтому каждая грань имеет как минимум четыре ребра, и каждое ребро принадлежит ровно двум граням). В графе полезности и , следовательно, в графе полезности неверно, что . Поскольку граф полезности не удовлетворяет этому неравенству, он не может быть плоским. [18]
является тороидальным графом , что означает, что его можно вложить без пересечений на тор , поверхность рода один. [19] Эти вложения решают версии головоломки, в которой дома и компании нарисованы на кофейной кружке или другой подобной поверхности, а не на плоской плоскости. [20] На торе даже достаточно дополнительной свободы, чтобы решить версию головоломки с четырьмя домами и четырьмя инженерными коммуникациями. [21] [5] Аналогично, если головоломка «Три полезности» представлена на листе прозрачного материала, ее можно решить после скручивания и склеивания листа, чтобы сформировать ленту Мёбиуса . [22]
Другой способ изменить правила головоломки, который сделал бы ее разрешимой, предложенный Генри Дюдени , — позволить линиям инженерных коммуникаций проходить через другие дома или коммуникации, кроме тех, которые они соединяют. [3]
Помимо головоломки о полезности, тот же граф встречается в нескольких других математических контекстах, включая теорию жесткости , классификацию клеток и хорошо покрытых графов , изучение чисел пересечений графов и теорию миноров графов .
Граф полезности является графом Ламана , что означает, что почти для всех размещений его вершин на плоскости нет способа непрерывно перемещать его вершины, сохраняя при этом все длины ребер, кроме как за счет жесткого движения всей плоскости, и что ни один из них не существует. его охватывающие подграфы обладают одинаковым свойством жесткости . Это наименьший пример непланарного графа Ламана. [23] Несмотря на то, что граф является минимально жестким, он имеет нежесткие вложения со специальным расположением вершин. [9] [24] Для вложений общего положения полиномиальное уравнение , описывающее все возможные размещения с одинаковой длиной ребер, имеет степень 16, что означает, что в целом может быть не более 16 размещений с одинаковой длиной. Можно найти системы длин ребер, для которых до восьми решений этого уравнения описывают реализуемые размещения. [24]
— граф без треугольников , в котором каждая вершина имеет ровно три соседа ( кубический граф ). Среди всех подобных графов он самый маленький. Следовательно, это (3,4)-клетка , наименьший граф, имеющий по три соседа на вершину и в котором самый короткий цикл имеет длину четыре. [25]
Как и все другие полные двудольные графы , это хорошо покрытый граф , что означает, что каждое максимальное независимое множество имеет одинаковый размер. В этом графе единственные два максимальных независимых множества являются двумя сторонами бираздела и имеют одинаковые размеры. является одним из семи 3-регулярных 3-связных хорошо покрытых графов. [26]
Две важные характеристики плоских графов, теорема Куратовского о том, что плоские графы - это в точности те графы, которые не содержат ни одного , ни полного графа в качестве подразделения, и теорема Вагнера о том, что плоские графы - это в точности графы, которые не содержат ни того, ни другого в качестве минора , используют и обобщить непланарность . [27]
« Задача кирпичного завода » Пала Турана в более общем смысле требует формулу минимального числа пересечений на рисунке полного двудольного графа с точки зрения числа вершин и на двух сторонах двудольного графа. График полезности можно нарисовать только с одним пересечением, но не с пересечением нуля, поэтому его число пересечений равно единице. [5] [28]
