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

Оглавление

Введение____________________________________________________2

0.        Необходимые вспомогательные утверждения__________________3

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

2.        Формула Эйлера для планарных графов_________________________7

3.        Критерии планарности____________________________________10

4.        Двойственность и планарность_____________________________18

5.        Алгоритм укладки графа на плоскости_______________________21

6.        Характеристики планарных графов___________________________25

7.        Упражнения______________________________________________________27

8.        Список литературы_______________________________________________29

Введение

Графы стали изучаться ещё математиками  18 веке но как предмет математической теории только в 20 веке. В настоящее время теория графов находит всё более и более широкое применение применяются в  естественных науках (физика, химия, биология, социология, лингвистика).  Простейшему с топологической точки зрения объекту – графам (1 – мерным комплексам) посвящена моя работы. Сначала обсуждается общие понятия, затем его топологическое  и метрическое свойство: планарность.

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

0.               Необходимые определения и вспомогательные утверждения

Рассматривается множе­ство V, состоящее из соединенных некоторым образом точек назовем V множеством вершин и элементы   вершинами  Граф

                                                                                                              (0.1.1)

с множеством вершин V есть некоторое семейство сочетаний или пар вида

                                                                                                (0.1.2)

указывающее, какие вершины считаются соединенными. В соответствии с геометрическим представлением графа каждая конкретная пара (0.1.2) называется ребром графа, вершины а и b называются концевыми точками или кон­цами ребра E.

                                                                                                    (0.1.3)

ребро (0.1.3) будет называться петлей.

В определении ребра (0.1.2) мо­жно принимать или не принимать во внимание порядок расположения двух, его концов. Если этот порядок не­существен, т. е. если

                                                                                                   (0.1.4)

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

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

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

Возьмём в пространстве R3 несколько точек A1 ..., Ап и соединим некоторые из них попарно непересекающимися кривыми. Полученное множество с индуцированной из R3 топологией называют графом, или 1-мерным комплексом. Точки  A1 ..., Ап называют при этом верши­нами, или 0-мерными клетками, а соединяющие их кривые называют рёбрами, или 1-мерными клетками. Количество рёбер, выходящих из вершины графа, называют степенью вершины. В том случае, когда из любой вершины графа можно пройти по его рёбрам в любую другую вершину, граф называют связным.

Граф может иметь петли (рёбра, начало и конец которых совпадают) и двойные рёбра (несовпадающие рёбра, имеющие одну и ту же пару вершин).

Последовательность попарно различных вершин v1,...,vn, соединён­ных рёбрами v1v2, v2v3,…,vnv1, называют циклом.

Плоским графом назовем граф, вершины которого являются точками плоскости, а ребра — непрерывными плоскими линиями без самопересечений, соединяющими соответствующие вершины так, что никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины. Примеры плоских графов даны на рис. 36.1.

Любой граф, изоморфный плоскому графу, будем называть планарным. О планарных графах говорят, что они укладываются на плоскости (имеют плоскую укладку). В дальнейшем будут рассматриваться укладки графов не только на плоскости, но и на других поверхностях и в пространстве. Поэтому дадим определение укладки графа в произвольное пространство. Прежде всего введем понятие жордановой кривой, под которой будем понимать непрерывную спрямляемую линию, не имеющую самопересечений.  Будем говорить, что граф G укладывается в пространство L, если существует такое отображение вершин и ребер графа G соответственно в точки и жордановы кривые этого пространства, что различным вершинам соответствуют различные точки, а кривые, соответствующие различным ребрам, пересекаются только в инцидентных этим ребрам вершинах. Изображенный таким образом граф называется укладкой графа G в пространство L.

Теорема 1.1. Каждый граф  укладывается в трехмерное пространство Е3.

Все вершины графа G помещаем в различные точки оси ОХ. Из пучка плоскостей, проходящих через эту ось, выберем \EG\ различных плоскостей. Далее, каждое ребро uv  EG изображаем в соответствующей плоскости полуокружностью, проходящей через вершины u и v. Понятно, что в результате получаем укладку графа G в Е3, так как все ребра лежат в разных плоскостях и потому не пересекаются во внутренних точках.

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

