WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 | 2 || 4 | 5 |   ...   | 44 |

– Рис. 2. Граница грани – не цикл – § 1. Топологические и геометрические свойства графов Рис. 3. Область видимости для Рис. 4. Область видимости для невыпуклого четырёхугольника одной из новых граней Построим теперь последовательно требуемое вложение графа G, начиная с графа Gv-3. В качестве вложения графа Gv-3 возьмём произвольный треугольник. В качестве вершины Vv-3 возьмём произвольную точку внутри этого треугольника. Точку Vv-3 нужно соединить с двумя или тремя вершинами треугольника. После этого треугольник разобьется либо на треугольные области, либо на треугольную и невыпуклую четырёхугольную. Если вершину Vv-4 нужно поместить в треугольную область, то это делается произвольным образом. Если же вершину Vv-4 нужно поместить в невыпуклую четырёхугольную область, то поместим её в область, заштрихованную на рис. 3. Это – область, из которой видны все вершины – цикла. В дальнейшем, исходя из области видимости, мы на каждом шаге снова будем получать некоторую область видимости – непустое открытое – множество (рис. 4). Вершину Vi-1 нужно каждый раз помещать в область видимости.

Для доказательства непланарности графов обычно используется простейший вариант теоремы Жордана – для конечнозвенных ломаных.

– Т е о р е м а 1.2 (кусочно-линейная теорема Жордана). Пусть C – – замкнутая несамопересекающаяся конечнозвенная ломаная на плоскости R2. Тогда R2 \ C состоит ровно из двух связных областей, причём границей каждой из них служит C.

Д о к а з а т е л ь с т в о. Выберем некоторый фиксированный круг D, пересекающий ломаную C по отрезку. Из каждой точки множества R2 \ C можно сколь угодно близко подойти к ломаной C, не пересекая ее. Затем, идя вдоль ломаной C, можно войти в круг D. Ломаная C делит круг D на две части, поэтому количество областей не больше двух.

Остаётся доказать, что множество R2 \ C несвязно. Пусть x R2 \ C и l – произвольный луч с началом x. Пересечение луча l с ломаной C со– стоит их нескольких точек и отрезков. Каждой такой точке (или отрезку) сопоставим 0 или 1 в зависимости от того, как расположены входящее и выходящее звенья ломаной C по отношению к лучу l: если они расположены по одну сторону от l (или если луч l касается C), то сопоставим 0, 20 Глава I. Графы а если по разные стороны – сопоставим 1. Чётность (остаток от деления – на 2) суммы всех сопоставленных чисел при повороте луча изменяется непрерывно, поэтому чётность постоянна. Ясно также, что во всех точках связной области множества R2 \ C чётность должна быть одной и той же. С другой стороны, если некоторый отрезок пересекает ломаную C ровно в одной точке, то в его концах чётность принимает разные значения.

С л е д с т в и е. Пусть a, b, c, d – точки замкнутой несамопе– ресекающейся ломаной C, расположенные в указанном порядке.

Предположим, что точки a и c соединены ломаной L1, а точки b и d соединены ломаной L2, причём обе эти ломаные лежат в одной и той же из двух областей, образованных ломаной C. Тогда ломаные L1 и L2 пересекаются в некоторой точке.

Д о к а з а т е л ь с т в о. Точки a и c разбивают ломаную C на две части. Ломаные C и L1 разбивают плоскость на три области: границей одной из этих областей служит C, а границами двух других областей служит L1 и дуги ломаной C (для доказательства этого утверждения можно рассмотреть концы отрезка, пересекающего ломаную L1 в одной точке и не пересекающего ломаную C). По условию ломаная L2 лежит в той же области множества R2 \ C, что и ломаная L1. Поэтому точки ломаной L2, близкие к точкам b и d, лежат в разных областях, образованных ломаными C и L1.

Простейшими примерами непланарных графов служат графы K3,и K5, изображённые на рис. 5 (вершинами этих графов являются только выделенные точки: у графа K3,3 шесть вершин, а у графа K5 пять вершин).

Аналогично можно определить графы Kn и Kn,m. Граф Kn (полный граф с n вершинами) состоит из n вершин, попарно соединённых рёбрами.

Граф Kn,m состоит из n + m вершин, разбитых на два подмножества из n вершин и из m вершин; рёбрами соединены все пары вершин из разных множеств.

