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