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

С л е д с т в и е 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.

1.5. Теорема Штейница Рёбра выпуклого многогранника (в трёхмерном пространстве) образуют 3-связный граф (теорема 1.12 на с. 34). Этот граф, очевидно, планарен: поверхность выпуклого многогранника с одной выколотой точкой гомеоморфна плоскости. Оказывается, что 3-связность и планарность графа являются не только необходимыми, но и достаточными условиями того, что граф реализуется как набор рёбер выпуклого многогранника.

Т е о р е м а 1.13 (Штейниц [123]). Граф) можно реализовать как набор рёбер выпуклого многогранника в трёхмерном пространстве тогда и только тогда, когда этот граф 3-связен и планарен.

Д о к а з а т е л ь с т в о (см. [35]). Напомним, что граф 3-связен тогда и только тогда, когда он содержит по крайней мере 4 вершины и после выбрасывания любых двух его вершин и выходящих из них рёбер получается связный граф (теорема 1.11 на с. 32). В 3-связном графе не может быть вершин, из которых выходит менее трёх рёбер, поэтому 3-связный граф с n вершинами содержит по крайней мере n 3 2 рё/ бер. Следовательно, минимальное число рёбер имеет 3-связный граф K4, образованный рёбрами тетраэдра.

Доказательство теоремы Штейница проведем индукцией по числу рёбер 3-связного планарного графа. База индукции: граф K4, имеющий 6 рёбер. Шаг индукции делается в два этапа:

1) Сначала сопоставляем 3-связному планарному графу G, имеющему более 6 рёбер, 3-связный планарный граф G с меньшим числом рёбер.

2) Затем по данному выпуклому многограннику P, рёбра которого образуют граф G, мы строим выпуклый многогранник P, рёбра которого образуют граф G.

Пусть G - граф с ребром e. Определим операцию уничтожения - ребра e следующим образом. Сначала удалим из графа G ребро e, а затем, ) Здесь предполагается, что у графа нет ни петель, ни двойных рёбер.

36 Глава I. Графы Рис. 16. Уничтожение ребра e если в результате такой операции возникнут вершины степени 2, удалим их, т. е. заменим одним ребром два ребра с общей вершиной, из которой не выходит никаких других рёбер (рис. 16).

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

Ш а г 1. Любой 3-связный планарный граф G, число рёбер которого больше 6, имеет ребро e, уничтожив которое, получим 3-связный планарный граф G.

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

Пусть = {0,..., n} - набор несамопересекающихся путей в гра - фе G. Сопоставим графу G и набору путей 1-мерный комплекс G, у которого могут быть петли и двойные рёбра. Вершинами комплекса G будут те вершины графа G, которые являются концами путей i, и те вершины графа G, через которые проходят по крайней мере два пути i.

Рёбрами комплекса G будут дуги путей i, высекаемые на этих путях вершинами G.

е м м а. Пусть G - 3-связный граф. Тогда существует такой - набор путей {0,..., n}, что для (k) = {0,..., k}, где 1 k n, выполняются следующие свойства:

1) комплекс G(k) является 3-связным графом;

2) G(1) = K4;

3) G(n) = G;

4) при k = 1,..., n - 1 путь k+1 не пересекает граф G(k) в точках, отличных от концов пути k+1.

Д о к а з а т е л ь с т в о. Набор путей {i} для графа G будем строить по индукции. Прежде всего докажем, что любой 3-связный граф G содержит подграф, гомеоморфный K4. Пусть x и y - две различные вершины - графа G. По условию существуют независимые пути 1, 2 и 3 из x в y. Из этих трёх путей только один путь может быть ребром. Пусть для з 1. Топологические и геометрические свойства графов определённости пути 2 и 3 проходят через вершины z2 и z3, отличные от x и y. После выбрасывания точек x и y остаётся связный граф, поэтому точки z2 и z3 можно соединить путём, не проходящим через x и y.

Путь может частично проходить по 2 и 3, но у него есть участок, не проходящий по 2 3 и соединяющий вершины v 2 и w 3. Вершины x, y, v, w и высекаемые ими на путях, 1, 2, 3 дуги образуют подграф, гомеоморфный K4.

Среди всех подграфов графа G, гомеоморфных K4, выберем подграф T, которой содержит наибольшее число вершин графа G. Пусть x, y, v, w - его вершины. В качестве 0 выберем путь vw, а в качестве - 1 выберем путь vxwy. Тогда G(1) = K4.

Предположим, что пути 0,..., k уже построены и G(k) = G. Тогда выполняется одно из двух условий:

а) существует вершина z графа G, которая лежит на ребре графа G(k), но не является вершиной графа G(k);

б) условие а) не выполняется, но существует вершина z графа G(k), из которой выходит ребро графа G, не являющееся ребром графа G(k).

Действительно, из связности графа G следует, что если некоторая вершина графа G не принадлежит графу G(k), то существует ребро графа G, один конец которого принадлежит графу G(k), а другой не принадлежит.

В случае а) рассмотрим ребро e графа G(k), содержащее вершину z.

Пусть z1 и z2 - концы ребра e, а z - вершина графа G(k), отличная от - - z1 и z2. Из 3-связности графа G следует, что в нём существует путь из z в z, не проходящий через z1 и z2. Поэтому в графе G существует путь из некоторой внутренней точки ребра e в некоторую точку (не обязательно вершину) графа G(k), не имеющий с графом G(k) общих точек, отличных от концов пути. В качестве k+1 выберем такой путь, содержащий наибольшее число вершин графа G.

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

Пути 0,..., k выбирались так, чтобы они содержали наибольшее число вершин графа G. Поэтому путь ведёт из вершины z в вершину графа G, не соседнюю с z. В качестве пути k+1 выберем путь, проходящий через наибольшее число вершин графа G.

В случае б) в графе проводится дополнительное ребро; это не может нарушить 3-связность графа.

В случае а) либо на одном ребре выбирается дополнительная вершина u и из нее проводится ребро в уже имеющуюся вершину, либо на двух рёбрах выбираются дополнительные вершины u и v и проводится ребро uv. Ясно, что после выбрасывания любых двух вершин нового 38 Глава I. Графы Рис. 17. Три варианта уничтожения ребра графа, отличных от u и v, граф остаётся связным. Выбрасывание вершины u эквивалентно выбрасыванию ребра в старом графе, на котором лежит вершина u. После выбрасывания одного ребра 3-связный граф превращается по крайней мере в 2-связный граф. Поэтому новый граф 3-связен.

Остальные требования, которым должен удовлетворять путь k+1, выполняются очевидным образом.

С помощью леммы шаг 1 доказывается совсем просто. Пусть {0,..., n} - набор путей для 3-связного графа G, содержащего более - 6 рёбер. Этот граф отличен от K4, поэтому n > 1. У графа G нет вершин степени 2, поэтому путь n состоит из одного ребра графа G.

После уничтожения этого ребра получаем 3-связный граф G(n-1), что и требовалось.

Теперь нужно сделать второй шаг - научиться строить по выпуклому - многограннику P, соответствующему графу G, выпуклый многогранник P, соответствующий графу G. В планарном графе G уничтожаемое ребро может быть одного из трёх видов, изображённых на рис. 17.

Этим трём видам уничтожаемых рёбер графов соответствуют три вида добавляемых рёбер многогранников; они изображены на том же рисунке.

Требуемое преобразование многогранников можно попытаться построить, слегка пошевелив грани F1 и F2, чтобы они оказались в разных плоскостях (в исходном многограннике P они лежат в одной плоскости, а в многограннике P они должны лежать в разных плоскостях).

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