WWW.DISSERS.RU

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

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


Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 44 |

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 они должны лежать в разных плоскостях).

Но при этом возникает одна трудность: если плоскость грани проходит через n-гранный угол, где n 4, то шевелить её нельзя, потому что иначе нарушится структура графа рёбер многогранника. Например, для многогранника, изображённого на рис. 18, нельзя шевелить ни грань F1, § 1. Топологические и геометрические свойства графов Рис. 18. Грани F1 и F2 шевелить нельзя ни грань F2, потому что иначе нарушится структура рёбер, выходящих из вершин A и B. Таким образом, чтобы добиться требуемого, придется пошевелить ещё и вершины A и B. В свою очередь, малое шевеление вершины может нарушить структуру графа рёбер, если эта вершина принадлежит грани, у которой более трёх сторон.

Чтобы избавиться от этой трудности, можно попытаться упорядочить вершины и грани так, чтобы последовательность вершин и граней начиналась четверкой F1, F2, c, d и никакой член последовательности не был инцидентен) более чем трём предшествующим членам. В самом деле, если вершины и грани удастся так упорядочить, то можно пошевелить грани F1 и F2, а затем каждый следующий член последовательности сдвигать так, чтобы он оказывался инцидентным всем тем предшествующим членам последовательности, которым он должен быть инцидентен. Если вершина инцидентна трём предшествующим граням, то ее положение определено однозначно. Если же вершина инцидентна p < 3 предшествующим граням, то при выборе положения вершины имеется 3 - p степеней свободы.

Ш а г 2. Множество всех вершин и граней 3-связного планарного графа G можно упорядочить так, что любой член последовательности вершин и граней инцидентен не более чем трём предшествующим членам.

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

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

) Инцидентными могут быть только вершина и грань (или грань и вершина); вершина A инцидентна грани F, если A F.

40 Глава I. Графы Рис. 19. Граф G Требуется упорядочить вершины графа G так, чтобы в последовательности вершин каждая вершина была бы соединена рёбрами не более чем с тремя предыдущими. При этом в качестве четырёх первых вершин нуж но взять заданные вершины k1, k2, k3 и k4, порождающие цикл в графе G.

В графе G все грани 4-угольные, поэтому можно воспользоваться следствием теоремы 1.8 (см. с. 30). В результате получим, что граф G имеет по крайней мере 8 вершин степени 3 (вершин степени 1 и 2 у него, очевидно, нет). В частности, граф G имеет вершину степени 3, отличную от вершин k1, k2, k3 и k4. Эту вершину мы выберем в качестве последнего члена последовательности и обозначим её kn (здесь n – число вершин – графа G). Пусть K(n) – граф, полученный из графа G выбрасыванием – вершины kn и выходящих из неё рёбер.

Предположим, что вершины kn, kn-1,..., km уже выбраны и, кроме того, построены графы K(n), K(n - 1),..., K(m). Если m > 5, то нужно выбрать вершину km-1 и построить граф K(m - 1). По условию вершины k1, k2, k3 и k4 заданы так, что порождаемый ими граф является циклом.

В частности, степень каждой из этих вершин не меньше 2. Если граф K(m) содержит изолированную вершину или вершину степени 1, то такую вершину можно выбрать в качестве вершины km-1. Если же степень любой вершины графа K(m) не меньше 2, то возможны два случая.





С л у ч а й 1. В графе K(m) подграф, порожденный вершинами k1, k2, k3 и k4, изолирован.

Выбросим из графа K(m) вершины k1, k2, k3 и k4. К полученному графу снова можно применить следствие теоремы 1.8 и найти в этом § 2. Гомотопические свойства графов графе по крайней мере одну вершину степени не более 3. Эту вершину выберем в качестве km-1.

С л у ч а й 2. В графе K(m) по крайней мере одна из вершин k1, k2, k3 и k4 соединена ребром с вершиной ki, i 5.

В этом случае одна из вершин k1, k2, k3 и k4 имеет степень не менее 3, поэтому в величину 2v2 + v3 эти вершины дают вклад не более 7. Это означает, в частности, что граф K(m) имеет вершину степени не более 3, отличную от вершин k1, k2, k3 и k4. Эту вершину мы и выберем в качестве km-1.

Во всех случаях граф K(m - 1) получается из графа K(m) выбрасыванием вершины km-1.

§ 2. Гомотопические свойства графов 2.1. Фундаментальная группа графа На графах (1-мерных комплексах) можно наблюдать многие явления гомотопической топологии, чем мы сейчас и займемся.

