Проблема трех коммунальных услуг

«Вода, газ и электричество» перенаправляется сюда. Информацию об коммунальных услугах см. в разделе « Коммунальные услуги » . О романе «Канализация, газ и электричество» см. Мэтта Раффа .

Схема задачи трех утилит, показывающая линии на плоскости. Может ли каждый дом быть подключен к каждой коммунальной сети без пересечения линий подключения?

Два представления графа полезности, также известного как граф Томсена или $K_{3,3}$

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

Эту загадку можно формализовать как задачу топологической теории графов, задав вопрос, является ли полный двудольный граф $K_{3,3}$, где вершины представляют дома и коммунальные услуги, а ребра представляют их соединения, имеет граф, вложенный в плоскость. Невозможность головоломки соответствует тому факту, что $K_{3,3}$ не является плоским графом . Известны многочисленные доказательства этой невозможности, которые составляют часть доказательства теоремы Куратовского, характеризующей плоские графы двумя запрещенными подграфами, один из которых $K_{3,3}$. Вопрос о минимизации числа пересечений в рисунках полных двудольных графов известен как задача Турана о кирпичном заводе , и для $K_{3,3}$ минимальное количество пересечений - одно.

$K_{3,3}$ часто называют графом полезности . — это граф с шестью вершинами и девятью ребрами, который применительно к задаче Его также называют графиком Томсена в честь химика XIX века Юлиуса Томсена . Это хорошо покрытый граф , наименьший без треугольников кубический граф и наименьший непланарный минимально жесткий граф .

История

Обзор истории проблемы трех полезностей дан Куллманом (1979) . Он утверждает, что большинство опубликованных упоминаний о проблеме характеризуют ее как «очень древнюю». В самой ранней публикации, найденной Куллманом, Генри Дюдени ( 1917 ) называет это «водой, газом и электричеством». Однако Дьюдени утверждает, что проблема «стара, как мир... намного старше, чем электрическое освещение или даже газ ». Дюдени ранее публиковал ту же головоломку в журнале The Strand Magazine в 1913 году. Конкурирующее право на приоритет принадлежит Сэму Лойду , который, по словам его сына в посмертной биографии, опубликовал эту задачу в 1900 году.

Другая ранняя версия проблемы предполагает подключение трех домов к трем колодцам. Это формулируется аналогично другой (и разрешимой) головоломке, в которой также участвуют три дома и три фонтана, причем все три фонтана и один дом касаются прямоугольной стены; головоломка снова включает в себя создание непересекающихся связей, но только между тремя обозначенными парами домов и колодцами или фонтанами, как в современных головоломках с числовыми связями . Загадка Лойда «Ссорливые соседи» также предполагает соединение трех домов с тремя воротами тремя непересекающимися дорожками (а не девятью, как в задаче об коммунальных услугах); один дом и трое ворот находятся на стене прямоугольного двора, внутри которого находятся два других дома.

Как и в задаче трех полезностей, граф $K_{3,3}$ появляется в публикациях конца 19-го и начала 20-го веков, как в ранних исследованиях структурной жесткости, так и в публикациях конца 19-го и начала 20-го веков. и в теории химических графов , где Юлиус Томсен предложил ее в 1886 году для неопределенной на тот момент структуры бензола . В честь работы Томсена $K_{3,3}$ иногда называют графом Томсена.

Заявление

Задачу трех полезностей можно сформулировать следующим образом:

Предположим, что каждый из трех домов необходимо подключить к компаниям по водоснабжению, газу и электричеству, используя отдельную линию от каждого дома к каждой компании. Есть ли способ сделать все девять соединений так, чтобы ни одна из линий не пересекала друг друга?

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

Говоря более формальными терминами теории графов , проблема заключается в том, является ли полный двудольный граф $K_{3,3}$ представляет собой планарный граф . Этот граф имеет шесть вершин в двух подмножествах по три: по одной вершине для каждого дома и по одной для каждого коммунального предприятия. Он имеет девять ребер: по одному ребру для каждой пары дома с полезностью или, говоря более абстрактно, по одному ребру для каждой пары вершин в одном подмножестве и вершины в другом подмножестве. Планарные графы — это графы, которые можно нарисовать без пересечений на плоскости, и если бы такой рисунок можно было найти, он решил бы загадку трех полезностей.

Решения головоломок

Неразрешимость

