6. П ланарность

   1. Плоские и планарные графы

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

14. Граф называется плоским ,если его вершины – это точки лежащие на плоскости ,а рёбра – линии на плоскости , которые не пересекаются друг с другом.

Граф называется планарным, если он изоморфен плоскому графу.

3. Плоские графы:

4. Граф :

является планарным т.к. его можно представить в виде плоского т.о.:

5. Граф:

Следующая классическая головоломка наводит на мысль, что не только планарные графы.

Задача о 3-х домах и 3-х колодцах. Имеются 3 дома 1,2,3 и 3 колодца 4,5,6 (граф ):

Каждый хозяин пользуется любым из 3-х колодцев. В некоторый момент обитатели домов решили проложить дорожки до колодцев так , чтобы дорожки не пересекались .Возникает вопрос : возможно ли это .Все попытки нарисовать 9 непересекающихся дорожек оканчиваются неудачей. При этом легко нарисовать 8 дорожек (непересекающихся), но 9 обязательно пересечет хотя бы 1 из них. Т.е. граф К_3,3 не является планарным.

1. Грани плоского графа. Формула Эйлера

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

Таким образом, плоский граф разделяет плоскость на грани.

16. Границей грани будем считать множество вершин и рёбер, принадлежащей этой грани.

6. Граф с 4-мя гранями. Плоский граф имеет единственную неограниченную грань (4). Такая грань называется внешней, а остальные грани - внутренними.

4. Эйлера. Для всякого связного плоского графа верно равенство:

1. -число граней плоского графа.

4. Проведем по индукции по числу рёбер. Если , то , т.е. теорема выполняется.

Предположим, что теорема выполняется для всех графов с числом рёбер <= , т.е. . Добавим еще одно ребро. Если добавляемое ребро соединяет существующие вершины, то , , . Тогда . Если добавляемое ребро соединяет существующую вершину с новой, то , , . Тогда .

5. Если связный планарный граф (), то .

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

.

2. и непланарны.

6. 1. Рассмотрим . Имеем , . Если планарен, то . Получили противоречие.

2. Рассмотрим . Имеем , . В этом графе нет треугольников, значит, если этот граф планарен, то в его плоской укладке каждая грань ограничена по крайней мере четырьмя ребрами. Следовательно, или . По формуле Эйлера , отсюда . Имеем . Получили противоречие.