WWW.DISSERS.RU

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

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

Pages:     | 1 |   ...   | 23 | 24 || 26 | 27 |   ...   | 49 |

Нетрудно понять, что граф вкладывается в плоскость R2 тогда и только тогда, когда он вкладывается в сферу S2. Можно рассматривать вложения графов не только в сферу S2, но и в другие поверхности. Например, граф K6 можно расположить на проективной плоскости P2, а графы Kи K4,4 можно расположить на торе (рис. 74).

Рис. 74. Графы K6, K7 и K4,174 Глава IV. Двумерные поверхности. Накрытия. Расслоения...

Т е о р е м а 13.1 (Кёниг [83]). а) Любой конечный граф G можно вложить в некоторую замкнутую ориентируемую двумерную поверхность M2.

б) Если граф G связен, а поверхность M2 имеет минимальный род, то каждая из областей, на которые граф G разбивает M2, гомеоморфна диску.

Д о к а з а т е л ь с т в о. а) Если допустить пересечения рёбер, то любой граф можно расположить на сфере. Устранить пересечения можно, приклеив к сфере ручки. При этом одно ребро остаётся на сфере, а другое проходит по ручке (рис. 75).

б) Достаточно рассмотреть случай, когда граф G не имеет двойных рёбер. Пусть U1,..., Um – области, на которые граф G – разбивает M2. По условию граф G связен и не имеет двойных рёбер, поэтому граница каждой из областей Ui гомеоморфна окружРис. 75. Устранение пересечений рёбер ности. Область Ui стягиваема тогда и только тогда, когда в результате приклеивания диска D2 к Ui (по границе) получается сфера S2. Предположим, что одна из областей Ui нестягиваема. Если мы вырежем из M2 область Ui и приклеим вместо неё D2, то в результате граф G окажется расположенным на поверхности M2, род которой строго меньше рода поверхности M2.

Это противоречит минимальности рода поверхности M2.

З а м е ч а н и е 1. Если граф можно расположить на ориентируемой поверхности M2, то его можно расположить и на неориентируемой поверхности M2 # P2.

З а м е ч а н и е 2. Если граф G разбивает поверхность M2 на стягиваемые области, то род поверхности M2 не обязательно минимален.

Например, букет двух окружностей можно расположить требуемым образом как на сфере, так и на торе.

Минимальный род ориентируемой поверхности, на которой можно расположить граф G, называют родом графа. Род графа G будем обозначать g(G).

Т е о р е м а 13.2. Пусть G – связный граф без петель и двойных – рёбер, содержащий v вершин и e рёбер. Тогда e v g(G) - + 1, 6 а если граф G не содержит циклов длины 3, то e v g(G) - + 1.

4 § 13. Графы на поверхностях. Взрезанный квадрат графа Д о к а з а т е л ь с т в о. Можно считать, что все области, на которые граф G разбивает поверхность M2, стягиваемы. В таком случае 2 - 2g(M2) = v - e + f, где f – число областей, на которые граф G – разбивает M2. Если граница каждой области состоит не менее чем из n рёбер, то nf 2e, поэтому 1 2 n - 2 v g(G) g(M2) 2 - v + e 1 - = e - + 1.

2 n 2n По условию у графа G нет петель и двойных рёбер. Это означает, что n 3, т. е. (n - 2) 2n 1 6. Если же у графа G нет ещё и циклов длины 3, / / то n 4, т. е. (n - 2) 2n 1 4.

/ / (n - 3) (n - 4) П р и м е р. g(Kn).

n(n - 1) Д о к а з а т е л ь с т в о. Число рёбер графа Kn равно, поэтому n(n - 1) n n2 - 7n + 12 (n - 3) (n - 4) g(Kn) - + 1 = =.

12 2 12 (m - 2) (n - 2) П р и м е р. g(Km,n).

Д о к а з а т е л ь с т в о. Число вершин графа Km,n равно m + n, а число рёбер равно mn. Кроме того, у графа Km,n нет циклов длины 3.

Поэтому mn m + n (m - 2) (n - 2) g(Km,n) - + 1 =.

