WikiDer > Проблема трех коммунальных служб - Википедия

Three utilities problem - Wikipedia
Сюда перенаправляется «Вода, газ и электричество». Об утилитах см. Общественная полезность.
Проблема трех коммунальных служб. Можно ли подключить каждый дом к каждой инженерной сети без пересечения линий связи?
В самолете нужен один переход

Классический математическая головоломка известный как проблема трех коммунальных служб; в проблема трех коттеджей или иногда вода, газ и электричество можно сформулировать так:

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

Проблема представляет собой абстрактную математическую головоломку, которая накладывает ограничения, которых не было бы в практической инженерной ситуации. математический поле топологическая теория графов который изучает встраивание из графики на поверхности. В более формальном теоретико-графовый термины, проблема заключается в том, полный двудольный граф K3,3 является планарный.[1] Этот график часто называют график полезности применительно к проблеме;[2] его также называли Граф Томсена.[3]

История

Обзор истории проблемы трех коммунальных предприятий дает Куллман (1979). Он утверждает, что большинство опубликованных ссылок на проблему характеризует ее как «очень древнюю».[4]В самой ранней публикации, найденной Куллманом, Генри Дудени (1917) называет это «вода, газ и электричество». Однако Дудени заявляет, что проблема «стара как холмы ... намного старше, чем электрическое освещение, или даже газ".[5] Дудени также ранее опубликовал ту же головоломку в Журнал Strand в 1913 г.[6]

Другой ранний вариант проблемы - подключение трех домов к трем колодцам.[7]Он сформулирован аналогично другой (и решаемой) головоломке, которая также включает в себя три дома и три фонтана, причем все три фонтана и один дом касаются прямоугольной стены; головоломка снова включает в себя непересекающиеся соединения, но только между тремя обозначенными парами домов и колодцев или фонтанов, как в современных номер ссылка загадки.[8]

Математически проблема может быть сформулирована в терминах графические рисунки из полный двудольный граф K3,3. Этот график впервые появился в Хеннеберг (1908).[9]У него шесть вершин, разделенных на два подмножества по три вершины, и девять ребер, по одному для каждого из девяти способов спаривания вершины из одного подмножества с вершиной из другого подмножества. Проблема трех утилит заключается в том, является ли этот граф это планарный граф.[1]

Решение

Граф полезности, также известный как граф Томсена или K3,3

Как это обычно представляется (на плоской двумерной плоскости), решение служебной головоломки - «нет»: невозможно выполнить все девять соединений, если ни одна из линий не пересекает друг друга. Другими словами, график K3,3 не плоский. Казимеж Куратовски заявил в 1930 году, что K3,3 неплохо,[10] из чего следует, что проблема не имеет решения. Куллман, однако, заявляет, что «Интересно, что Куратовски не опубликовал подробного доказательства того, что [ K3,3 является] неплоским ».[4]

Одно из доказательств невозможности найти планарное вложение K3,3 использует анализ случая с участием Теорема Жордана. В этом решении исследуются различные возможности расположения вершин относительно 4-циклов графа и показано, что все они несовместимы с плоским вложением.[11]

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

Обобщения

K3,3 нарисовано только с одним пересечением.

Две важные характеристики плоских графов, Теорема Куратовского что планарные графы - это именно те графы, которые не содержат ни K3,3 ни полный график K5 как подразделение, и Теорема Вагнера что планарные графы - это именно те графы, которые не содержат ни K3,3 ни K5 как незначительный, использовать и обобщить непланарность K3,3.

Решение задачи трех утилит на торе.

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

Пал Туран"s"проблема кирпичного завода"в более общем плане спрашивает формулу для минимальное количество переходов на рисунке полный двудольный граф Kа,б по количеству вершин а и б по обе стороны двудольного. Граф полезности K3,3 может быть нарисован только с одним пересечением, но не с нулевым пересечением, поэтому его номер пересечения равен единице.[13]

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

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

Это также Граф Ламана, что означает, что он образует минимально жесткая система когда он вложен (с перемычками) в плоскость. Это наименьший пример непланарного графа Ламана, как и другой минимальный неплоский граф, K5, не является минимально жестким.

Рекомендации

  1. ^ а б Бона, Миклош (2011), Обзор комбинаторики: введение в теорию перечисления и графов, World Scientific, стр. 275–277, ISBN 9789814335232. Бона представляет загадку (в виде трех домов, соединенных с тремя колодцами) на стр. 275, и пишет на стр. 277, что это «эквивалентно проблеме рисования. K3,3 на ровной поверхности без пересечений ».
  2. ^ График полезности из mathworld.wolfram.com
  3. ^ а б Кокстер, Х. С. М. (1950), «Самодуальные конфигурации и регулярные графы», Бюллетень Американского математического общества, 56: 413–455, Дои:10.1090 / S0002-9904-1950-09407-5, МИСТЕР 0038078.
  4. ^ а б Куллман, Дэвид (1979), «Проблема коммунальных услуг», Математический журнал, 52 (5): 299–302, JSTOR 2689782.
  5. ^ Дудени, Генри (1917), «Проблема 251 - Вода, газ и электричество», Развлечения по математике, Томас Нельсон
  6. ^ Дудени, Генри (1913), «Сложности, с простыми головоломками для начинающих», Журнал Strand, т. 46, стр. 110.
  7. ^ "Головоломка", Успешное земледелие, т. 13, стр. 50, 1914 г.; "Загадка колодца и дома", Товарищ молодежи, т. 90 нет. 2, стр. 392 г., 1916 г..
  8. ^ «32. Загадка фонтана», Собственная книга фокусника или все искусство колдовства, Нью-Йорк: Дик и Фицджеральд, 1857, стр. 276.
  9. ^ Хеннеберг, Л. (1908), «Графическая статика дер старрен Кёрпер», Encyklopädie der Mathematischen Wissenschaften, 4.1, стр. 345–434. Как цитирует Кокстер (1950). См. В частности п. 403.
  10. ^ Куратовски, Казимеж (1930), "Sur le problème des Courbes Gaches en topologie" (PDF), Фонд. Математика. (На французском), 15: 271–283.
  11. ^ Трюдо, Ричард Дж. (1993), Введение в теорию графов (Исправленное, расширенное переиздание. Ред.), Нью-Йорк: Dover Pub., Стр. 68–70, ISBN 978-0-486-67870-2, получено 8 августа 2012
  12. ^ Каппрафф, Джей (2001), Связи: геометрический мост между искусством и наукой, Серии K&E о узлах и всем остальном, 25, World Scientific, стр. 128, ISBN 9789810245863.
  13. ^ Пах, Янош; Шарир, Миха (2009), «5.1 Переходы - проблема кирпичного завода», Комбинаторная геометрия и ее алгоритмические приложения: лекции по Алкале, Математические обзоры и монографии, 152, Американское математическое общество, стр. 126–127.
  14. ^ Кэмпбелл, S. R .; Эллингем, М.Н.; Ройл, Гордон Ф. (1993), "Характеристика хорошо покрытых кубических графов", Журнал комбинаторной математики и комбинаторных вычислений, 13: 193–212, МИСТЕР 1220613.

внешняя ссылка