Введение

Математическая головоломка об избежании пересечений

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

История

В обзоре истории проблемы трех коммуникаций он утверждает, что большинство опубликованных ссылок на проблему характеризуют ее как "очень древнюю". В самой ранней публикации, найденной Кульманом, она называется "вода, газ и электричество". Однако, по словам Дюденея, проблема "стара, как горы, намного старше электрического освещения или даже газа". Дюденей также опубликовал ту же головоломку ранее, в журнале The Strand Magazine в 1913 году. Конкурирующее право на первенство принадлежит Сэму Ллойду, который был процитирован его сыном в посмертной биографии как опубликовавший проблему в 1900 году. Другая ранняя версия проблемы включает соединение трех домов с тремя колодцами. Она описывается аналогично другой (и разрешимой) головоломке, которая также включает три дома и три фонтана, причем все три фонтана и один дом касаются прямоугольной стены; головоломка снова включает создание непересекающихся соединений, но только между тремя заданными парами домов и колодцев или фонтанов, как в современных головоломках Numberlink. Головоломка Ллойда "Сварливые соседи" аналогично включает соединение трех домов с тремя воротами тремя непересекающимися путями (а не девятью, как в проблеме с коммуникациями); один дом и три ворота находятся на стене прямоугольного двора, который содержит в себе два других дома. Помимо проблемы трех коммуникаций, этот граф появляется в публикациях конца XIX и начала XX века как в ранних исследованиях структурной жесткости, так и в теории химических графов, где Юлиус Томсен предложил его в 1886 году для тогдашней неопределенной структуры бензола. В честь работы Томсена граф иногда называют графом Томсена.

Нерастворимость

Как обычно представляется (на плоской двухмерной плоскости), решение головоломки с коммуникациями "нет": нет способа установить все девять соединений, не допустив пересечения линий. Иными словами, граф не является планарным. Казимеж Куратовский в 1930 году установил, что граф непланарен, из чего следует, что задача не имеет решения. Однако, отмечается, что "любопытно, что Куратовский не опубликовал детального доказательства того, что [ ] не является планарным". Одно из доказательств невозможности планарного вложения использует анализ случаев, основанный на теореме о кривой Жордана. В этом решении рассматриваются различные варианты расположения вершин относительно 4 циклов графа и показывается, что ни один из них не совместим с планарным вложением. Альтернативно, можно доказать, что любой связный двудольный планарный граф с вершинами и ребрами имеет , комбинируя формулу Эйлера (где – число граней планарного вложения) с наблюдением о том, что число граней не превышает половины числа ребер (вершины, окружающие каждую грань, должны чередоваться между домами и коммуникациями, поэтому каждая грань имеет как минимум четыре ребра, и каждое ребро принадлежит ровно двум граням). В графе с коммуникациями и , следовательно, в графе с коммуникациями утверждение неверно, поскольку он не удовлетворяет этому неравенству, и, следовательно, граф с коммуникациями не может быть планарным.

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

является тороидальным графом, что означает, что его можно вложить без пересечений на тор, поверхность рода один. Эти вложения позволяют решать варианты головоломки, в которых дома и компании изображены на кофейной кружке или другой подобной поверхности, а не на плоской плоскости. На торе даже хватает дополнительной свободы, чтобы решить вариант головоломки с четырьмя домами и четырьмя предприятиями коммунального хозяйства. Аналогично, если головоломка с тремя предприятиями коммунального хозяйства представлена на листе прозрачного материала, её можно решить, скрутив и склеив лист, чтобы образовать ленту Мёбиуса. Другой способ изменить правила головоломки, который сделает её разрешимой, предложенный Генри Дюденеем, – разрешить линиям коммунальных услуг проходить через другие дома или предприятия коммунального хозяйства, кроме тех, к которым они подключены.

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

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

Жесткость

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

Другие графологические свойства

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

Обобщения

Две важные характеристики планарных графов, теорема Куратовского, утверждающая, что планарные графы — это именно те графы, которые не содержат ни K₅, ни K₃,₃ в качестве подграфа, полученного делением ребер, и теорема Вагнера, утверждающая, что планарные графы — это именно те графы, которые не содержат ни K₅, ни K₃,₃ в качестве минора, используют и обобщают непланарность. "Задача о кирпичной фабрике" Пала Турана в более общем виде ставит вопрос о формуле для минимального числа пересечений на чертеже полного двудольного графа Kₘ,ₙ в зависимости от числа вершин m и n на двух сторонах двудольного графа. Граф полезности может быть нарисован только с одним пересечением, но не без пересечений, поэтому его число пересечений равно единице.