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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


курсовая работа Плоские и планарные графы

Информация:

Тип работы: курсовая работа. Добавлен: 02.11.2012. Сдан: 2012. Страниц: 11. Уникальность по antiplagiat.ru: < 30%

Описание (план):



Оглавление
Введение____________________________________________________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 страниц, но и это доказательство весьма сложно. Оно тоже было получено с помощью компьютера.
              Из формулы Эйлера можно вывести разные другие формулы. Из них наиболее часто применяется следующая формула.
              Теорема 2.3. Пусть G — планарный граф без изолированных вершин, vi — число его вершин, из которых выходит i рёбер, fj — число граней, ограниченных  рёбрами (с учетом их кратностей).
Тогда где s — число компонент связности графа G.
              Доказательство.   Ясно, что (каждое ребро имеет ровно два конца и  принадлежит ровно двум граням). Кроме того, и Поэтому из формулы Эйлера следует, что где s — число компонент связности графа G.             
              Следствие.   Если все грани 4-угольные, то 3v1+2v2+v38. Часто используется также следующее неравенство
 
3.      Критерии планарности
Имеется несколько критериев планарности графа. Мы рассмотрим характеризации планарности графов, данные G. С. Понтрягиным, К. Куратовским, К. Вагнером и С. Наклейном. Следует заметить, что практическая про­верка условий, которыми ниже характеризуются планарные графы, не всегда является простой. Однако разработаны эффективные алгоритмы, позволяющие для любого заданного графа или найти его плоскую укладку, или установить, что граф непланарен. Один из таких алгорит­мов приведен в § 41.
Для того чтобы сформулировать широко известный критерий Понтрягина — Куратовского, введем понятие гомеоморфизма графов. Нам понадобится операция под­разбиения ребра е = аb графа. Она состоит в следующем:
из графа удаляется ребро е и добавляются два новых ребра е1 = аv, e2 = vb, где v — новая вершина.
Два графа называются гомеоморфными, если оба они могут быть получены из одного и того же графа подразбиением его ре­бер.
На рис. 39.1 изображены гомеоморфные графы.
Если граф планарный, то очевидно, что любой граф,
гомеоморфный ему, также является планарным.
 
Исторически первым критерием планарности графов является следующий критерий, доказанный Л. С. Понтрягиным (1927 г.) и К. Куратовским (1930 г.) независимо друг от друга.
Теорема 3.1. Понтрягина — Куратовского.
Граф планарен тогда и только тогда, когда он не содер­жит подграфов, гомеоморфных К5 или К3,3.
Тем самым можно утверждать, что многие графы непланарны и независимо от того, как они изображены на плоскости, некоторые их ребра обязательно пересекаются.
Необходимость доказана, по­скольку доказана непланарность графов К5 и Кз,з (теорема 1.3.). Для доказательства достаточности требуются новые понятия и теоремы. Будет достаточно, ес­ли мы, касаясь вопросов, связанных с плоской укладкой 2-связного графа G, рассмотрим лишь 3-связные графы, полученные из G специальным образом.
Пусть x(G) = 2|G.| ? 4. Из определения двусвязности вытекает существование вершин а, b ? VG, таких что граф Н = G — а — b не связен. Рассмотрим следующее преобразование А графа G. Пусть h1, h2, ..., Hr — связные компоненты графа Н. Для каждой такой компо­ненты Hi рассмотрим граф Gi, порожденный в G мно­жеством V U Hi , a Ub и дополненный ребром ab, если аb ? EG. В результате преобразования А получаем семей­ство графов g1, g2, ..., Gr, причем |Gi| ? 3, х(Gi) ? 2 (i = l, r) (рис. 39.2).
 
 
 
 
 
 
 
