Из Википедии, бесплатной энциклопедии
  (Перенаправлено из задачи Трех дач )
Перейти к навигации Перейти к поиску
Сюда перенаправляется «Вода, газ и электричество». Для коммунальных услуг см. Коммунальные предприятия .
Проблема трех коммунальных служб. Можно ли подключить каждый дом к каждой инженерной сети без пересечения линий связи?
В самолете нужен один переход

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

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

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

История [ править ]

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

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

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

Решение [ править ]

Граф полезности, также известный как граф Томсена или K 3,3
Доказательство без слов : один дом временно удален. Линии, соединяющие оставшиеся дома с инженерными коммуникациями, делят плоскость на три области: желтый, красный и синий. В какой бы регион ни был помещен удаленный дом, утилита такого же цвета находится за пределами региона. Теорема Жордана утверждает, что соединяющая их линия должна пересекать одну из существующих линий.

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

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

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

Обобщения [ править ]

K 3,3 нарисована только с одним пересечением.
Решение задачи трех утилит на торе.

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

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

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

Другие свойства теории графов [ править ]

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

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

Ссылки [ править ]

  1. ^ a b Бона, Миклош (2011), Прогулка по комбинаторике: Введение в теорию перечисления и графов , World Scientific, стр. 275–277, ISBN 9789814335232. Бона представляет загадку (в виде трех домов, соединенных с тремя колодцами) на стр. 275 и пишет на стр. 277, что это «эквивалентно задаче рисования K 3,3 на плоской поверхности без пересечений».
  2. ^ Utility Graph с сайта mathworld.wolfram.com
  3. ^ Б Косетер, HSM (1950), "Автодуальные конфигурации и регулярные графы", Бюллетень Американского математического общества , 56 : 413-455, DOI : 10,1090 / S0002-9904-1950-09407-5 , MR 0038078 .
  4. ^ a b Куллман, Дэвид (1979), "The Utilities Problem", Mathematics Magazine , 52 (5): 299–302, JSTOR 2689782 . 
  5. ^ Дудени, Генри (1917), «Проблема 251 - Вода, газ и электричество» , Развлечение по математике , Томас Нельсон
  6. ^ Dudeney, Генри (1913), "недоумение, с некоторыми легкими головоломками для начинающих" , The Strand Magazine , Vol. 46, стр. 110.
  7. ^ "Головоломка" , Успешное земледелие , т. 13, стр. 50, 1914 г.; «Загадка колодца и дома» , Товарищ молодежи , т. 90 нет. 2, стр. 392 г., 1916 г..
  8. ^ «32. Загадка фонтана» , The Magician's Own Book, Or, The Whole Art of Conjuring , New York: Dick & Fitzgerald, 1857, p. 276.
  9. ↑ Хеннеберг, Л. (1908), « Графическая статистика », « Encyklopädie der Mathematischen Wissenschaften» , 4.1 , стр. 345–434.. Цитируется Coxeter (1950) . См., В частности, стр. 403 .
  10. ^ Kuratowski, Казимир (1930), "Sur Le problème де courbes gauches ан Topologie" (PDF) , Фонд. Математика. (на французском языке), 15 : 271–283 .
  11. ^ Трюдо, Ричард Дж. (1993), Введение в теорию графов (исправленное, расширенное переиздание. Ред.), Нью-Йорк: Dover Pub., Стр. 68–70, ISBN 978-0-486-67870-2, получено 8 августа 2012 г.
  12. ^ Kappraff, Джей (2001), Connections: Геометрический мост между искусством и наукой , K & E серии на Узлов и все, 25 , World Scientific, стр. 128, ISBN 9789810245863.
  13. ^ Пах, Янош ; Шарир, Миха (2009), «5.1 Пересечения - проблема кирпичного завода», комбинаторная геометрия и ее алгоритмические приложения: лекции Алкалы , математические обзоры и монографии, 152 , Американское математическое общество , стр. 126–127.
  14. ^ Кэмпбелл, SR; Эллингем, Миннесота ; Ройл, Гордон Ф. (1993), "Характеристика хорошо покрытых кубических графов", Журнал комбинаторной математики и комбинаторных вычислений , 13 : 193–212, MR 1220613 .

Внешние ссылки [ править ]

  • 3 утилиты Puzzle at Cut-the knot
  • Загадка с утилитами объяснена и «решена» на Archimedes-lab.org
  • Лой, Джим, Доказательство того, что невозможная головоломка невозможна , архивировано с оригинала 20 января 2007 г.
  • Вайсштейн, Эрик В. , «Граф полезности» , MathWorld