4 2 Доказанные нами оценки для рода графов Kn и Km,n нельзя улучшить.

А именно, для графа Kn (соответственно, для графа Km,n) существует вложение в ориентируемую поверхность рода, равного наименьшему (n - 3) (n - 4) целому числу, которое больше или равно (соответственно, (m - 2) (n - 2) ). Примеры таких вложений строятся достаточно сложно, особенно для графов Kn. Впервые такие примеры для Kn построены Рингелем и другими в [109], [110] и [94]. Примеры вложений графов Km,n построены в [108]. Более современное изложение этих конструкций приведено в [63].

13.2. Раскраски карт Будем говорить, что на поверхности M2 любую карту можно раскрасить в n цветов, если вершины любого графа (без петель), кото176 Глава IV. Двумерные поверхности. Накрытия. Расслоения...

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

Для двойственного графа получается раскраска, при которой соседние области разноцветные.

Т е о р е м а 13.3 (Хивуд [69]). Любую карту на замкнутой ориентируемой поверхности рода g > 0 можно раскрасить в 7 + 1 + 48g цветов.

Д о к а з а т е л ь с т в о. Если e – ребро – графа G, то любая правильная раскраска вершин графа G является также правильной Рис. 76. Двойственный раскраской графа G - e. Поэтому проведение граф дополнительного ребра не может уменьшить количество цветов, которое нужно для раскраски вершин графа. Таким образом, после проведения дополнительных рёбер можно считать, что граф G разбивает поверхность M2 на треугольные стягиваеg мые области. В таком случае 2e(G) = 3f(G), поэтому из равенства v(G) - e(G) + f(G) = 2 - 2g следует, что e(G) = 3v(G) + 6g - 6. Ясно также, что сумма степеней вершин графа G равна 2e(G), поэтому степень одной из вершин не превосходит 2e(G) 12(g - 1) = 6 +. (1) v(G) v(G) Предположим, что число n таково, что у любого графа на поверхности рода g есть вершина степени не более n - 1 (отметим, что число n = 7 + 12(g - 1) таким свойством обладает). Тогда индукцией по числу вершин графа легко доказывается, что любой граф на поверхности рода g можно раскрасить в n цветов. Действительно, если после выбрасывания из графа G вершины v, степень которой не превосходит n - 1, получается граф, который можно раскрасить в n цветов, то и сам граф G можно раскрасить в n цветов (для окраски вершины v остаётся по крайней мере один цвет).

Пусть n(g) – минимальное число цветов, которыми можно раскрасить – любую карту на поверхности рода g (число n(g) конечно, потому что любую карту на поверхности рода g можно раскрасить в 7 + 12(g - 1) цветов). Рассмотрим граф G, для которого это минимальное число n(g) реализуется и, кроме того, выполняется оценка (1). Ясно, что v(G) n(g), § 13. Графы на поверхностях. Взрезанный квадрат графа поэтому если g 1, то 12(g - 1) 12(g - 1) n(g) 7 + 7 +.

v(G) n(g) (Обратите внимание, что для сферы это неравенство неверно.) Решая неравенство n(g)2 - 7n(g) 12g - 12 и учитывая неравенство n(g) > 0, получаем требуемое.

Неравенство n(g)2 - 7n(g) 12g - 12 можно переписать в виде (n(g) - 3) (n(g) - 4) g.

Это неравенство тесно связано с неравенством (n - 3) (n - 4) g(Kn).

Действительно, если граф Kn вкладывается в поверхность рода g, то n(g) n, поскольку для раскраски графа Kn требуется n цветов.

Примеры вложений графов Kn в ориентируемые поверхности, построенные Рингелем и другими, показывают, что 7 + 1 + 48g n(g).

Соединив эти неравенства с неравенствами Хивуда, получим 7 + 1 + 48g n(g) =.

Напомним, что в случае g = 0 рассуждения Хивуда применить нельзя.

