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

Но при этом возникает одна трудность: если плоскость грани проходит через 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, и т. д.

Пусть p : X X A - естественная проекция. Отображение F1 обла/ - дает следующим свойством: F1 (A) = A. Поэтому существует (единственное) отображение q : X A A, для которого F1 = q p. Для дока/ зательства гомотопической эквивалентности пространств X и X A доста/ точно проверить, что q p idX и p q idX/A. Гомотопия Ft по построению связывает отображения F1 = q p и F0 = idX. А так как Ft (A) A при всех t, то p Ft = qt p, где qt - некоторая гомотопия, связывающая - отображения q0 = idX/A и q1 = p q.

Последовательные переходы от 1-мерного комплекса X к 1-мерному комплексу X A приводят в конце концов к 1-мерному комплексу, у кото/ рого нет рёбер с несовпадающими концами. Такой комплекс представляет собой букет окружностей.

Нетрудно убедиться, что связный 1-мерный комплекс, содержащий nвершин и n1 рёбер, гомотопически эквивалентен букету n1 - n0 + окружностей. Чтобы доказать это, построим максимальное дерево, т. е.

стягиваемый подкомплекс, содержащий все вершины. Фиксируем для этого некоторую вершину P0 и рассмотрим множества Sn, n = 1, 2,..., состоящие из тех вершин, для которых самый короткий путь до Pпроходит ровно через n рёбер. Соединим каждую вершину из множества 44 Глава I. Графы Sn+1 с одной из тех вершин множества Sn, с которыми она соединена ребром (рис. 22). В результате получим максимальное дерево. Оно содержит n0 - 1 рёбер, которые можно последовательно стянуть. После этого получится 1-мерный комплекс с одной вершиной и n1 - n0 + рёбрами, т. е. букет n1 - n0 + 1 окружностей.

Важной характеристикой линейно связного топологического пространства X с отмеченной точкой x0 является его фундаментальная группа 1 (X, x0). Элементами фундаментальной группы служат классы гомотопных петель в X с началом x0, т. е. отображений f : I X отрезка I = [0, 1], для которых f(0) = f(1) = x0. Структура группы на множестве 1 (X, x0) вводится следующим образом. Положим f1 (2t) при 0 t 1 2, / f1 f2(t) = f2 (2t - 1) при 1 2 t 1.

/ Иными словами, за первую половину пути мы с удвоенной скоростью проходим петлю f1, а за вторую половину пути мы с удвоенной скоростью проходим петлю f2.

Единичным элементом фундаментальной группы служит класс, содержащий постоянное отображение f : I x0. Для класса, содержащего петлю f(t), обратным является класс, содержащий петлю g(t) = f(1 - t).

В самом деле, гомотопия при 0 t s 2, / x f(2t - s) при s/2 t 1/2, Fs (t) = f(2 - 2t - s) при 1 2 t 1 - s 2, / / x0 при 1 - s 2 t / (рис. 23) связывает отображения F0 = fg и F1 : I x0.

Рис. 22. Максимальное дерево з 2. Гомотопические свойства графов Рис. 23. Обратный элемент Рис. 24. Ассоциативфундаментальной группы ность умножения С помощью рис. 24 несложно построить гомотопию, связывающую отображения f1 (f2 f3) и (f1 f2) f3.

Пусть - путь в X с началом x1 и концом x2; f - петля с началом - - и концом в точке x1. Тогда -1 f - петля с началом и концом в точке x2.

- Легко проверить, что отображение f -1 f индуцирует изоморфизм группы 1 (X, x1) на группу 1(X, x2). Пути и индуцируют один и тот же изоморфизм тогда и только тогда, когда класс петли -1 принадлежит центру группы 1 (X, x1). В самом деле, петли -1 f и -1 f гомотопны тогда и только тогда, когда петли f(-1) и (-1) f гомотопны.

инейно связное пространство X называют односвязным, если 1 (X, x0) = 0 для некоторой точки x0 X; в таком случае 1 (X, x1) = для любой точки x1 X.

Непрерывное отображение f : X Y естественным образом индуцирует гомоморфизм f : 1 (X, x0) 1 (Y, y0), где y0 = f(x0). При этом гомоморфизме класс, содержащий петлю (t), переходит в класс, содер жащий петлю f((t)). Ясно, что (fg) = f g.

Т е о р е м а 2.2. Пусть ft - гомо - топия, связывающая отображения f0, f1 : X Y. Тогда гомоморфизм (f1) : 1 (X, x0) 1 (Y, f1(x0)) совпа дает с композицией гомоморфизма (f0) : 1 (X, x0) 1 (Y, f0 (x0)) и изоморфизма 1 (Y, f0(x0)) 1 (Y, f1 (x0)), индуцированного путём (t) = ft (x0), соединяющим точки f0 (x0) и f1 (x0).

Д о к а з а т е л ь с т в о. Пусть h - - Рис. 25. Гомотопия некоторая петля в X с началом и концом в точке x0. Требуется доказать, что петли f1 (h(t)) и -1 f0 (h(t)) гомотопны. Рассмотрим отображение F : I I Y, заданное формулой 46 Глава I. Графы F(s, t) = fs (h(t)). Семейство путей, один из которых изображён на рис. 25, представляет собой гомотопию, связывающую петли f1h и -1 (f0h).

Т е о р е м а 2.3. Фундаментальные группы гомотопически эквивалентных линейно связных топологических пространств изоморфны.

Д о к а з а т е л ь с т в о. Предположим, что линейно связные топологические пространства X и Y гомотопически эквивалентны. Тогда существуют отображения f : X Y и g : Y X, для которых fg idY и gf idX. Согласно теореме 2.2 гомоморфизмы g f : 1 (X, x0) 1 (X, gf(x0)) и f g : 1 (Y, y0) 1 (Y, fg(y0)) являются композициями тождественного отображения и изоморфизма, т. е. изоморфизмами.

Рассмотрим гомоморфизмы ( ( f1) g f2) 1 (X, x0) - 1 (Y, f(x0)) - 1(X, gf(x0)) - 1(Y, fgf(x0)).

( ( (Здесь f1) и f2) - гомоморфизмы фундаментальных групп с разными - отмеченными точками, индуцированные одним и тем же отображением f.) ( Гомоморфизм g f1) - изоморфизм, поэтому g - эпиморфизм. Гомомор - - ( физм f2) g - изоморфизм, поэтому g - мономорфизм. В итоге получа - - ем, что g - изоморфизм.

- Из теорем 2.1 и 2.3 следует, что фундаментальная группа связного 1-мерного комплекса изоморфна фундаментальной группе некоторого букета окружностей. А именно, фундаментальная группа связного 1-мерного комплекса, содержащего n0 вершин и n1 рёбер, изоморфна фундаментальной группе букета n1 - n0 + 1 окружностей.

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