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

Например, на рис. 19 граф выделяет на плоскости следующие области.

А1, А2 , А3 , А4 , А5 .

Теорема Эйлера.

Связный плоский граф с n вершинами и m ребрами разбивает плоскость на r областей (включая внешнюю) , причем n-m+r=2.

Примеры неплоских графов.

Задача о трех домах трех колодцах.

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

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

Можно ли это сделать?

Число лишних точек пересечения можно свести к одной, если провести дорожки так, как указано на рис. 21.

Вопрос: является ли соответствующий граф плоским, т.е. можно ли провести дорожки так, чтобы они не пересекались нигде, кроме вершин графа A, B, C, x, y, z?Сколько не пытаться, нужного решения не найти. Однако наша неспособность решить задачу методом проб не дает математического доказательства того, что это вообще невозможно сделать.

Строгое же доказательство основано на следующей теореме.

Теорема Жордана.

Пусть K-непрерывная замкнутая линия на плоскости. Линия

Эйлеровы графы.

Гамильтоновы графы.

I. Задача о кенингсбергских мостах, 1936 год, Эйлер.

Город Кенингсберг (ныне Калининград) расположен на берегах реки Прегель и двух островах. Различные части города были соединены семью мостами. По воскресеньям горожане совершали прогулки по городу. Можно ли совершить прогулку таким образом, чтобы, выйдя из дома, вернуться обратно, пройдя в точности один раз по каждому мосту? Схематично карта Кенингсберга изображена на рис. 24.

Эйлер показал, что этого сделать нельзя.

На рис. 25 изображен граф, изоморфный графу на рис. 24.

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

Введем следующие определения:

Определение.

Путь в графе, содержащий все ребра графа, называется эйлеровым.

Определение.

Цикл, содержащий все ребра графа по одному разу, называется эйлеровым.

Определение.

Граф, обладающий эйлеровым циклом, называется эйлеровым графом.

Определение.

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

Теорема:

Граф G является эйлеровым тогда и только тогда, когда G-связный и все его вершины четные.

Алгоритм построения эйлерова цикла в связном графе со всеми вершинами четной степени.

Выйти из произвольной вершины Vi . Каждое пройденное

Ребро зачеркнуть. Если путь l1 замыкается в Vi и проходит

Через все ребра графа, то получим эйлеровый цикл.

Если остались непройденные ребра, то должна существовать

Вершина V2 , принадлежащая l1 и ребру.

Так как V2-четная, то число ребер, которое принадлежит V2 и

Которые не вошли в путь l1, тоже четно. Начнем новый путь l2 из

V2 и используем только те ребра, которые не принадлежат l1 , этот

Путь кончится в V2.

Объединим теперь оба цикла: из Vi пройдем по l1 к V2, затем по l2 и

Вернувшись в V2 ,пройдем по оставшейся части l1 обратно в Vi .

Если снова найдутся ребра, не вошедшие в путь, то найдем новые

Циклы, так как число ребер и вершин конечно, то процесс

Закончится.