13.3. Взрезанный квадрат графа Взрезанным квадратом симплициального комплекса K называют j подпространство в |K K |, состоящее из всех произведений i, j где i и – непересекающиеся симплексы в K. Взрезанный квадрат K – имеет естественную структуру CW -комплекса. Количество его вершин равно n2 - n, где n – количество вершин K.

– Граф G, не имеющий петель и двойных рёбер, можно рассматривать как 1-мерный симплициальный комплекс с тем же самым множеством вершин. Поэтому для графа можно рассмотреть взрезанный квадрат. Если у графа есть пара непересекающихся рёбер, то взрезанный квадрат – 2-мерный CW -комплекс. В дальнейшем мы будем предполагать, – что у графа G есть пара непересекающихся рёбер.

178 Глава IV. Двумерные поверхности. Накрытия. Расслоения...

Т е о р е м а 13.4. а) Взрезанный квадрат графа G является замкнутым двумерным псевдомногообразием (не обязательно связным) тогда и только тогда, когда после выбрасывания из графа G любой пары вершин vi и vj, соединённых ребром, остаётся набор циклов, т. е. из любой вершины vk {vi, vj}, выходит ровно два ребра, идущих не в вершины vi и vj.

б) Если граф G 2-связен (т. е. он остаётся связным после выбрасывания любой вершины), то его взрезанный квадрат связен.

Д о к а з а т е л ь с т в о. а) Пусть из вершины vk {vi, vj} выходят рёбра vkvp,..., vkvp, где vp,..., vp {vi, vj}. Тогда во взрезанном 1 s 1 s квадрате графа G к ребру vk vivj примыкают грани vkvp vivj, = 1,..., s. Поэтому взрезанный граф является замкнутым псевдомногообразием тогда и только тогда, когда s = 2 для всех троек вершин {vi, vj, vk}.

б) Вершины vi vj и vp vq можно соединить рёбрами следующим образом. Если p = j, то можно сначала соединить vi vj с vp vj, а за тем vp vj с vp vq. Чтобы соединить вершины vi vj и vj vi, выберем вершину vk {vi, vj} и сначала соединим vi vj с vk vj, затем vk vj с vk vi, а затем vk vi с vj vi.

Условие теоремы 13.4 выполняется для графов K5 и K3,3. Поэтому их взрезанные квадраты – связные замкнутые поверхности.

– З а д а ч а 13.1. [120] Докажите, что взрезанный квадрат графа K3,3 – сфера с четырьмя ручками, а взрезанный квадрат графа K5 – – – сфера с шестью ручками.

З а д а ч а 13.2. Докажите, что взрезанный квадрат графа не может быть сферой с нечётным числом листов Мёбиуса.

§ 14. Расслоения и гомотопические группы Понятие локально тривиального расслоения со слоем F является обобщением понятия накрытия. Для накрытия слой F дискретен, а для локально тривиального расслоения слой может быть произвольным топологическим пространством. При обсуждении свойств расслоений нам понадобится понятие гомотопической группы, которое является обобщением понятия фундаментальной группы.

14.1. Накрывающая гомотопия Локально тривиальным расслоением называют четвёрку (E, B, F, p), где E, B и F – топологические пространства, p : E B – – – отображение, обладающее следующими свойствами:

§ 14. Расслоения и гомотопические группы – у любой точки x B есть окрестность U, для которой p-1 (U) – U F;

– гомеоморфизм U F p-1 (U) согласован с отображением p, т. е.

– диаграмма U F p-1 (U) p U коммутативна (здесь U F U – проекция на первый множитель).

– Пространства E, B и F называют, соответственно, пространством расслоения, базой и слоем; отображение p называют проекцией.

Часто для краткости расслоением мы будем называть само отображение p : E B.

П р и м е р. Накрытие p : X X является локально тривиальным расслоением со слоем F = p-1 (x), x X.

П р и м е р. Естественная проекция p : B F B является локально тривиальным расслоением. Это расслоение называют тривиальным.

Расслоения p1 : E1 B и p2 : E2 B называют эквивалентными, если существует такой гомеоморфизм h: E1 E2, что p1 = p2h. Расслоение, эквивалентное тривиальному, тоже называют тривиальным.