Теорема 3.1.1. Пусть х(G) = 2, |G| ? 4. Граф G планарен тогда и только тогда, когда планарен каждый граф Gi, полученный в результате преобразования А.
Необходимость. Если G — планарный граф, то любой его подграф, в том числе G0i = G(VGi), плана­рен. Если Gi содержит ребро аb, то Gi = G0i. В противном случае по лемме 34.7 в G существуетG0i-цепь L, соединя­ющая вершины а и b. Подграф Gi0 U L планарен, но он гомеоморфен графу Gi.
Достаточность. Пусть все графы g1, G2, ..., Gr планарны. Пусть Р1, Р2 , ..., Рr— соответствующие им плоские укладки, у которых ребро ab лежит на внешней грани. Будем последовательно объединять графы Р1, p2, ..., Рr. Сначала построим такую укладку объедине­ния Р1,2 графов Р1 и P2, в которых имеется общее ребро ab, что граф Р2 лежит на внешней грани графа Р1. Затем изобразим P1,2 так, чтобы ребро ab оказалось на внешней грани, и используя прежний прием, построим объедине­ние P1,.2,3 графов P1,2и Pз (рис. 39.3) и т. д., пока не объ­единим все графы p1, Р2, ..., Рг. Полученный в результат - не плоский граф p1,2 …….r может отличаться от исходного графа G только ребром аb.
 
 
 
 
Утверждение 3.1.1. Пусть x(G)=2, |G| ? 4. Тогда в результате многократного применения преобразова              ния А к графу G будет получено такое семейство графов              Gi  G2, .. …GR ,что для любого i = 1, R либо Gi=K3, либо х (Gi) ? 3.
Поскольку Кз — планарный граф, то вопрос о планарности 2-связных графов свелся к вопросу о планарности 3-связных графов. Прежде чем формулировать критерий планарности 3-связных графов, докажем лемму.
Лемма 3.1.1. Пусть x(G)= 2, |G| ? 4. Пусть, да­лее, g1, g2, ..., Gr — графы, полученные в результате пре­образования А,и Аb — ребро этих графов, не принадлежащее графу G. Тогда для любого i = 1, r существует Сi -цепь графа G, соединяющая вершины а и b.
Поскольку x(Gk) ? 2 для любого k = 1, r, то ребро аb принадлежит некоторому простому циклу графа Gk. При любом k ? i часть этого цикла, не содержащая ребра ab, и служит искомойGi,-цепью.
Плоский граф назовем выпуклым прямолинейным графом, если границей каждой его грани является выпуклый многоугольник. Напомним, что многоугольник называет­ся выпуклым, если он целиком расположен по одну сто­рону от любой прямой, на которой лежит сторона много­угольника, и никакие две его стороны не лежат на одной прямой.
Теорема 3.1.2. Если граф 3-связный, то он либо изоморфен выпуклому прямолинейному графу, либо со­держит подграф, гомеоморфный К5 или К3,3
Доказательство проведем индукцией по числу n вершин графа. Для n = 4 утверждение теоремы верно, так как граф К4 изоморфен выпуклому прямолинейному графу (см. рис. 36.1, б), а других 3-связных четырех вершинных графов не существует.
Пусть G — 3-связный граф, |G|=n ? 5 и для всех графов с меньшим числом вершин теорема верна, тогда в графе G есть такое ребро x = uv, что граф Gx, полученный из G в результате стягивания этого ребра, является 3-связным. Пусть Gx содержит под­граф Н, гомеоморфный K5 (рис. 39.5, а). Покажем, что тогда граф G содержит подграф, гомеоморфный К5 или Kз,з. Это очевидно в случае, когда Н не содержит верши­ны x0, полученной в результате стягивания ребра х, или содержит ее в качестве вершины степени 2. Пусть теперь степень каждой из вершин а, b, с, d, х0 в Н равна четы­рем. Тогда вершина х0 соединена простыми непересекающимися цепями L1, L2, .L3, L4 с вершинами а, b, с, d cоответственно. В графе G этим цепям соответствуют пе­ресекающиеся простые цепи L1, L2, .L3, L4, соединяющие каждую из вершин а, b, с, d с одной из вершин и и v. Если одна из этих вершин, например и, принадлежит трем или четырем цепям, то в G существует подграф, гомеоморфный К5 (рис. 39.5, б).  А если каждая из вершин u и v принадлежит ровно двум цепям, то в G существует подграф, гомеоморфный Кз,з (рис. 39.5, в, г).
Пусть теперь в Gx нет подграфов, гомеоморфных графы К5 или .Кз.з. По индуктивному предположению существует выпуклый прямолинейный граф G0х, изоморфный графу Gx. Тогда G0x—x0 — 2-связный плоский граф, каждая грань которого ограничена простым циклом.
Как обычно, через NG(v) обозначим окружение вершины v в графе G. Пусть С — простой цикл, ограничивающий грань графа G0х — х0, которая содержит NG0x(х0). Вершины из ng(v)\u делят цикл С на простые цепи
L1 =(a1 ..., a2),  L2 =(a2, ..., а3), ..., Lk = (ak, ..., a1 ).                                    (1)
 