Рис. 5. Графы K3,3 и K§ 1. Топологические и геометрические свойства графов Т е о р е м а 1.3. Графы K3,3 и K5 непланарные.

Д о к а з а т е л ь с т в о. Вершины графа K3,3 можно занумеровать так, что его рёбра образуют замкнутую ломаную x1x2x3x4x5x6, а кроме того, у графа есть рёбра x1x4, x2x5 и x3x6. Если бы граф K3,3 был планарным, то указанная замкнутая ломаная разбивала бы плоскость на две области и два из указанных трёх рёбер лежали бы в одной из этих областей. Но в таком случае эти рёбра обязаны пересекаться.

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

З а д а ч а 1.1. а) Можно ли граф K3,3 вложить в лист Мёбиуса (т. е.

расположить на листе Мёбиуса так, чтобы его рёбра попарно не пересекались) б) Можно ли граф K5 вложить в тор Наметим ещё один подход к доказательству непланарности графов K3,3 и K5. Будем предполагать, что все рассматриваемые графы расположены на плоскости, но их рёбра могут при этом пересекаться (рёбра пересекаются в конечном числе точек, и никакое ребро не проходит через вершину). Назовём индексом пересечения двух графов количество точек пересечения рёбер одного графа с рёбрами другого графа, приведённое по модулю 2. (Предполагается, что графы находятся в общем положении, т. е. они пересекаются в конечном числе точек, и точки пересечения отличны от вершин.) З а д а ч а 1.2. Докажите, что индекс пересечения двух циклов равен 0.



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

суммирование снова ведётся по модулю 2.

З а д а ч а 1.3. а) Предположим, что для любого ребра графа несмежные с ним рёбра образуют цикл. Докажите, что индекс самопересечения такого графа не зависит от того, как он расположен на плоскости, а зависит только от самого графа.

б) Докажите, что графы K3,3 и K5 непланарные.

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

Т е о р е м а 1.4 (Куратовский). Граф непланарен тогда и только тогда, когда он содержит подграф, гомеоморфный K3,3 или K5.

Д о к а з а т е л ь с т в о (см. [91]). Нам остаётся доказать трудную часть теоремы Куратовского: если граф непланарен, то он содержит подграф, гомеоморфный K3,3 или K5. Предположим, что существуют непла22 Глава I. Графы Рис. 6. Граф K3,нарные графы, не содержащие подграфов, гомеоморфных K3,3 или K5.

Среди всех таких графов выберем граф G с наименьшим числом рёбер.

Ш а г 1. Пусть граф G содержит ребро xy. Тогда после выбрасывания вершин x и y (и выходящих из них рёбер) получается граф G - x - y, не содержащий подграфов, гомеоморфных графу K3,2 (рис. 6).

Предположим, что граф G = G - x - y содержит подграф, гомеоморфный графу K3,2.

Несложно убедиться, что граф G xy, полученный из графа G стя/ гиванием ребра xy в точку, не содержит подграфов, гомеоморфных K3,или K5. В самом деле, если граф G xy содержит подграф, гомеоморфный / K3,3, то граф G содержит подграф, гомеоморфный K3,3, а если граф G xy / содержит подграф, гомеоморфный K5, то граф G содержит либо подграф, гомеоморфный K5, либо подграф, гомеоморфный K3,3 (рис. 7).

Из минимальности графа G следует, что граф G xy планарен. По/ этому граф G = G - x - y = (G xy) - (xy) тоже планарен. Рассмотрим / вложение в плоскость графа G xy и индуцированное им вложение в плос/ Рис. 7. Граф G содержит подграф K3,3 или K§ 1. Топологические и геометрические свойства графов кость графа G. Одна из областей, на которые рёбра графа G разбивают плоскость, содержит вершину xy графа G xy. Пусть F – подграф гра/ – фа G, состоящий из рёбер, которые ограничивают эту область. Граф F разбивает плоскость не более чем на две части, поэтому он не содержит подграфов, гомеоморфных K3,2. Согласно предположению граф G содержит подграф, гомеоморфный K3,2. Следовательно, у графа G есть ребро e, отличное от рёбер графа F. Это, в частности, означает, что граф F разбивает плоскость на две части. Поэтому он содержит некоторый цикл C. Выброшенная вершина xy и ребро e лежат в разных частях плоскости, заданных циклом C. Для определённости будем считать, что вершина xy лежит внутри C, а ребро e лежит вне C.