Доказательство без слов : Один дом временно удален. Линии, соединяющие оставшиеся дома с коммуникациями, делят плоскость на три района. В каком бы регионе ни находился удаленный дом, заштрихованное таким же образом коммунальное предприятие находится за пределами этого региона. По теореме Жордана о кривой , соединяющая их линия должна пересекать одну из существующих линий.

Как это обычно представляется (на плоской двухмерной плоскости), решение головоломки полезности — «нет»: невозможно выполнить все девять соединений так, чтобы ни одна из линий не пересекала друг друга.Другими словами, график $K_{3,3}$ не является плоским. Казимеж Куратовский заявил в 1930 году, что $K_{3,3}$ является неплоским, откуда следует, что задача не имеет решения. Куллман (1979) , однако, утверждает, что «достаточно интересно, что Куратовский не опубликовал подробного доказательства того, что [ $K_{3,3}$ ] неплоский».

Одно из доказательств невозможности найти плоское вложение $K_{3,3}$ использует анализ случая, включающий теорему о кривой Жордана . В этом решении рассматриваются различные возможности расположения вершин относительно 4-циклов графа и показано, что все они несовместимы с плоским вложением.

В качестве альтернативы можно показать, что любой без мостов с двудольный планарный граф $V$ вершины и $E$ края имеет $E\leq 2V-4$ объединив формулу Эйлера $V-E+F=2$ (где $F$ — количество граней плоского вложения) с учетом того, что количество граней не превышает половины количества ребер (вершины вокруг каждой грани должны чередоваться между домами и инженерными коммуникациями, поэтому каждая грань имеет не менее четырех ребер, и каждая ребро принадлежит ровно двум граням). На графике полезности $E=9$ и $2V-4=8$ поэтому в графике полезности неверно, что $E\leq 2V-4$. Поскольку граф полезности не удовлетворяет этому неравенству, он не может быть плоским.

Изменение правил

Решение на ленте Мёбиуса

Решение на торе

Тор позволяет разместить до 4 инженерных сетей и 4 домов.

$K_{3,3}$ является тороидальным графом , что означает, что его можно вложить без пересечений на тор , поверхность рода один. Эти вложения решают версии головоломки, в которой дома и компании нарисованы на кофейной кружке или другой подобной поверхности, а не на плоской плоскости. На торе даже достаточно дополнительной свободы, чтобы решить версию головоломки с четырьмя домами и четырьмя инженерными коммуникациями. Аналогично, если головоломка о трех полезностях представлена ​​на листе прозрачного материала, ее можно решить, скрутив и склеив лист, чтобы получилась лента Мёбиуса .

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

Свойства графа полезности

Помимо головоломки полезности, тот же график $K_{3,3}$ возникает в нескольких других математических контекстах, включая теорию жесткости , классификацию клеток и хорошо покрытых графов , изучение чисел пересечений графов и теорию миноров графов .

Жесткость

График полезности $K_{3,3}$ является графом Ламана для , что означает, что почти всех размещений его вершин на плоскости нет способа непрерывно перемещать его вершины, сохраняя при этом все длины ребер, кроме как за счет жесткого движения всей плоскости, и что ни один из его охватов подграфы обладают одинаковым свойством жесткости . Это наименьший пример непланарного графа Ламана. Несмотря на то, что граф является минимально жестким, он имеет нежесткие вложения со специальным расположением вершин. Для вложений общего положения полиномиальное уравнение , описывающее все возможные размещения с одинаковой длиной ребра, имеет степень 16, что означает, что в общем случае может быть не более 16 размещений с одинаковой длиной. Можно найти системы длин ребер, для которых до восьми решений этого уравнения описывают реализуемые размещения.

графов

$K_{3,3}$ — граф без треугольников , в котором каждая вершина имеет ровно три соседа ( кубический граф ). Среди всех подобных графов он самый маленький. Следовательно, это (3,4)-клетка , наименьший граф, имеющий по три соседа на вершину и в котором самый короткий цикл имеет длину четыре.

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

Обобщения

Рисунок $K_{3,3}$ с одним переездом

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

» Пала Турана « Задача кирпичного завода в более общем плане требует формулу минимального числа пересечений на рисунке полного двудольного графа. $K_{a,b}$ по количеству вершин $a$ и $b$ по обе стороны двураздела. График полезности $K_{3,3}$ может быть нарисован только с одним пересечением, но не с пересечением нуля, поэтому номер его пересечения равен единице.

Внешние ссылки

• Головоломка с 3 утилитами в Cut-the-knot
• Загадка утилит, объясненная и «решенная» на Archimedes-lab.org
• Вайсштейн, Эрик В. , «График полезности» , MathWorld