Для доказательства этой теоремы достаточно рассмотреть стереографическую проекцию (рис. 36.4). Пусть граф G уложен на сфере. Проведем плоскость Q, касательную к сфере, так, чтобы северный полюс N (точка, диаметрально противоположная точке касания) не лежал на ребре и не совпадал с вершиной графа G. Те­перь рассмотрим граф G', полученный стереографической проекцией графа G из точки N на плоскость Q. Посколь­ку существует биективное соответствие между точками сферы, отличными от N, и их стереографическими проек­циями, то граф G' плоский и изоморфен графу G. Следо­вательно, G — планарный граф.

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

Задача о трех домах и трех колодцах. Имеются три дома 1, 2, 3 и три колодца 4, 5, 6 (рис. 36.5). Каждый хозяин пользуется любым из трех колодцев. В некоторый момент обитатели домов решили проложить дорожки до колодцев так, чтобы исключить встречи на дорожках, т. е. чтобы дорожки не пересекались. Все попытки нарисовать девять непересекающихся дорожек, соединяющих дома с колодцами, заканчиваются неудачей. При этом легко нарисовать семь непересекающихся дорожек, но девятая обязательно пересечет хотя бы одну из этих восьми. Оказывается, что неудачи не случайны. Ниже будет доказано, что граф К3,3 не укладывается на плоскости, т. е. не является планарным.

Утверждение 1. Почти все графы не являются, планарными.

                     Теорема 1.3.   Графы К3,3 и К5  непланарные.

                 Доказательство. Вершины графа К3,3 можно занумеровать так, что его рёбра образуют замкнутую ломаную х1x2x3x4x5x6, а кроме того, у графа есть рёбра х1x4, х2x5 и х3x6. Если бы граф К3,3 был планарным, то указанная замкнутая ломаная разбивала бы плоскость на две области и два из указанных трёх рёбер лежали бы в одной из этих областей. Но в таком случае эти рёбра обязаны пересекаться.

                  Непланарность графа К5  доказывается аналогично. Замкнутая ломаная х1x2x3x4x5 разбивает плоскость на две области. Три из пяти остальных рёбер графа лежат в одной из этих областей. Из этих трёх рёбер можно выбрать два ребра, не имеющие общих вершин.             

                  Наметим ещё один подход к доказательству непланарности графов К3,3 и К5 - Будем предполагать, что все рассматриваемые графы распо­ложены на плоскости, но их рёбра могут при этом пересекаться (рёбра пересекаются в конечном числе точек, и никакое ребро не проходит через вершину). Назовём индексом пересечения двух графов количество точек пересечения рёбер одного графа с рёбрами другого графа, приведённое по модулю 2. (Предполагается, что графы находятся в общем положе­нии, т. е. они пересекаются в конечном числе точек, и точки пересечения отличны от вершин.)

                  Назовём индексом самопересечения графа на плоскости сумму ин­дексов пересечения всех его (неупорядоченных) пар несмежных рёбер; суммирование снова ведётся по модулю 2.

                  Ясно, что если граф содержит подграф, гомеоморфный К3,3 или К5,  то он непланарен. В 1930 г. Куратовский  доказал, что верно и обратное.