Далее рассмотрим отдельно два случая.
Случай 1. Все вершины из NG(u)\v принадлежат одной из цепей (1). Тогда, удалив из G0x все ребра вида (x0, b), где b ? ai (i = 1, k), получим граф G', изоморф­ный графу G — u. Ребрами графа G' являются отрезки, и все его грани, кроме, возможно, грани, содержащей вершины из NG(u), будут выпуклыми многоугольниками.
Пусть вершина х0 принадлежит внутренней грани гра­фа G0x.
 
 
 
 
 
 
Всякий выпуклый многоугольник обладает следующим свойством: для любой его вершины существует такая ее окрестность, в которой можно пере­мещать эту вершину (при неподвижных остальных), не нарушая выпуклости многоугольника. Поэтому в графе G0х существует такая окрестность 0(х0) точки х0, что при перемещении х0 в 0(х0) будет сохраняться выпуклость всех многоугольников, находящихся внутри цикла С.
Будем считать, что вершины из NG(u)\v находятся па цепи Lk и разбивают ее на части: (а1, ..., b1), (b1, ... ..., b2), ..., (bl-i, ..., bl), (bl,, ..., ak). Обозначим через Т точки плоскости, лежащие внутри кривой (цикла) (х0, b1, ..., b2, ..., bl х0). Поместив вершину и в лю­бую точку области О (х0) объединяя с Т и соединив и со всеми вер­шинами из NG(u) (считая x0 =v), получим выпуклый прямолинейный граф, изоморфный графу G (рис. 39.6). Подобным образом поступаем и тогда, когда вершина х0 принадлежит внешней грани графа G0x. (На рис. 39.7 а, б изображен случай, когда вершина и принадлежит внут­ренней грани графа G', а на рис. 39.7 в, г — внешней.)

     Случай 2. Не существует цепи (1), содержащей все вершины  из  множества  NG(u)\v.  В  этой  ситуации множество всех ребер, инцидентных и и v, нельзя изобра­зить без пересечений. В самом деле, если
М= \ (NG(u)\v) ? (NG(v)\u)\ ? 3,
т. е. число вершин цикла С, смежных и с u, и с v, не меньше трех, то в G существует подграф, гомеоморфный графу К5 (рис. 39.8). Если же М ? 2, то в G есть подграф, гомеоморфный графу Кз,з. На рис.39.9—39.11 изображены случаи, ког­да М = 2, 1, 0 соответственно.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Осталось доказать достаточность условий теоремы. Пусть в графе G нет подграфов, гомеоморфных К5 или Кз,з- если G — 3-связный граф, тогда он планарен. Пусть x (G) =2, |G| ? 5. Далее доказательство проведём от противного. Предположим, что граф G не планарный. Тогда в результате многократного применения к не ­преобразования А получим семейство графов G1, G2,……., GR, среди которых имеется 3-связный граф G. В Gt есть подграф К, геоморфный К5 или Кз,з. Если все ребра графа К ? G, то К — подграф графа G, т. е. получено противоречие. Если же некоторое ребро аb ? ЕК не входит G, то по лемме существует Gi-цепь графа G, соединяющая вершины а и b. Нетрудно показать, что Gi-цепи, cоответствующие различным таким ребрам, не имеющих вершин, кроме, возможно, концевых. Заменив каждое такое ребро соответствующей Gi-цепью, получим подграф графа G, гомеоморфный графу К. Вновь имеем проворечие.
 

 
В качестве иллюстрации рассмотрим граф Петерсена(содержит подграф, гомеоморфный графу Кз,з(рис. 39.12, {a1,a2,a3} и {b1,b2,b3} — доли). Следовательно, этот граф не является планарным.
Помимо критерия Понтрягина — Куратовского есть и другие критерии планарности графа. Приведем некоторые из них без доказательств.
Теорема 3.2. (К. Вагнер, 1937 г.). Граф планарен тогда и только тогда, когда в нем нет подграфов, стяги­ваемых к графам К5 или Кз,з.
Поскольку граф Петерсена стяги­вается к К5 (для этого нужно стянуть пять ребер, соеди­няющих вершины внутреннего и внешнего циклов), то непланарность графа Петерсена с помощью критерия Вагнера доказывается совсем просто.
Отметим здесь, что стягивая любое ребро планарного графа, получаем вновь планарный граф.
Очевидно, что все ациклические графы планарны. Поэтому вполне естественна формулировка критерия пла­нарности, исключающая этот тривиальный случай. Та­ким критерием является следующая теорема.
Теорема 3.3. (С. Маклейн, 1937 г.). Граф планарен тогда и только тогда, когда в каждом его нетривиаль­ном блоке есть такой базис циклов С1, С2, ..., Ck и такой один дополнительный цикл Со, что любое ребро блока принадлежит ровно двум из этих k + 1 циклов.
4. Двойственность и планарность
Целью этого параграфа является получение еще од­ного критерия планарности графа, основанного на поня­тии двойственности.
Условимся, что всюду в этом пункте слово «граф» означает «псевдограф». Кроме того, видоизменим здесь использованную выше операцию стягивания ребра е = uv ?EG, под которой теперь будем понимать удаление ребра е и отождествление вершин и и v в но­вую вершину, инцидентную тем ребрам графа G, которые были инцидентны вершинам и и v, за исключением реб­ра е (рис. 40.1). Тем самым теперь появляющиеся при стягивании ребра кратные ребра не отождествляются, как ранее.
Для плоского графа G построим новый плоский граф G*, который назовем геометрически двойственным к G. Для этого внутри каждой грани Ti графа G выберем по одной точке V*i. Эти точки — вершины будущего графа G*. Далее, каждому ребру е ? EG поставим в соответствие жорданову кривую е*, которая пересекает лишь одно реб­ро е графа G и соединяет вершины v *i, лежащие в гранях, границы которых содержат ребро е (таких граней может быть две или одна). Кривые е* — ребра графа G*. Ребра графа G* можно провести так, чтобы они не пересекались. На рис. 40.2 сплошной линией изображен граф G, а пунктирной — граф G*. Заметим, что петлю в G* порождает всякий мост в G, а кратные

ребра появляются в G* тогда и только тогда, когда две грани графа G имеют более одного общего ребра.

Т.о. построен граф G*, геометри­чески двойственный к плоскому графу G. Он определяется однозначно с точностью до изоморфизма, причем граф G*всегда связен. Последнее утверждение легко доказать индукцией по числу вершин графа G* (т. е. по числу гра­ней графа G) путем стягивания ребра е* графа G*, что, соответствует удалению ребра е в графе G. При этом, если ребро е — граница двух граней, то упомянутые операции приводят к уменьшению числа вершин графа G* (числа граней графа G) на единицу. Применяя формулу Эйлера, легко получить
Утверждение 4.1. Если G — плоский связный (n, т)-граф с f гранями, a G* — (n*, т*)-граф, геометрисески двойственный к нему, с I* гранями, то n* = f, n* = m, f* = n.
Поскольку граф G* — плоский, то можно построить граф, геометрически двойственный к G*, который естественно обозначить через G**. Связь между графами G и G** устанавливает следующая теорема.
Теорема 4.1. Если G — плоский связный граф, то граф G** изоморфен графу G.
Из утверждения 4.1 следует, что n** —f* = n, где n**=\G**\. Следовательно, каждая грань графа G* со­держит одну вершину графа G (G**). Поэтому построе­ние, при помощи которого граф G* получен из G, можно обратить, т. е. получить G из G*.
Граф, двойственный к планарному графу, определяет­ся следующим образом: рассмотрим любую укладку это­го графа и построим геометрически двойственный граф. Здесь уместно отметить, что планарный граф, допускаю­щий несколько укладок на плоскости, может иметь не изоморфные двойственные графы .
Теорема 4.2. Пусть G —планарный граф, G* — граф, геометрически двойственный к G. Подмножество ребер из G образует простой цикл в G тогда и только тогда, когда соответствующее множество ребер из G* об­разует разрез в G*.
Для доказательства этой теоремы потребуется одна очевидная лемма.
Лемма 4.2. Пусть Н — связный граф, множество VH вершин которого разбито на два подмножества V1 и V2. Множество ребер
является разрезом тогда и только тогда, когда графы H(V1) u H(V2) связны.
Доказательство теоремы 4.2. Не исклю­чая общности, будем считать, что G — плоский граф.
Пусть С — простой цикл в G. Тогда он ограничивает одну или несколько внутренних граней графа G, т. е. ог­раничивает часть плоскости, содержащую непустое мно­жество W вершин графа G*. Поэтому ребра из G*, пере­секающие ребра цикла С, образуют множество М в G*, удаление которого разделяет связный граф G* на два подграфа с множествами вершин W и VG*\W (рис. 40.3). Индукцией по числу вершин легко доказать связность каждого из этих подграфов. Следовательно, на основании леммы 40.4 М — разрез в графе G*.
 
 
 
 
Путем обращения приведенного выше рассуждения до­казывается обратное утверждение о том, что разрезу в G* соответствует простой цикл в G.
Теорема 4.2. естественным образом приводит к следующему  комбинаторному  определению  двойственности графов, которое обобщает геометрическую двойственность позволяет сформулировать еще один критерий планарности графов.
Граф G* называется абстрактно двойственным к графом G, если между множествами EG и EG* существует биекция, обладающая тем свойством, что подмножество ребер из G обра­зует простой цикл в G тогда и только тогда, когда соответствующее ему подмножество ребер из G* об­разует разрез в G*.
На рис. 40.4 изображены граф и абстрактно двойственный к нему граф. Соответствующие ребра обо­значены одной и той же буквой.
Понятие абстрактной двойственности обобщает понятиe геометрической двойственности, так как согласно теореме 40.3 справедливо
Утверждение 4.3. Граф, геометрически двойственный к плоскому графу, является абстрактно двойстнным к нему.
Непосредственно из определения вытекает следующее утверждение.
Утверждение 4.4. Граф Н является абстрактно двойственным к графу G тогда и только тогда, когда матроид M(G) циклов графа G изоморфен матроиду М*(G) разрезов графа Н.
 
             
 
 
5. Алгоритм укладки графа на плоскости
Рассмотренные в предыдущих параграфах критерии планарности таковы, что если даже удалось установить планарность графа, то нет информации о том, как строить его укладку на плоскости. В то же время при реше­нии практических задач недостаточно знать, что граф планарен, а необходимо, как правило, построить его плоское изображение. Все это вызвало появление алгоритмов, которые не только проверяют граф на планарность, но и одновремен­но строят его плоскую укладку, если это возможно. Один из таких алгоритмов (алгоритм ? ) рассмотрим в этом параграфе.
Алгоритм ? укладки графа G представляет собой процесс последовательного присоединения к некоторому уложенному подграфу С0 графа G новой цепи, оба конца к
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.