Чтобы прийти к противоречию, построим вложение графа G в плоскость. Для ext C, т. е. для части графа G G, лежащей вне цикла C, воспользуемся уже имеющимся вложением графа G. Оставшуюся часть графа G обозначим G - ext C. Она содержит строго меньше рёбер, чем граф G, поскольку ребро e ей не принадлежит. Из минимальности графа G следует, что граф G - ext C планарен. В графе G - ext C вершины x и y соединены ребром, поэтому при любом вложении графа в плоскость вершины x и y лежат либо внутри C, либо вне C. Можно считать, что они лежат внутри C. Поэтому у планарного графа G - ext C есть вложение, для которого цикл C служит границей. Комбинируя указанные вложения графов ext C и G - ext C, получаем вложение графа G.

Ш а г 2. Пусть граф G содержит ребро xy. Тогда у графа G - x - y не может быть двух вершин степени 1.

Предположим, что из вершин u и v графа G - x - y выходит по одному ребру. Из минимальности графа G следует, что у него нет вершин, из которых выходит менее трёх рёбер. Поэтому вершины u и v соединены рёбрами с вершинами x и y. Кроме того, вершины x и y соединены ребром, а значит, вершины x, y, u, v порождают в G подграф, содержащий граф K3,2. В таком случае из шага 1 следует, что у графа G не может быть рёбер, оба конца которых отличны от x, y, u, v. Пусть w – вершина – графа G, отличная от x, y, u, v. Из вершины w выходит не менее трёх рёбер, поэтому она соединена ребром с одной из вершин u и v. Согласно предположению каждая из вершин u и v соединена ребром не более чем с одной вершиной, отличной от x и y. Поэтому граф G содержит не более двух вершин, отличных от x, y, u, v. В таком случае граф G является одним из четырёх графов, изображённых на рис. 8.

Ш а г 3. Пусть граф G содержит ребро xy. Тогда граф G - x - y является циклом.

Пусть G = G - x - y. У графа G нет изолированных вершин, поскольку изолированная вершина графа G соответствует вершине гра24 Глава I. Графы Рис. 8. Четыре варианта графа G фа G, из которой выходит не более двух рёбер, а это противоречит минимальности графа G. Из шагов 1 и 2 следует, что граф G представляет собой одно или несколько деревьев, вершинами которых служат « » « » циклы (рис. 9); при этом у графа G не может быть более одного ребра со свободным концом.

Предположим, что граф G не является циклом. Он не может содержать двух изолированных циклов C1 и C2. В самом деле, вершины x и y вместе с вершинами цикла C1 порождают граф, содержащий подграф, гомеоморфный K3,2, поскольку любая вершина цикла C1 соединена ребром с вершиной x или с вершиной y. Поэтому у графа G не может быть рёбер, оба конца которых отличны от x, y и вершин цикла C1. Таким образом, граф G содержит цикл C, у которого есть вершина v, соединённая Рис. 9. Связная компонента графа G § 1. Топологические и геометрические свойства графов Рис. 10. Подграф графа G Рис. 11. Структура графа G ребром с некоторой вершиной w, не принадлежащей циклу C; при этом никакие другие вершины цикла C не соединены рёбрами с вершинами, не принадлежащими циклу C (рис. 10).





В графе G любая вершина цикла C, кроме вершины v, соединена ребром с вершиной x или с вершиной y. Таких вершин по крайней мере две, поэтому вершины цикла C вместе с вершинами x и y порождают граф, содержащий подграф, гомеоморфный K3,2. Из этого следует, что у графа G нет рёбер, не имеющих общих вершин с циклом C. Но для ребра, не входящего в цикл C, общей с циклом C вершиной может быть только вершина v, причём из v выходит только одно ребро, не содержащееся в цикле C. Следовательно, граф G состоит из подграфа, изображённого на рис. 10, и рёбер, выходящих из вершин x и y.

Если цикл C содержит более трёх вершин, то после выбрасывания из графа G вершин v и w получается граф, содержащий подграф, гомеоморфный K3,2. Поэтому цикл C содержит ровно три вершины, а тогда граф G имеет такой вид, как на рис. 11. Этот граф планарен.

Доказательство теоремы Куратовского теперь легко завершается.

