WWW.DISSERS.RU

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

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


Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 44 |

Легко проверить, что граф 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.

С л е д с т в и е 1. При любом вложении листа Мёбиуса в R3 его край зацеплен со средней линией.

Д о к а з а т е л ь с т в о (см. [89]). Вложим в лист Мёбиуса граф K6, как показано на рис. 15.

Циклы 134 и 256 соответствуют краю листа Мёбиуса и его средней линии. Несложно проверить, что во всех других парах несамопересекающихся циклов один из циклов заклеен треугольной областью, принадлежащей листу Мёбиуса. Такие циклы не могут быть зацеплены, потому что иначе возникли бы самопересечения листа Мёбиуса. Если циклы Ci и Cj не зацеплены, то (Ci, Cj) = 0. Поэтому циклы 134 и 256 зацеплены.

С л е д с т в и е 2. Проективную плоскость RP2 нельзя вложить в R3.

Д о к а з а т е л ь с т в о. Вырежем из вложенной в R3 проективной плоскости диск D2. В результате получим лист Мёбиуса. Его средняя линия C зацеплена с S1 = D2, поэтому C пересекает D2, чего не может быть.

1.4. k-связные графы Два пути, проходящих по рёбрам графа из вершины x в вершину y, называют независимыми, если у них нет других общих вершин, кроме x и y.

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

Т е о р е м а 1.11 (Менгер–Уитни). Граф G, содержащий по край– ней мере k + 1 вершину, является k-связным тогда и только тогда, ) В гомотопической топологии этот термин имеет совсем другой смысл.

§ 1. Топологические и геометрические свойства графов когда после выбрасывания любых его k - 1 вершин (и выходящих из них рёбер) получается связный граф.





Д о к а з а т е л ь с т в о (см. [100]). Мы докажем более общее утверждение, а именно, если p(G, x, y) – наибольшее число независимых – путей из вершины x в вершину y, а q(G, x, y) – наименьшее чис– ло точек, отличных от x и y и обладающих тем свойством, что любой путь из вершины x в вершину y проходит через одну из них, то p(G, x, y) = q(G, x, y).

Неравенство p(G, x, y) q(G, x, y) достаточно очевидно. В самом деле, пусть 1,..., p – независимые пути из x в y; x1,..., xq – точки – – (отличные от x и y), для которых любой путь из x в y проходит через одну из них. Из независимости путей 1,..., p следует, что каждый из них проходит не более чем через одну из точек x1,..., xq. С другой стороны, любой путь из x в y проходит через одну из точек x1,..., xq, поэтому p q.

Предположим, что G – граф с минимальным числом рёбер, для – которого не выполняется равенство p(G, x, y) = q(G, x, y). Тогда p = = p(G, x, y) < q(G, x, y) = q. У графа G есть рёбра, отличные от ребра xy. Пусть – одно из таких рёбер, G- – граф, полученный из гра– – A фа G выбрасыванием ребра, и G = G – граф, полученный из графа G / – A стягиванием ребра в одну точку. Число рёбер графов G- и G строго меньше числа рёбер графа G, поэтому согласно предположеA A нию p(G-, x, y) = q(G-, x, y) и p(G, x, y) = q(G, x, y), а значит, A q(G-, x, y) = p(G-, x, y) p(G, x, y) = p

A Таким образом, в графах G- и G есть множества вершин I и, разделяющие x и y и состоящие менее чем из q элементов. Множеству соответствует множество J вершин графа G, разделяющее x и y. При этом |J| |J | + 1 и |J| q. Следовательно, |J| = || + 1. Это означает, что оба конца ребра принадлежат множеству J.

Пусть Hx – множество вершин z I J, для которых в G есть путь – из x в z, не проходящий через остальные вершины из множества I J; Hy определяется аналогично. Любой путь из x в y в графе G проходит через одну из вершин множества J, поэтому, в частности, он проходит через одну из вершин множества I J. Первая из таких вершин лежит в Hx, а последняя лежит в Hy. Поэтому множества Hx и Hy разделяют вершины x и y в графе G, а значит, |Hx| q и |Hy| q.