2. Формула Эйлера для планарных графов.

              Для выпуклого многогранника (в трёхмерном пространстве) справед­лива следующая формула Эйлера: если v — число вершин многогранни­ка, е — число рёбер и f — число граней, то v-е+f = 2. Граф, образо­ванный рёбрами выпуклого многогранника в трёхмерном пространстве, планарен: если из поверхности выпуклого многогранника выколоть одну точку, то получится топологическое пространство, гомеоморфное плос­кости.

                  Для планарных графов формула Эйлера остаётся справедливой и в общей ситуации. Будем называть гранями связные области, на ко­торые разбивает плоскость вложенный в неё пленарный граф.

              Теорема 2.1 (формула Эйлера). Пусть G — планарный граф, состоящий из s компонент связности, среди которых нет изоли­рованных вершин. Пусть, далее, v — число вершин графа G, а е — число его рёбер. Тогда для любого вложения графа G в плоскость число граней f одно и то же, а именно, f = 1 + s - v + e.

              Доказательство. Если граф не содержит циклов, то он не раз­бивает плоскость. Связные компоненты такого графа называют деревья­ми. Индукцией по числу рёбер дерева легко доказать, что у любого дерева число вершин ровно на 1 больше числа рёбер. В самом деле, удаление любого ребра разбивает дерево на два дерева с меньшим числом рёбер. Поэтому для графа, состоящего из одного или нескольких деревьев, фор­мула Эйлера верна.             

        Если же граф содержит цикл, то можно рассмотреть область, ограниченную циклом и не содержащуюся в другой области, ограниченной циклом. Для такой области удаление одного граничного ребра уменьшает число граней на 1 и не изменяет число вершин.

              Следствие. Связный планарный граф (без петель и двой­ных рёбер) содержит вершину, степень которой не превос­ходит 5.

        Доказательство. Любая грань содержит не менее 3 рёбер, по­ этому 3f 2е. Подставляя это неравенство в соотношение 3f = 6-Зv + Зе, получаем е3v-6. Предположим, что из любой вершины выходит не менее 6 рёбер. Тогда 6v2е, а значит, 6v2е2(3v-6)=6v-12, чего не может быть.

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

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

              Доказательство. Пусть G — планарный граф с п вершинами. Применим индукцию по п. При п5 утверждение очевидно. Предполо­жим, что утверждение доказано для всех планарных графов, у которых число вершин не превосходит п-1. Если у графа G есть вершина v, степень которой строго меньше 5, то рассмотрим граф С, который полу­чается из графа G после выбрасывания вершины v и выходящих из неё рёбер. Согласно предположению индукции вершины графа С можно рас­красить в 5 цветов. Вершина v в графе G соединена рёбрами менее чем с 5 вершинами, поэтому её можно окрасить в цвет, отличный от цветов соседних с ней вершин.

              Предположим теперь, что у графа G нет вершин, степень которых строго меньше 5. Тогда у него есть вершина v, степень которой равна 5. Вершины графа G, соседние с вершиной v, не могут быть все попарно соединены рёбрами, потому что иначе граф G содержал бы непланарный граф К5. Пусть v1 и v2 — вершины графа G, соединённые рёбра­ми с вершиной v и не соединённые ребром друг с другом. Рассмотрим сначала граф G', который получается из графа G после выбрасыва­ния вершины v и выходящих из неё рёбер. Затем рассмотрим граф G", который получается из графа G' после проведения дополнительного ре­бра, соединяющего вершины v1 и v2. Это дополнительное ребро можно составить из рёбер v1v и vv2, поэтому граф G" планарен. Наконец, стя­нем в графе G" дополнительное ребро в точку. В результате получим планарный граф G"', число вершин которого равно n-2. По предпо­ложению вершины этого графа можно раскрасить в 5 цветов. Эта рас­краска индуцирует раскраску вершин графа G', при которой вершины v1 и v2 будут одного цвета. Это означает, что вершины графа G, со­седние с вершиной v, имеют не более 4 различных цветов. Поэтому вершину v можно окрасить в цвет, отличный от цветов соседних с ней вершин.

              Замечание. В действительности вершины любого планарного графа можно раскрасить в 4 цвета (теорема о четырёх красках), но доказывается это чрезвычайно сложно. Первое опубликованное доказательство теоремы о четырёх красках (занимало 150 страниц, но исчерпывающее изложение этого доказательства занимало 740 страниц). Затем появились более простые доказательства, занимающие чуть больше 40 страниц, но и это доказательство весьма сложно. Оно тоже было получено с помощью компьютера.