Книги по разным темам Pages:     | 1 |   ...   | 2 | 3 | 4 | 5 | 6 |   ...   | 49 |

В графе 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.

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

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

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

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

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

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

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

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

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

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

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

Д о к а з а т е л ь с т в о. Пусть G - планарный граф с n вершинами.

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

з 1. Топологические и геометрические свойства графов Предположим теперь, что у графа G нет вершин, степень которых строго меньше 5. Тогда у него есть вершина v, степень которой равна 5.

Вершины графа G, соседние с вершиной v, не могут быть все попарно соединены рёбрами, потому что иначе граф G содержал бы непланарный граф K5. Пусть 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 цвета (теорема о четырёх красках), но доказывается это чрезвычайно сложно. Первое опубликованное доказательство теоремы о четырёх красках ([27] и [29]) занимало 150 страниц, но исчерпывающее изложение этого доказательства [28] занимало 740 страниц. Затем появились более простые доказательства.

Например, доказательство, приведённое в [112], занимает чуть больше 40 страниц, но и это доказательство весьма сложно. Оно тоже было получено с помощью компьютера.

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

б) Пусть - гладкая замкнутая кривая, все самопересечения кото - рой трансверсальны. Докажите, что разбивает плоскость на области, которые можно раскрасить в два цвета так, что области, граничащие по некоторой дуге, будут разного цвета.

Из формулы Эйлера можно вывести разные другие формулы. Из них наиболее часто применяется следующая формула.

Т е о р е м а 1.8. Пусть G - планарный граф без изолированных - вершин, vi - число его вершин, из которых выходит i рёбер, fj - - - число граней, ограниченных j рёбрами (с учетом их кратностей).

30 Глава I. Графы Тогда (4 - i)vi + (4 - j) fj = 4(1 + s) 8, где s - число компонент - i j связности графа G.

Д о к а з а т е л ь с т в о. Ясно, что ivi = 2e = jfj (каждое ребро i j имеет ровно два конца и принадлежит ровно двум граням). Кроме того, vi = v и fj = f. Поэтому из формулы Эйлера следует, что i j (4 - i)vi + (4 - j) fj = 4v - 2e + 4f - 2e = i j = 4(v - e + f) = 4(1 + s), где s - число компонент связности графа G.

- С л е д с т в и е. Если все грани 4-угольные, то 3v1 + 2v2 + v3 8.

Часто используется также следующее неравенство.

Т е о р е м а 1.9. Если любая грань ограничена циклом, содержаn(v - 2) щим не менее n рёбер, то e.

n - Д о к а з а т е л ь с т в о. Требуемое неравенство следует из неравенств nv - ne + nf 2n и 2e nf.

З а д а ч а 1.5. Воспользовавшись теоремой 1.9, получите ещё одно доказательство непланарности графов K5 и K3,3.

1.3. Вложения графов в трёхмерное пространство В плоскость можно вложить не любой граф. Но любой конечный граф можно вложить в трёхмерное пространство. Более того, граф можно вложить в трёхмерное пространство так, что все его рёбра будут прямолинейными отрезками. Например, если вершины графа разместить на кривой (t, t2, t3), то отрезки, соединяющие вершины графа, не будут пересекаться. В самом деле, точки кривой с параметрами t1, t2, t3, t4 являются вершинами тетраэдра, объем которого равен 2 1 t1 t1 t 1 t2 t2 t2 1 = 0;

2 1 t3 t3 t2 1 t4 t4 tв частности, противоположные рёбра этого тетраэдра не пересекаются.

Обсудим теперь более подробно вложения в R3 графа K6, состоящего из шести вершин, попарно соединённых рёбрами. Выберем в графе Kтри вершины и рассмотрим цикл C1, порождённый этими тремя вершиз 1. Топологические и геометрические свойства графов нами, и цикл C2, порождённый тремя остальными вершинами. Фиксируем проекцию вложенного в R3 графа K6 и определим (C1, C2) как остаток от деления на 2 количества перекрестков, на которых цикл C1 проходит над C2. Иными словами, (C1, C2) = lk(C1, C2) (mod 2), где lk - коэф - фициент зацепления. В частности, (C1, C2) = (C2, C1) (доказательство этого свойства коэффициента зацепления приведено в [17]). Поэтому можно рассмотреть число (K6) = (Ci, Cj), где суммирование ведется 1 по всем = 10 неупорядоченным парам непересекающихся циклов 2 из трёх элементов.

Т е о р е м а 1.10 ([116] и [48]). Для любого вложения графа Kв трёхмерное пространство (K6) 1 (mod 2). В частности, для любого такого вложения найдётся пара зацепленных циклов.

Д о к а з а т е л ь с т в о. У графа Kесть вложение в R3, для которого ровно два цикла зацеплены, а все остальные циклы незацеплены (рис. 13).

юбое вложение графа K6 в R3 можно преобразовать в данное вложение, если при этом допускаются преобразования рёбер, изображённые на рис. 14.

Посмотрим, что происходит с (K6) при пересечении пары рёбер ei и ej. Число (Cp, Cq) при этом изменяется лишь в том случае, когда ei Cp и ej Cq Рис. 13. Граф K6 с двумя за(или ej Cp и ei Cq). Непересекающиецепленными циклами ся циклы Cp и Cq, содержащие пару рёбер ei и ej, существуют тогда и только тогда, когда рёбра ei и ej несмежные. Таких пар циклов для данных рёбер ei и ej ровно две: к ребру ei можно добавить одну из двух вершин, которые не входят в ei и ej. Таким образом, при пересечении ребра с самим собой или со смежным ребром число lk(Ci, Cj) не изменяется, а при пересечении ребра с несмежным ребром это число изменяется Рис. 14. Изменение типа перекрёстка (пересечение пары рёбер) 32 Глава I. Графы Рис. 15. Вложение графа K6 в лист Мёбиуса на 2. Поэтому число (K6) = lk(Ci, Cj) (mod 2) не изменяется при всех преобразованиях вложения графа K6.

Pages:     | 1 |   ...   | 2 | 3 | 4 | 5 | 6 |   ...   | 49 |    Книги по разным темам