Т е о р е м а 14.1 (Фельдбау). Локально тривиальное расслоение над кубом Ik тривиально.

Д о к а з а т е л ь с т в о. Покажем сначала, что если куб Ik =Ik-1 I k разбит на два полукуба Ik = Ik-1 0, и I+ = Ik-1, 1, причём 2 над каждым из них расслоение тривиально, то расслоение тривиально и над всем кубом Ik. Иными словами, если заданы гомеоморфизk k мы h± (I±) F I±, согласованные с проекцией, то по ним можно построить гомеоморфизм h: p-1 (Ik) F Ik, согласованный с проекцией. Согласованность с проекцией означает, что если y p-1 (x), то h(y) = (f, x), f F. Поэтому гомеоморфизм h задаётся семейством гомеоморфизмов x : p-1 (x) F, x I. На множестве p-1 (Ik ) в качестве h можно взять h-, т. е. считаем, что x = x,- при x Ik. Для 1мы k точки a Ik I+ = Ik-1 заданы два гомеоморфизма p-1 (x) F, а именно, a,+ и a,-. Рассмотрим гомеоморфизм a =a,- (a,+)-1 : F k F и с его помощью определим гомеоморфизм x для x I+ следующим k образом. Пусть a(x) – ортогональная проекция точки x I+ на перего– 1 родку Ik-1. Положим x =a(x)x,+. Для точки x =aIk-2 это определение согласовано с предыдущим, поскольку aa,+ = 180 Глава IV. Двумерные поверхности. Накрытия. Расслоения...

= a,- (a,+)-1a,+ = a,-. Из этого следует, что семейство гомеоморфизмов x непрерывно зависит от x, а значит, оно задаёт гомеоморфизм h: p-1 (Ik) F Ik, согласованный с проекцией.

Теперь требуемое утверждение легко доказать методом от противного. Действительно, предположим, что над кубом Ik задано локально тривиальное расслоение, которое не является тривиальным. Разрежем куб Ik на два полукуба. Из доказанного выше утверждения следует, что над одним из полукубов расслоение нетривиально. Разрежем теперь его и т. д. В результате можно получить последовательность параллелепипедов, диаметры которых стремятся к нулю, причём над каждым параллелепипедом расслоение нетривиально. Более того, эта последовательность параллелепипедов сходится к некоторой точке x0. По определению у точки x0 есть окрестность, над которой расслоение тривиально. Один из рассматриваемых параллелепипедов целиком лежит в этой окрестности, поэтому расслоение над ним тривиально. Получено противоречие.

Пусть p : E B – локально тривиальное расслоение, f : X B – – – некоторое отображение. Мы будем говорить, что отображение f : X E накрывает отображение f, или является поднятием отображения f, если p f = f.

Для расслоений выполняется свойство, во многом похожее на существование поднятия пути для накрытий. Основное отличие заключается в том, что для накрытий поднятие пути с заданным началом единственно, а для расслоений верна только теорема существования.

Т е о р е м а 14.2 (о накрывающей гомотопии). Пусть p : E B – – локально тривиальное расслоение, X – CW -комплекс, X X – его – – подкомплекс. Предположим, что заданы:

– отображение h: X E;

– – гомотопия H : X I B отображения h = ph;

– – гомотопия H : X I E, накрывающая ограничение на X I – гомотопии H и продолжающая отображение h: X {0} E, ограниченное на X {0}.

Тогда существует гомотопия H : X I E, которая накрывает гомотопию H и одновременно является продолжением гомото пии H и отображения h: X {0} E.

Д о к а з а т е л ь с т в о. Рассмотрим сначала случай, когда расслоение тривиально, т. е. E = B F и p(b, f) = b. В этом случае отображение H задаётся покомпонентно двумя отображениями: в B и в F. Отображение в B совпадает с отображением H, поэтому остаётся построить отображение в F. Для этого достаточно применить следующее утверждение, которое бывает полезно и во многих других ситуациях.

Pages:     | 1 |   ...   | 23 | 24 || 26 | 27 |   ...   | 49 |



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

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