Пусть x и y – смежные вершины графа G. Тогда граф G - x - y пред– ставляет собой цикл C, каждая вершина которого в графе G соединена ребром с вершиной x или с вершиной y. Предположим, что вершина u цикла C соединена ребром с вершиной x и не соединена ребром с вершиной y. Тогда вершина v цикла C, соседняя с вершиной u, не соединена ребром с вершиной x. Действительно, если граф G содержит ребро xv, то после выбрасывания этого ребра получаем планарный граф.

У этого планарного графа нет ребра yu, поэтому на плоскости точки x и v можно соединить и получить вложение графа G, чего не может быть.

26 Глава I. Графы Итак, либо все вершины цикла C соединены с обеими вершинами x и y, либо они поочередно соединены то с x то с y. В первом случае граф G содержит подграф, гомеоморфный K5, а во втором случае граф G содержит подграф, гомеоморфный K3,3.

Другие доказательства теоремы Куратовского можно найти в [125].

Помимо критерия Куратовского известны и другие критерии планарности графов; см., например, [92], [41] и [30]. Одним из наиболее интересных среди этих критериев является критерий Уитни [141], основанный на понятии двойственности для графов.

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

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

Т е о р е м а 1.5 (Уитни). Граф планарен тогда и только тогда, когда существует двойственный ему граф.

Д о к а з а т е л ь с т в о (см. [104]). Прежде всего убедимся в том, что для планарного графа можно построить двойственный ему граф.

Рассмотрим вложение планарного графа G в плоскость и выберем в каждой из областей, на которые граф G разбивает плоскость, по одной точке. Эти точки будут вершинами графа G. Две вершины графа G соединим ребром, если соответствующие им части плоскости граничат по некоторому ребру графа G. Ясно, что графы G и G двойственны друг другу.

Займемся теперь доказательством трудной части теоремы Уитни: если граф непланарен, то у него нет двойственного графа. При этом мы воспользуемся теоремой Куратовского, т. е. будем доказывать, что если граф содержит подграф, гомеоморфный K3,3 или K5, то у него нет двойственного графа.

Ш а г 1. У графов K3,3 и K5 нет двойственных графов.

Предположим, что G – граф, двойственный графу K3,3. У графа K3,– нет разделяющих множеств, состоящих менее чем из трёх рёбер, и у него есть циклы только длины 4 и 6. Поэтому у графа G нет циклов длины 1 или 2 и из любой его вершины выходит по крайней мере 4 ребра. Из этих двух условий следует, что у графа G есть по крайней мере 5 вершин.

Из каждой вершины выходит по крайней мере 4 ребра. Поэтому у графа G есть по крайней мере 5 · 4 2 = 10 рёбер. Получено противоречие, так как / у графа K3,3 всего 9 рёбер.

Предположим теперь, что G – граф, двойственный графу K5. У гра– фа K5 нет двойных рёбер и у него есть разделяющие множества только § 1. Топологические и геометрические свойства графов из 4 и 6 рёбер. Поэтому у графа G нет вершин степени менее 3 и у него есть циклы только длины 4 и 6. Граф G имеет 10 рёбер и не совпадает с K5, поэтому он имеет по крайней мере 6 вершин. Если граф G имеет ровно 6 вершин, то он должен иметь такой вид, как на рис. 12. У такого графа 9 рёбер, а у графа K5 количество рёбер равно 10. Если же граф G имеет 7 или более вершин (которые по условию имеют степень не менее 3), то количество его рёбер не меньше 7 · 3 2 > 10.

/ Ш а г 2. Если у графа G есть двойственный граф, то и у любого его подграфа тоже есть двойственный граф.

Достаточно доказать, что если у графа G есть двойственный граф G и e – – Рис. 12. Структура граребро графа G, то у графа H, полученного фа G с шестью вершинами из графа G выбрасыванием ребра e, есть двойственный граф H. Легко проверить, что если e – ребро графа G, – соответствующее ребру e графа G, то граф H, полученный из графа G стягиванием ребра e в точку, двойствен графу H.

Ш а г 3. Если у графа G есть двойственный граф, то и у любого графа H, гомеоморфного графу G, тоже есть двойственный граф.

Достаточно доказать, что если у графа G есть двойственный граф G и граф H получен из графа G добавлением вершины степени 2, лежащей на ребре e графа G, то у графа H тоже есть двойственный граф H.

Pages:     | 1 | 2 || 4 | 5 |   ...   | 44 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.