Оглавление
Проблема с тремя коммунальными услугами
-
История и формулировка головоломки
- Головоломка “Три коммунальных службы” была впервые опубликована в 1960 году.
- Задача состоит в том, чтобы соединить три дома с системами водоснабжения, газоснабжения и электроснабжения без пересечения линий.
-
Математическая формализация
- Головоломка является частью топологической теории графов и изучает вложение графов в плоскости.
- Граф, описывающий задачу, называется полным двудольным графом
- K
- 3
- ,
- {\displaystyle K_ _BOS_3,3}
- .
-
Неразрешимость задачи
- Куратовский в 1930 году доказал, что
- не является плоским графом, что делает задачу неразрешимой.
- Куллман утверждает, что Куратовский не опубликовал доказательства своей теоремы.
-
Альтернативные решения и свойства
- Существуют решения головоломки, которые используют тороидальные вложения или позволяют инженерным сетям проходить через другие объекты.
- Граф
-
Обобщения и рекомендации
- Задача о кирпичном заводе обобщает головоломку и связана с минимальным числом пересечений на чертежах двудольных графов.
- Внешние ссылки предоставляют дополнительную информацию и решения головоломки.
Полный текст статьи: