Задача о трёх домах и трёх колодцах

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

Спустя некоторое время обитатели домов А, В, и С серьёзно поссорились друг с другом и решили проложить дорожки к трём колодцам а, b, с так, чтобы по пути к колодцам и обратно им не приходилось встречать друг друга.

А возможно ли это? Является ли соответствующий граф плоским, т.е. можно ли провести дорожки так, чтобы они не пересекались нигде, кроме вершин графа А, В, С и а, b, с?

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

На рис. 1.4 показан один из возможных вариантов проведения тропинок. Решим эту задачу посредством рассуждений.

От домиков А и С проведём требуемые тропинки. Полученный граф разделит плоскость на области: X , Y , Z. Легко заметить, что домик В может находиться в одной из этих областей. 

Рис.1. 4

Рассмотрим каждый случай в отдельности.

1. Если домик В находится в области Z, как изображено на рисунке, то от него невозможно провести тропинку к b, которая не пересекалась бы ни с одной из уже проведённых тропинок.

2. Если домик В находится в области Y , то от него невозможно провести тропинку к объекту а, которая не пересекалась бы ни с одной из уже проведённых.

3. Если домик В находится в области X, то от него невозможно провести тропинку к объекту c, которая не пересекалась бы ни с одной из уже проведённых. Итак, получается, что граф, выражающий ситуацию данной задачи, плоским быть не может. А это значит, что задача неразрешима.

Лекция 2.  Теорема Куратовского. Формула Эйлера для многогранников

Задача о полном графе, имеющем 5 вершин.

 Доказать, что любой полный граф, имеющий пять вершин, неплоский.

Решение.

 Вершины графа обозначим буквами А, В, С, D, К. Если по точкам А, В, С и D построим полный граф, то он будет плоским и разделит плоскость на четыре области (рис. 2.1).

Рис. 2.1

Обозначим эти области буквами X,Y,Z,U. Тогда точка К будет расположена в одной из этих областей. Проведя рассуждения, аналогичные предыдущим, получаем, что полный граф с пятью вершинами действительно плоским быть не может.

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

Рис. 2.2

Эти два графа, изображённые на рис.2. 2, называются графами Куратовского.

Критерий, характеризующий плоские графы, был предложен в 1930 г. польским математиком Куратовским.

Чтобы сформулировать его, мы должны сначала объяснить, что мы понимаем под расширением и сжатием графа.