Отображения f0, f1 : X Y называют гомотопными, если существует такое непрерывное отображение F : X [0, 1] Y, что F(x, 0) = = f0 (x) и F(x, 1) = f1 (x). Иными словами, отображения f0 и f1 можно связать семейством непрерывных отображений ft : X Y, 0 t 1, непрерывно зависящих от t. Это семейство непрерывных отображений называют гомотопией, связывающей f0 и f1. Для гомотопности отображений f0 и f1 используется обозначение f0 f1.

Легко проверить, что гомотопность отображений – отношение экви– валентности. При доказательство того, что если f g и g h, то f h, следует воспользоваться теоремой о склейке отображений (теорема 0.на с. 14).

З а д а ч а 2.1. Пусть отображения) f, g : GL(n, R) GL(n, R) GL(2n, R) заданы формулами A 0 AB f(A, B) =, g(A, B) =.

0 B 0 Докажите, что f g.

Отображение, гомотопное постоянному отображению, называют гомотопным нулю.

) На множестве, состоящем из матриц размером m n, топология вводится следующим образом: каждая матрица отождествляется с точкой пространства Rmn (или Cmn, если элементы матрицы комплексные) и берётся индуцированная топология.

42 Глава I. Графы Топологические пространства X и Y называют гомотопически эквивалентными, если существуют такие непрерывные отображения f : X Y и g : Y X, что отображения f g и g f гомотопны тождественным отображениям пространств Y и X, соответственно. Для гомотопической эквивалентности пространств X и Y используется обозначение X Y.

Топологическое пространство называют стягиваемым, если оно гомотопически эквивалентно точке.

У п р а ж н е н и е 1. Докажите, что пространство Rn стягиваемо.

Топологическое пространство X называют линейно связным, если любые две его точки x0 и x1 можно соединить путём, т. е. существует непрерывное отображение f отрезка I = [0, 1] в X, для которого f(0) = xи f(1) = x1.

У п р а ж н е н и е 2. Докажите, что линейно связное пространство связно.

З а д а ч а 2.2. Докажите, что следующие топологические пространства матриц линейно связны: а) пространство вещественных матриц порядка n с положительным определителем; б) пространство SO(n), состоящее из ортогональных матриц порядка n с определителем 1;

в) пространство U(n), состоящее из унитарных матриц порядка n;

г) пространство SU(n), состоящее из унитарных матриц порядка n с определителем 1.

Если в топологических про странствах X и Y, не имеющих общих точек, отмечены точки x0 X и x1 Y, то можно определить топологическое пространство X Y = X Y {x0, y0}, называемое / букетом пространств X и Y. Иными словами, пространство X Y Рис. 20. Букет окружностей получается в результате отождествления точек x0 и y0. По-другому букет X Y можно определить как подмножество в X Y, состоящее из таких точек (x, y), что x = x0 или y = y0. Аналогично для пространств X1,..., Xn с отмеченными точками x1,..., xn можно определить букет X1... Xn = X1... Xn {x1,..., xn}. Букет n окружностей изображён / на рис. 20.

Т е о р е м а 2.1. Любой конечный связный 1-мерный комплекс гомотопически эквивалентен букету окружностей.

§ 2. Гомотопические свойства графов Д о к а з а т е л ь с т в о. Предположим, что концы ребра A 1-мерного комплекса X не совпадают. Тогда A представляет собой отрезок, а не окружность, поэтому существует гомотопия ft : A A, связывающая тождественное отображение f0 = idA и постоянное отображение f1 : A A. Докажем, что в таком случае про- странства X и X A гомотопически эквивалентны.

/ Гомотопию ft : A A можно продолжить до такой гомотопии Ft : X X, что F0 = idX. Иными словами, отображение множества (A I) (X {0}) X I можно продолжить до отображения всего множества X I. Это продолжение строится следующим образом. Пусть оба конца ребра B принадлежат ребру A. Тогда отображение задано на трёх из четырёх сторон квадрата B I; на рис. 21 эти стороны Рис. 21. Продолжеизображены сплошными линиями, а четвертая стоние отображения рона квадрата изображена пунктиром. Все точки луча, выходящего из точки P, отобразим в одну и ту же точку (образ точки пересечения луча с одной из трёх выделенных сторон). Если один конец (или оба конца) ребра B не принадлежит ребру A, то на одной боковой стороне (или на обеих боковых сторонах) отображение задаём произвольно. Затем аналогично строим продолжение отображения для рёбер, граничащих с A и B, и т. д.

Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 44 |










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

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