Пусть z Hx Hy. Тогда в G есть пути из x в z и из z в y, не проходящие через вершины множества I J, отличные от z. Из этих двух путей можно составить один путь из x в y. Путь проходит ровно через одну вершину множества I J, а именно, вершину z. Поэтому, в частности, путь не проходит через ребро, поскольку оба конца 34 Глава I. Графы ребра лежат в J. Следовательно, путь принадлежит графу G -, а значит, путь проходит через одну из вершин множества I. Но такой вершиной может быть только вершина z. Кроме того, путь проходит через одну из вершин множества J; такой вершиной тоже может быть только вершина z. Таким образом, z I J, т. е. Hx Hy I J.

Поэтому |Hx| + |Hy| = |Hx Hy| + |Hx Hy| |I J| + |I J| = |I| + |J|, но этого не может быть, поскольку |Hx| q, |Hy| q, |I| < q и |J| = q.

С л е д с т в и е. Пусть G1 и G2 – k-связные подграфы одного – и того же графа. Тогда если |G1 G2| k, то граф G1 G2 k-связен.

Д о к а з а т е л ь с т в о. Согласно теореме Менгера–Уитни после – выбрасывания произвольных k - 1 вершин графа G1 G2 графы G1 и Gостаются связными. У графов G1 и G2 есть общая вершина, отличная от выброшенных вершин, поэтому граф G1 G2 тоже остаётся связным.

Важным примером n-связных графов являются графы, образованные рёбрами выпуклых многогранников в n-мерном пространстве. Будем называть граф n-реализуемым, если его можно реализовать как набор рёбер (невырожденного) выпуклого многогранника в Rn.

Т е о р е м а 1.12 (Балинский [31]). Любой n-реализуемый граф является n-связным.

Д о к а з а т е л ь с т в о. Пусть Pn – многогранник в Rn, рёбра кото– рого образуют рассматриваемый граф. Требуется доказать, что если выбросить произвольные вершины A1,..., An-1 и выходящие из них рёбра, то в результате получится связный граф. Пусть V – аффинное простран– ство, порожденное точками A1,..., An-1. Возможны два случая.

С л у ч а й 1. V не содержит внутренних точек многогранника Pn.

k В этом случае V Pn = F1 – грань многогранника Pn. Пусть H1 – – – k опорная гиперплоскость многогранника Pn, содержащая грань F1, H2 – – l вторая опорная гиперплоскость, параллельная H1, и F2 = Pn H2. Если A – вершина многогранника Pn, отличная от A1,..., An-1, то из A – можно опуститься по рёбрам многогранника на гиперплоскость H1, не поднимаясь при этом на гиперплоскость H2, и, в частности, не проходя через вершины A1,..., An-1 и выходящие из них рёбра. Из другой вершины B мы точно так же попадаем в некоторую вершину многогранl l ника F2 = Pn H2. Остаётся заметить, что вершины многогранника Fобразуют связный граф.

С л у ч а й 2. V содержит внутренние точки многогранника Pn.

Размерность пространства V не превосходит n - 2. Поэтому существует гиперплоскость H, содержащая пространство V и ещё хотя бы одну вершину An многогранника Pn, не лежащую в V. Пусть H1 и H2 – – § 1. Топологические и геометрические свойства графов опорные гиперплоскости многогранника Pn, параллельные H. Такие же рассуждения, как и в случае 1, показывают, что из любой вершины A, отличной от A1,..., An-1, можно попасть в вершину An, не проходя при этом через вершины A1,..., An-1 и выходящие из них рёбра.

Для этого нужно спуститься или подняться на гиперплоскость H1 или гиперплоскость H2. Ясно также, что если из любой вершины можно пройти в вершину An, то из любой вершины можно пройти в любую другую вершину, пройдя через вершину An.

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 44 |










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

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