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

Поэтому читатель, у которого нет интереса к теории графов, может их пропустить.

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

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

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

1.1. Планарные графы Граф G называют планарным, если его можно расположить на плоскости так, чтобы его рёбра попарно не пересекались. При этом, вообще говоря, рёбра могут быть произвольными кривыми линиями, но легко убедиться, что рёбра можно считать конечнозвенными ломаными. Более того, Вагнер [135] и Фари [55] независимо доказали следующее утверждение.

18 Глава I. Графы Т е о р е м а 1.1. Любой планарный граф можно так вложить в плоскость, что все его рёбра будут прямолинейными отрезками.

Д о к а з а т е л ь с т в о. Требуемое утверждение достаточно доказать для максимальных планарных графов. (Планарный граф называют максимальным, если после добавления любого дополнительного ребра он перестает быть планарным.) Ясно, что у максимального планарного графа все грани (области, на которые он разбивает плоскость) содержат ровно по три ребра. Пусть G - максимальный планарный граф, содержащий - v 4 вершин (при v < 4 утверждение очевидно). Выберем в графе G произвольную вершину V1, отличную от вершин криволинейного треугольника, ограничивающего граф G. Пусть G1 - граф, который получается - из графа G после выбрасывания вершины V1 и выходящих из неё рёбер.

В графе G1 все грани, кроме грани F1, которой принадлежала выброшенная вершина V1, являются треугольными. Грань F1 ограничена циклом C1.

Среди вершин цикла C1 выберем вершину V2, отличную от вершин треугольника, ограничивающего граф G, и рассмотрим граф G2, который получается из графа G1 после выбрасывания вершины V2 и выходящих из нее рёбер. В графе G2 грань F2, которой принадлежала вершина V2, не обязательно ограничена циклом (соответствующий пример приведён на рис. 2).

Чтобы грань F2 была ограничена некоторым циклом C2, вершину Vнужно выбрать специальным образом. А именно, пусть цикл C1 содержит вершину V степени 2 (имеется в виду степень вершины в графе G1), причём V отлична от вершин ограничивающего граф G треугольника. Тогда в качестве V2 мы выбираем именно эту вершину V. Концы рёбер, выходящих из вершины V, соединены ребром, поэтому после выбрасывания вершины V мы получим цикл C2. Если же цикл C1 не содержит вершин степени 2, то в качестве V2 можно выбрать произвольную вершину.

Продолжая аналогичные операции, получим последовательность графов G, G1, G2,..., Gv-3, где Gv-3 - граф, состоящий из трёх вершин, - попарно соединённых рёбрами; при этом граница каждой грани Fi - цикл.

- Рис. 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).

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