Содержание к диссертации
Введение
1. Базисные вложения графов 20
1.1. Примеры и план доказательств 20
1.1.1. Примеры на базисные вложения 20
1.1.2. Вычисления дефекта графов 21
1.1.3. Частные случаи теоремы 1.1 22
1.1.4. План доказательства теоремы 1.1 23
1.2. Необходимые условия базисной вложимости 24
1.2.1. Геометрический критерий базисного вложения 24
1.2.2. Ограничение на первое число Бетти графа 25
1.2.3. Охлопывание базисного вложения 26
1.2.4. Доказательство необходимости в теореме 1.1 28
1.2.5. Грубое ограничение на дефект графа 29
1.2.6. Тонкое ограничение на дефект графа 32
1.3. Конструкция универсальных графов 34
1.3.1. Универсальные листья и сердцевина 35
1.3.2. Тонкая ветвь 36
1.3.3. Толстая ветвь 37
1.3.4. Универсальное дерево 37
1.3.5. Универсальный граф 38
1.4. Построение базисного вложения 40
1.4.1. Сильно базисное и совершенно базисное вложения 40
1.4.2. Совершенно базисное вложение универсального листа 41
1.4.3. Совершенно базисное вложение сердцевины 42
1.4.4. Совершенно базисное вложение тонкой ветви 43
1.4.5. Совершенно базисное вложение толстой ветви 46
1.4.6. Сильно базисное вложение универсального дерева 48
1.4.7. Базисное вложение универсального графа 50
1.5. Доказательство достаточности в теореме 1.1 50
1.5.1. Случаи плоскости R х R и цилиндра К х S1 51
1.5.2. Редукция к связному дереву 52
1.5.3. Выделение удовлетворительных точек 53
1.5.4. Выделение сердцевины 54
1.5.5. Достраивание тонкой и толстой ветвей 55
1.5.6. Окончание доказательства теоремы 1.1 56
1.6. Доказательство следствий 1.1-1.6 56
1.6.1. Доказательство следствий 1.1 и 1.2 56
1.6.2. Доказательство следствия 1.3 58
1.6.3. Доказательство следствий 1.4, 1.5 и 1.6 62
2. Метод трехстраничных вложений И. А. Дынникова 64
2.1. Геометрический смысл полугрупп RSGn и NSGn 64
2.1.1. Геометрический смысл букв алфавита А„ 64
2.1.2. Локальные движения в трехстраничном подходе 66
2.1.3. План доказательства теоремы 2.1 68
2.2. Трехстраничные вложения заузленных графов 69
2.2.1. Формальное определение трехстраничного вложения 69
2.2.2. Построение трехстраничного вложения 70
2.2.3. Доказательство теоремы 2.1а 72
2.2.4. Сбалансированные слова в алфавите А„ 72
2.3. Графовые плетения и трехстраничные плетения 73
2.3.1. Графовые плетения 73
2.3.2. Полугруппа RGTn графовых плетений 74
2.3.3. Трехстраничные плетения 76
2.4. Доказательства основных результатов 78
2.4.1. Полугруппа RBTn почти сбалансированных плетений 78
2.4.2. Доказательство теоремы 2.16 79
2.4.3. Доказательство теоремы 2.1в и следствий 2.1а, 2.2а 80
2.4.4. Случай нежесткой изотопии и заузленных J-графов 81
2.5. Доказательство леммы 2.3 82
2.5.1. Новые эквивалентности слов в полугруппе RSGn 82
2.5.2. Разложение г-сбалансированных слов 84
2.5.3. Вывод соотношений <р(11) - <>(23) из (1)-(10) 87
2.6. Приложения метода трехстраничных вложений 90
2.6.1. Группа заузленного графа и многочлен Александера 90
2.6.2. Классификация заузленных цепочек 93
2.6.3. Трехстраничный индекс заузленных графов 96
2.6.4. Группы, ассоциированные с полугруппами RSGn, NSGn 100
Литература ЮЗ
- Необходимые условия базисной вложимости
- Построение базисного вложения
- Достраивание тонкой и толстой ветвей
- Построение трехстраничного вложения
Введение к работе
Настоящая диссертация представляет собой исследование по современной геометрической топологии. В первой главе изучаются базисные вложения графов. Во второй главе вводится взаимно однозначное кодирование для всех изотопических классов заузленных графов в Е3. Результаты обеих глав основаны на геометрических методах построения вложений графов в книжку со страницами. Во введении даются мотивировки исследований, вводятся ключевые понятия, формулируются известные результаты и теоремы автора.
1. Базисные вложения графов.
Первый параграф введения относится к главе 1. В пункте 1.1 обсуждаются вопросы, которые привели к понятию базисного вложения. В пункте 1.2 даются необходимые определения и формулируется критерий базисной вложимости графов в книжку со страницами (теорема 1.1). Пункт 1.3 посвящен следствиям этого критерия о запрещенных и универсальных семействах графов.
1.1. Истоки базисных вложений графов.
Под топологическим вложением понимается гомеоморфизм на образ. Свойство базисности усиливает понятие топологического вложения. Это свойство связано с вопросом представления непрерывных функций многих переменных на компактах в виде суперпозиции непрерывных функций меньшего числа переменных. Базисные вложения стали изучаться в работах, мотивированных решением А. Н. Колмогорова и В. И. Арнольда 13-й проблемы Д. Гильберта. Д. Гильберт сформулировал свою знаменитую 13-ю проблему так: "доказать, что уравнение 7-й степени х7 + ах3 + Ьх2 + сх + 1 = 0 имеет решения (непрерывно зависящие от параметров а, Ь, с), которые не выражаются в виде суперпозиции непрерывных функций только двух аргументов". А. Н. Колмогоров каждую непрерывную функцию многих переменных сумел представить в виде суперпозиции непрерывных функций только трех переменных [б]. В. И. Арнольд случай трех переменных свел к случаю двух[1], см. также [2]. После этого А. Н. Колмогоров доказал, что каждая функция, непрерывная на n-мерном кубе 1п, представляется в виде суммы (2n + 1)-ой непрерывной функции одного переменного [7]. Ниже формулируется только ослабленная версия этой теоремы. Через С(Х, Y) обозначается пространство непрерывных функций X —> Y.
Теорема 1А (А. Н. Колмогоров [7]). При п > 2 существует такое семейство функций {(fi}f=tl с C(In;R), что любая функция / C(In;R) представляется в виде f{x) = ^+1 ді{ч>і(х)), х = (хи ...,хп)е 1п, дг Є C(R; R).
Теорема А. Н. Колмогорова не только опровергла гипотезу Д. Гильберта, но и поставила много новых вопросов. Обсуждение некоторых из них см. в [38, введение]. Здесь будет затронуто только одно направление, которое привело к понятию базисного вложения. В теореме 1А ключевую роль играет фиксированное семейство непрерывных функций {ifi}^1. Из этой теоремы следует, что непрерывное отображение ip = (: In —> K2n+1 разделяет точки куба /", т.е. является топологическим вложением. Я. Штернфельд переформулировал функциональную теорему А. Н. Колмогорова на топологическом языке, введя понятие базисного вложения [38, стр. 4].
Определение 1.1 (базисное вложение). Пусть X и Хі (1 < г < к) — компактные метрические пространства, а рг : X —» Хі — непрерывные функции. Семейство {ірі}і=і называется базисным, если каждая функция / Є С(Х;Ж) представляется в виде f(x) = ^=1^ 9і(<Рі(х))і гДе х Є X, ді Є С(Хі]Ж), 1 < г < к. Вопрос существования базисного семейства для пространств X,Хх,...Х^ является топологическим, т.е. ответ на него зависит только от топологии пространств X и Хі (1 < і < к). Кроме того, базисное семейство задает вложение (р = (ірк) ' X с Пі=і Х-іі которое называется базисным и обозначается X Съ Пг=і Х-і. Данное определение можно короче сформулировать следующим образом [38, предложение 8. (і) на стр. 5]. Вложение X С Пг=і ^ называется базисным, если любая функция / Є С(Х;Щ представляется в виде f(x) = ZLi&O^)' ГДе 9і Є С{Хі\Ж), х = (хі,...,хк) Є X, хг Є Хі.
Таким образом, свойство базисности усиливает понятие топологического вложения. В пункте 1.1.1 первой главы диссертации рассматриваются примеры базисных и небазисных вложений в R х Ж. Из теоремы А. Н. Колмогорова следует, что n-мерный куб Іп базисно вкладывается в R2n+1. Здесь и далее под Шт понимается прямое произведение т экземпляров прямой Ш. П. Остранд обобщил теорему 1А на произвольные компакты. Ниже формулируется только частный случай теоремы П. Остранда в терминах базисных вложений.
Теорема 1В (П. Остранд [33]). Любое n-мерное компактное метрическое пространство базисно вкладывается в М2""1"1.
Оказалось, что число 2п + 1 в теоремах 1А и 1В нельзя уменьшить.
Теорема 1С (Я. Штернфельд [38, теорема 1.12]). При п > 2 любое п-мерное компактное метрическое пространство не вкладывается базисно в R2".
Итак, согласно теоремам 1В и 1С произвольное компактное метрическое пространство X базисно вкладывается в Rm (т > 3) тогда и только тогда, когда dimX < ш^-. Последнее утверждение усиливает известную теорему Небелинга-Менгера о том, что любое n-мерное компактное метрическое пространство X топологически вкладывается в K2"+1. Заметим, что в отличие от топологического вложения, понятие базисного вложения позволяет охарактеризовать размерность компакта в терминах непрерывных функций на нем. При т — 1 понятия топологического и базисного вложения совпадают, но случай плоскости т = 2 еще до конца не разобран. Известно только описание линейно
&
связных 1-мерных компактов, базисно вложимых вЕх! [36, теорема 3]. Недавно появилось простое доказательство критерия Я. Штернфельда базисного вложения в плоскость R х R [31]. Также было доказано, что для конечных графов базисная вложимость вЕхМв непрерывном смысле эквивалентна базисной вложимости в гладком смысле1 [14]. Если прямую Ш заменить на 1-мерный компакт, то размерность 2тг + 1 в теоремах 1А и 1В можно уменьшить.
Теорема ID (Я. Штернфельд [38, замечание о теореме 4.6 на стр. 29]). Пусть п > 1 и X — произвольное n-мерное компактное метрическое пространство. Тогда компакт X базисно вкладывается в Шх П"-і Хі, где Хі — некоторые 1-мерные компакты (1 < г < п).
Последняя теорема тривиальна при п = 1. Однако, в этом случае можно рассмотреть следующие две открытые проблемы.
Задача 1а. Для данного 1-мерного компакта У (например, У — букет нескольких отрезков и окружностей) описать все 1-мерные компакты X, базисно вложимые в произведение2 ЕхУ.
Задача 16. Для данного 1-мерного компакта X (например, X — конечный граф) найти такой минимальный (по вложению) 1-мерный компакт У, что компакт X базисно вкладывается в произведение R х У.
В обзоре по открытым проблемам геометрической топологии [18] задача 1а была сформулирована в случае, когда X — конечный граф, а У — букет нескольких отрезков. В такой постановке задача 1а эквивалентна проблеме ха-рактеризации конечных графов X, базисно вложимых в книжку со страницами К х У. Задача 16 является частным случаем вопроса, который изучался Я. Штернфельдом [39]. В качестве следствия Я. Штернфельд охарактеризовал размерность произвольного дендрита (линейно связного компакта, не содержащего гомеоморфного образа окружности) в терминах нульмерных отображений (прообразы всех точек которых нульмерны) в другие дендриты.
В диссертации дается решение задачи 1а в случае, когда X — произвольный конечный граф, а У — букет отрезков и окружностей (теорема 1.1). Задача 16 решается для любого конечного графа X (следствие 1.2).
1.2. Критерий базисной вложимости графов.
Опишем класс графов, базисные вложения которых будут рассматриваться. Под конечным графом G понимается произвольный 1-мерный клеточный комплекс с конечным числом клеток. Его 0-мерные клетки называются вершинами, а 1-мерные — ребрами. Ребро / примыкает к вершине v, если точка v содержится в замыкании клетки /. Степень deg v вершины v Є G равна числу ребер графа G, примыкающих к ней. Вершины степени 0 называются изолированными. Граф может быть несвязным, но изолированные вершины не рассматриваются. Мулъти-ребро — это набор ребер, примыкающих к одной паре вершин, а петля — ребро, примыкающее ровно к одной вершине. Все графы считаются
Определение гладкого базисного вложения получается из последнего предложения определения 1.1 заменой в двух местах непрерывных функций на гладкие.
2Поскольку рассматриваются вложения компактов, произведение R х У можно заменить на [0,1] х Y.
неориентированными, допускаются мульти-ребра и петли. Графы изучаются с точностью до произвольного гомеоморфизма3. Для формулировки основного результата введем дополнительные понятия.
Определение 1.2 (склеенная книжка RxTn,m, ось ШхО). Для целых чисел п, т > 0 (п + 2т > 2) возьмем п отрезков, в каждом из которых выделен один конец, и т окружностей, в каждой из которых выделено по точке. Через Тпт обозначим букет всех этих отрезков и окружностей, в котором все выделенные точки склеиваются в одну: Tn>m = V"=1// V^L1 S]. Точка склейки в букете Тп_то будет считаться центром букета и обозначать через О. Произведение Шх Тпт назовем склеенной книжкой. Она состоит из п полуплоскостей и т цилиндров, склеенных вместе вдоль оси Ж х О.
Через #G обозначим количество связных компонент конечного графа G. По определению первое число Бетти b(G) графа G равно #G — x(G), где x(G) — эйлерова характеристика графа G. Цикл S С G — это подграф, гомеоморфный окружности. Например, дерево — это связный граф G без циклов (с первым числом Бетти b(G) = 0).
Определение 1.3 (сложные вершины и дефект 5(G)). Ребро, примыкающее к вершине степени 1, будет называться висячим. Вершина v Є G считается нер аз в етв ленной, если к ней примыкает висячее ребро, и разветвленной в противном случае. Вершина v Є G называется сложной, если либо ее степень degv > 5, либо degt» = 4 и она является разветвленной. Дефект 5(G) графа G — это сумма Y2(degv ~ 2) по всем сложным вершинам v графа G.
В пункте 1.1.2 первой главы диссертации дефект вычисляется для нескольких серий известных графов. Следующая теорема 1.1 решает задачу 1а (см. пункт 1.1) для случая, когда X — произвольный конечный граф, a Y = Тп^т.
Теорема 1.1. Фиксируем целые числа п, т > 0 (п + 2т > 2). Конечный граф G базисно вкладывается в книжку Ж х Tnm тогда и только тогда, когда его первое число Бетти b(G) < т и либо дефект 8(G) < п+2т, либо 5(G) — п+2т и одна из сложных вершин графа G является нер аз в етв ленной.
Теорема 1.1 для случая плоскости Кх R (п = 2, т — 0) дает такой критерий: "конечный граф G базисно вкладывается в R х Е тогда и только тогда, когда b(G) = 0 (т.е. G не имеет циклов) и 5(G) = 0 (т.е. G не содержит сложных вершин)". Этот результат эквивалентен характеризации (данной А. Б. Скопен-ковым в терминах запрещеных подграфов) конечных графов, которые базисно вкладываются вЕхЁ [36, теорема 1]. Другие частные случаи теоремы 1.1 подробно разбираются в пункте 1.1.3 первой главы.
Самая существенная часть теоремы 1.1 (при т = 0) доказана в [28]. На произвольное т > 0 результаты обобщены в [11, 29]. Теорема 1.1 дает эффективный критерий базисной вложимости конечных графов в книжку Ж х Тпт.
3Всюду в диссертации гомеоморфизм обозначается через «.
8.
Следствие 1.2. Для любых конечных графов X, Y существует конечный граф, который нельзя базисно вложить в произведение XxY. С другой стороны, для каждого конечного графа G существует такой минимальный (по вложению) букет ТП)ТП, что граф G базисно вкладывается в книжку R х ГП)ГП. При этом т = b{G), и если все сложные вершины графа G являются разветвленными, то п = max{0,S(G) - 2b{G) + I}, иначе п = max{0,5(G) - 26(G)}.
Следствие 1.2 означает, что не существует одного универсального произведения X х Y, в которое можно базисно вложить все конечные графы. Зато семейство произведений {їх ТПіГП | п, т > 0, п + 2т > 2} является универсальным, в том смысле, что для каждого конечного графа G найдется свое произведение ^ х Тп>т, куда граф G вкладывается базисно.
1.3. Запрещенное и универсальное семейства графов.
Многие теоремы геометрической топологии сформулированы в терминах запрещенных графов. Среди них — известная теорема Куратовского [27] о характеризации планарных графов. Для базисных вложений в книжку R х Tn>m также можно указать конечное запрещенное семейство.
Определение 1.4 {запрещенное семейство). Семейство графов {Рг(Тпт)} называется запрещенным (для базисных вложений в книжку R х Т„!ГП), если
все графы Рі(Тп>т) базисно невложимы в книжку К х ТП]ТП, и
любой граф, базисно невложимый в книжку їх ТПіТП, содержит подграф, гомеоморфный некоторому графу из семейства {Рі{ТПіГП)}.
Следствие 1.3. При фиксированных n, m > 0 (п + 2тп > 2) существует конечное запрещенное семейство графов для базисных вложений elx ТП)ГП.
Следствия 1.2 и 1.3 получены в [11, 29]. Следствие 1.3 допускает уточнения в некоторых частных случаях. А именно, запрещенные семейства будут найдены в явном виде для пар [п,т] = (0,1),(3,0),(1,1) в следствиях 1.4, 1.5 и 1.6 соответственно. Например, для базисных вложений в цилиндр R х S1 есть ровно 6 запрещенных графов, для книжки с тремя страницами R х Т3;о — 8 запрещенных графов, а для цилиндра с приклеенной полуплоскостью R х Гід — 16 запрещенных подграфов.
Определение 1.5 {универсальное семейство). Семейство графов {/;(ТЯіт)} называется универсальным (для базисных вложений в книжку R х Тпт), если
все графы Ui(Tn,m) базисно вкладываются в книжку R х Тп>т, и
любой граф, базисно вложимый в книжку R х ТП)ГП, содержится в некотором графе из семейства {Ui{Tnm)}.
X >±<
S U S 7о,2 з,з -^5>
Рисунок 1.1. Запрещенные графы для цилиндра Rx S1.
Т"
"4,0
грі
ems1:
EMS1)
,/-k_/_
,/-
.^-
V-
U3(Sl)
,/
///
/
/ /
/
кін/ _/
Рисунок 1.2. Универсальные графы для цилиндра 1x5і.
Чтобы определить универсальные графы ET^S1) для всех к Є N, введем понятие универсального листа 14 (IR).
Определение 1.6 {универсальный лист E4(R), корень). Пусть L\ — Т30 — триод, одна из висячих вершин которого считается корнем, а две другие — крайними. Тогда при к > 1 дерево Lfc+i получается из Ьь приклейкой двух висячих ребер5 в каждой крайней вершине. Крайними вершинами нового дерева
4На рисунках 1.1-1.6 жирные точки обозначают сложные вершины, а толстыми линиями выделены сети графов, см. определение 1.25 в пункте 1.6.2.
5Висячее ребро всегда приклеивается по одному из своих концов.
Lk+i будут висячие вершины всех новых приклеенных ребер. Затем в каждой невисячей вершине дерева Lk приклеим одно висячее ребро. Построенное дерево 4(R) называется универсальным листом с корнем г Є Li С 4(R) (см. рисунок 1.8 в пункте 1.4.2).
По определению лист С/о (К) — отрезок (висячее ребро) и C4(R) ~ Т4]о- В пункте 1.5.1 будет доказано, что все универсальные лисья {/fc(R)} образуют семейство универсальных графов для базисных вложений в плоскость R х R (случай п = 2,т = 0). Универсальный граф 4(51) получается приклейкой к окружности ровно в к точках по одному висячему ребру и одному универсальному листу6 4(R). Универсальный граф 4(Т3]о) получается склейкой по корням четырех универсальных листьев 4-і (К) и одного висячего ребра.
Следствие 1.5. Конечный граф G базисно вкладывается в R х Т3}о тогда и только тогда, когда выполнено одно из следующих эквивалентных условий:
(1.5а) граф G не содержит запрещенные подграфы с рисунка 1.3;
(1.56) граф G содержится в некотором универсальном графе /і(Т3іо) (где і > I), см. рисунок 1.4 при і = 1,2,3,4.
Т5,о U Т4'0
м,о ^ -м,о
X хх
ьчьч
^5,0 L-l ^4,0
а4,0 u -4,0
Рисунок 1.3. Запрещенные графы для книжки R х Т3]о-
Ui(T3>0)
/з(Тз,о)
ВД.о)
Ь\(Т3>0)
Рисунок 1.4. Универсальные графы для книжки R х T3i0.
Универсальный лист всегда приклеивается по своему корню.
Следствие 1.6. Конечный граф G базисно вкладывается в R х Т1(1 тогда и только тогда, когда выполнено одно из следующих эквивалентных условий:
(1.6а) граф G не содержит запрещенные подграфы с рисунка 1.5; (1.66) граф G содержится в некотором универсальном графе 7*(Гід) (где і > 1), см. рисунок 1.6 при г = 1,2, 3, 4, 5, 6.
оо со е ж ^ #*
S U S То 2 >5з,з ^б,о т' т" м т „
ЖЖ Ж>$< >$<>$< #>$<
Рисунок 1.5. Запрещенные графы для книжки R х Тід.
Рисунок 1.6. Универсальные графы для книжки Ш х Тід.
Ъ,о L-l ^5,0 ^5,0 U T'iQ T'lfi U Tig Тзд U T{{
2. Метод трехстраничных вложений И. А. Дынникова.
Во второй главе вложения конечных графов в книжку со страницами применяются к задаче взаимно однозначного кодирования изотопических классов заузленных графов ві3. В пункте 2.1 обсуждаются связи заузленных графов с теорией узлов и смежными областями. В пункте 2.2 вводятся необходимые определения, формулируются результаты И. А. Дынникова о кодировании неориентированных зацеплений и теоремы 2.1-2.2 автора. Пункт 2.3 посвящен алгебраическим и геометрическим следствиям теорем 2.1^2.2.
2.1. Заузленные графы в трехмерной топологии.
Заузленные графы — это подмножества G С I3, гомеоморфные конечным графам и рассматриваемые с точностью до объемлющей изотопии. Заузленные графы стали интенсивно изучаться на рубеже 90-х годов прошлого века в работах ведущих специалистов по теории узлов [23, 24, 25]. В этих исследованиях заузленные графы появились как естественные обобщения узлов. Сразу же был получен аналог теоремы Райдемайстера, описывающий заузленные графы в терминах плоских диаграмм, а также построены аналоги полиномиальных инвариантов узлов. В дальнейшем обнаружились важные связи заузленных графов как с самой теорией узлов, так и со смежными областями.
Например, категории тензорных представлений алгебр Хопфа (которые дают полиномиальные инварианты узлов в терминах квантовых групп) были расширены на все заузленные графы [34]. Японские топологи вслед за Таниямой [40] стали изучать заузленные графы, гомеоморфные фиксированному графу G, с точностью до таких известных в алгебраической топологии эквивалентно-стей, как кобордизмы, гомотопии и гомологии. В этом направлении, например, была получена гомологическая классификация заузленных графов [41] и классификация с точностью до пальцевых движений [42]. Благодаря открытым в 1990 году инвариантам Васильева [43] возрос интерес к сингулярным узлам. По определению сингулярные узлы — это заузленные 4-валентные графы, рассматриваемые с точностью до изотопии, в течение которой окрестность каждой вершины графа лежит в некоторой (непостоянной) плоской площадке. Выяснилось, что конструкция Васильева инвариантов конечного типа применима к любым заузленным графам [37]. Несмотря на значительный интерес к заузлен-ным графам, пока нет серьезных продвижений в следующей задаче.
Задача 2. Для любого конечного графа G классифицировать с точностью до объемлющей изотопии в 1R3 все заузленные графы, гомеоморфные G.
Почти единственным общим результатом по этой теме является характе-ризация заузленных графов GcR3, которые изотопны графам, вложенным в плоскость [35]. А именно, заузленный граф G С R3 можно изотопно переместить в плоскость тогда и только тогда, когда абстрактный граф G является планарным и для любого подграфа G' С G фундаментальная группа дополнения 7Гі(Е3 — G') свободна. Важным частным случаем задачи 2 является следующая проблема: для любого заузленного графа G С R3 определить, изотопен ли он своему зеркальному образу. По этому вопросу известно, что планар-
ный 3-связный граф, не имеющий автоморфизмов порядка 2, нельзя вложить в R3 так, чтобы полученный заузленный граф был изотопен своему зеркальному образу [21]. К данному моменту теория заузленных графов уже стала известной темой современной трехмерной топологии. Например, в последний обзор открытых проблем топологии малых размерностей [26] были включены несколько задач (5.15-5.18) по заузленным графам. Среди них — вопрос ха-рактеризации абстрактных самозаузленных графов, любые вложения которых в R3 обязательно содержат нетривиальный узел.
Одним из существенных результатов в теории узлов за последние 5-10 лет является трехстраничный подход И. А. Дынникова к изотопической классификации неориентированных зацеплений в R3 [4, 19]. Метод И. А. Дынникова заключается в изотопном перемещении зацепления в книжку Y = ЕхТ3о с тремя страницами и последующем кодировании полученного вложения. Подобные вложения в книжку с конечным числом страниц, возможно, впервые рассматривались Брюнном в 1898 году [15]. Брюнн доказал, что любой узел изотопен узлу, проекция которого на плоскость R2 имеет ровно одну особую точку. Позднее такие вложения привели к новому инварианту узлов — дуговому индексу [17]. Расширяя свой подход на книжку с произвольным числом страниц, И. А. Дын-ников уменьшил число соотношений в своей кодирующей полугруппе DS [5]. Недавно И. А. Дынников описал алгоритм, распознающий тривиальный узел монотононным образом с помощью прямоугольных диаграмм, которые тесно связаны с вложениями в книжку со страницами [20].
В настоящей диссертации подход И. А. Дынникова обобщается на произвольные заузленные графы. А именно, задача 2 сводится к алгебраической проблеме равенства центральных элементов в двух сериях конечно определенных полугрупп (теоремы 2.1 и 2.2). Кроме того, вопрос об изотопности заузленно-го графа своему зеркальному образу тоже сведен к проблеме равенства слов в конечно определенных полугруппах (следствие 2.1).
2.2. Взаимно однозначное кодирование заузленных графов.
Введем необходимые определения. Будем рассматривать только неориентированные конечные графы без изолированных вершин с точностью до гомеоморфизма. Поскольку висячие ребра нельзя заузлить, они исключаются. Графы могут быть несвязными, также допускаются петли и мульти-ребра (точные определения этих терминов см. в пункте 1.2 введения).
Определение 2.1 (fc-вершины, п-графы, J-графы). Если вершина А графа G имеет степень к, то она кратко называется к-в ершиной. Фиксируем целое п > 2. Если граф G имеет вершины степени только от 2 до п, то назовем его тигр афом. Пусть J = {ji,..., jk} — произвольное множество целых чисел ji > 3. Если граф G содержит А;-вершины только при к = 2 или к Є J, то G будет считаться J-графом.
Например, любой 2-граф состоит из нескольких окружностей, а каждый {4}-граф является по определению 4-валентным графом. Все рассуждения будут
14.
вестись в кусочно-линейной категории, т.е. ребра графа при вложении в М3 считаются конечными ломаными.
Определение 2.2 (заузленный граф, жесткая и нежесткая изотопии).
Заузленный п-граф G С R3 — это подмножество пространства R3, гомеоморф-ное произвольному n-графу G. (См. примеры на левых картинках рисунков 2.11 и 2.12 в параграфе 2.2). Заузленные графы будут изучаться с точностью до двух отношений эквивалентности — жесткой и нежесткой объемлющих изотопии. Нежесткая объемлющая изотопия между двумя заузленными графами G С R3 и Н С R3 — это такое непрерывное семейство гомеоморфизмов
Из определения 2.2 следует, что изотопные графы гомеоморфны, но среди гомеоморфных заузленных графов есть неизотопные друг другу. Например, известно много неизотопных замкнутых кривых в R3, каждая из которых гомеоморфна окружности. Заметим, что введенные выше два понятия объемлющей изотопии совпадают для заузленных 3-графов. Действительно, любую изотопию между заузленными 3-графами можно сделать жесткой. Для этого достаточно держать в некоторой (непостоянной) плоской площадке три дуги, выходящие из каждой вершины. Любой заузленный 2-граф по определению является неориентированным зацеплением. Сингулярные узлы — это заузленные J-графы при J = {4}, рассматриваемые с точностью до жесткой изотопии. Следующая обобщенная теорема Райдемайстера была первым результатом в теории заузленных графов, перенесенным из классической теории узлов.
Теорема 2А (Джониш-Миллет [23]). Заузленные графы жестко (соответственно, нежестко) изотопны тогда и только тогда, когда их плоские диаграммы можно совместить плоскими изотопиями и движениями Райдемайстера R1 — R5 (соответственно, R1 — Д4, R5') с рисунка 2.1.
Rl R2 R3 R3
Рисунок 2.1. Движения Райдемайстера для заузленных графов в R3.
На рисунке 2.1 многоточие между двумя ребрами обозначает последовательность нескольких ребер. Таким образом, движения Райдемайстера для заузлен-ных графов являются локальными, но двумерными. В параграфе 2.1 вводится линейное кодирование заузленных графов и конечное число локальных движений, порождающих любую объемлющую изотопию между графами в К3.
Определение 2.3 (кодирующий алфавит А„). Для каждого п > 2 рассмотрим следующий кодирующий алфавит:
An = { а*, Ьі, Сі, du хт>і І і Є Z3, 3 < т < п}.
Всюду считается, что индекс і принадлежит группе Z3 = {0,1,2}. Например, при п — 2 получается алфавит И. А. Дынникова из [4]:
А2 = { а0, аи а2, bo, Ьь Ь2, с0, сь с2, d0, du d2 }.
Общее количество букв алфавита А„ равно g(n) = 3(n + 2). Геометрическая интерпретация букв алфавита А„ будет дана в пункте 2.1.1.
Определение 2.4 (универсальные полугруппы7 RSGn и NSGn). Пусть RSGn — полугруппа, заданная образующими из алфавита А„ и определяющими соотношениями (1)-(10). Предполагается, что целочисленные параметры m,p,q удовлетворяют неравенствам 3 < m < п, 2 < р < v^ и 2 < q < |.
d0dxd2 = 1;
bidi = dbbi = 1;
Oj = aj+i
Ж2р_і,і-і = ^_х (х2Р_і,г^і+і)&і_і, #2g,i-i = dj-i {bi+\X2q^di+i)bi_l;
X2p-\jidi = аДх2р_1,г^ )C,, Ь^ ^2р-1,іЬі = оДЬ? ^2р-1,гЬг)^;
diX2q,idl~ = ai(diX2q,id4~1)ci, Щ~~ x2q^i = ai(bf~1X2g,ibi)ci;
(dlci)w = lu(diCj), где w {сг+ь Мг+і^г, m,i+i};
uv = то, где и Є {aA, bi-ididi-фі, X2p-i,ibi, с^д.А},
V Є {йг+Ъ ^г+1> Сг+Ь bidi+\di, Хт^\);
(9) (ж2р-1,А)>р,г = >р-1,г(-Т2р-1,А)' ГДЄ Afe.i = didi+ldi-l(k ^ Х);
(10) (diX2q,ibi)Dqj = Dqii(diX2q,ibi).
Заменим соотношения (9)-(10) на (9') x^ib^dfdf^d^^ — хт,Ф%. Через NSGn обозначим полугруппу, порожденную образующими из А„ и соотношениями (1) — (8), (9'). Для множества J = {ji,... , j/J целых чисел ji > 3 введем полугруппу RSGj, порожденную буквами {a,i,bi,Ci,di,xm^ \ г Є Ъ^,т Є J} и соотношениями (1)-(10), содержащими только эти буквы. Пусть полугруппа NSGj задается теми же буквами из А„ и соотношениями (1)-(8), (9') при т J.
Все полугруппы RSGn,NSGn имеют единичный элемент — пустое слово, т.е. являются моноидами. Одно из соотношений (2) избыточно: его можно получить из равенства (1) и остальных соотношений (2). Тогда общее количество
7RSG = rigig spatial graphs, NSG = non-rigid spatial graphs.
соотношений (1)-(10) равно r(n) = 3(n2+7n—2). Полугруппа NSGn имеет то же количество образующих и определяющих соотношений, что и RSGn. Если множество J содержит \J\ элементов, то полугруппы RSGj и NSGj порождаются 3(4 + \J\) буквами и 3(16 + 11|J\ + \J\2) соотношениями. Например, полугруппа8 И. А. Дынникова DS = RSG2 = NSG2 задается 12 образующими из А2 и 48 соотношеними (1)-(10), не содержащими букв xm>i. Первоначально в работе [4] полугруппа DS порождалась 54 соотношениями, но впоследствии 6 соотношений оказались лишними. Полугруппы RSG$ = NSGj, и RSG{ij задаются 15 образующими и 84 соотношениями, а полугруппы RSG4 Щ NSG4 — 18 образующими и 126 соотношениями. Элемент полугруппы называется центральным, если он коммутирует со всеми остальными элементами этой полугруппы.
Теорема 2В (И. А. Дынников [4]). Каждое неориентированное зацепление LcR3 кодируется некоторым элементом wi полугруппы DS.
Теорема 2С (И. А. Дынников [4]). Два неориентированных зацепления K,L С R3 изотопны тогда и только тогда, когда в полугруппе DS имеем wк = wl-
Теорема 2D (И. А. Дынников [4]). Элемент w Є DS кодирует некоторое неориентированное зацепление в R3 тогда и только тогда, когда w — центральный элемент полугруппы DS.
Коротко главный результат И. А. Дынникова формулируется так: "центр полугруппы DS взаимно однозначно кодирует (с точностью до объемлющей изотопии) все неориентированные зацепления в R3". И. А. Дынников описал группу DG обратимых элементов в своей полугруппе DS.
Теорема 2Е (И. А. Дынников [4]). Группа DG имеет следующее задание: DG = {х,у\ [[х, у], х2ух~2} = [[ж, у], у2ху'2} = [[х, у], [ж-1, у'1] = 1), [х, у] = хух~ху
Коммутант [DG, DG] изоморфен группе кос В^ из бесконечного числа нитей.
Теоремы 2B-2D являются частными случаями (при п = 2) теоремы 2.1, которую также удобно разбить на три части.
Теорема 2.1а. Каждый заузленный n-граф G С К3 кодируется некоторым элементом wq полугруппы RSGn.
Теорема 2.16. Любые два заузленных n-графа G, Н С R3 жестко изотопны тогда и только тогда, когда в полугруппе RSGn имеем wq = иін-
Теорема 2.1в. Элемент w Є RSGn кодирует некоторый заузленный п-граф в R3 тогда и только тогда, когда w — центральный элемент полугруппы RSGn. Алгоритм, определяющий, является ли данный элемент w Є RSGn центральным, имеет линейную сложность по длине слова w.
Коротко теорему 2.1 можно сформулировать так: "центр полугруппы RSGn взаимно однозначно кодирует с точностью до жесткой объемлющей изотопии все заузленные n-графы в R3". Например, центр полугруппы RSG^ = NSG3 взаимно однозначно кодирует все заузленные трехвалентные графы. Полугруппа Stg с таким же свойством была построена в работе [10], она порождается
8 Всюду в диссертации изоморфизм полугрупп и групп обозначается через й.
24 образующими и 90 соотношениями. В примере 2.2 (пункт 2.1.2) демонстрируется связь между полугруппами Stg и RSG$ — NSG^- А центр полугруппы RSG4 взаимно однозначно кодирует (с точностью до жесткой изотопии) все заузленные графы с вершинами степени только 3 и 4. В параграфе 2.1 дается геометрическая интерпретация полугруппы RSGn. Там же описывается план доказательства теоремы 2.1. Самая существенная часть теоремы 2.1 (при п = 3) доказана в [10], общий случай — в [11].
Фактически, теорема 2.1 сводит топологическую задачу жесткой изотопической классификации заузленных графов к алгебраической проблеме равенства центральных элементов в конечно определенных полугруппах RSGn. В некоторых частных случаях эту проблему удается решить в явном виде. Например, в параграфе 2.6 настоящей диссертации получена классификация бесконечного семейства сингулярных узлов, имеющих простые трехстраничные вложения (предложения 2.4 и 2.5). Там же исследован подход к проблеме равенства слов с помощью теории представлений групп. Оказалось, что при гомоморфизме полугрупп RSGn в ассоциированные группы теряется большая часть информации о заузленных графах (предложение 2.8). Этот отрицательный результат подчеркивает сложность задачи полной классификации заузленных графов. Результаты параграфа 2.6 не относятся к основным, они только демонстрируют возможные подходы к эффективной классификации заузленных графов.
Теорема 2.2. Центр полугруппы NSGn взаимно однозначно кодирует с точностью до нежесткой объемлющей изотопии все заузленные n-графы в R3. Алгоритм, определяющий, является ли данный элемент v Є NSGn центральным, имеет линейную сложность по длине слова V.
Как и в случае жесткой изотопии при п = 2 полугруппа NSG2 совпадает с полугруппой И. А. Дынникова DS. Для п — 3 оба понятия изотопии на заузленных графах одинаковы, поэтому NSGj, = RSG3. Но при п > 3 эти две серии полугрупп расходятся: RSGn "Щ NSGn, см. пример 2.2 в пункте 2.1.2.
2.3. Алгебраические и геометрические следствия.
В этом пункте формулируются следствия теорем 2.1-2.2.
Определение 2.5 (антиавтоморфизмы р„,єп, зеркальный образ). Рассмотрим следующее преобразование9 слов в алфавите А„:
f Рп(аг) = сі, рп{Ьг) = du pn(ci) = аг, pn{di) = bi:
{ Рп\%2р-1,г) = Х2р-1,іЬіС{, Pn\x2q,i) = x2q,i-
Отображение pn по формуле pn(uv) = pn{v)pn(u) продолжается до инволютив-ных антиавтоморфизмов рп : RSGn —> RSGn и єп : NSGn —> NSGn. Аналогично определяются антиавтоморфизмы pj : RSGj —» RSGj и ej : NSGj —> NSGj. Зеркальный образ графа GcK3 — это граф G' С Е3, который получается из G отражением относительно некоторой двумерной плоскости в R3.
При помощи антиавтоморфизмов рп, еп вопрос об изотопности заузленного графа своему зеркальному образу также сводится к проблеме равенства слов.
9Как обычно, считается і Є Z3, 2 < р < ^^, 2 < q < ^-, число п фиксировано.
Следствие 2.1. а) Пусть заузленный n-граф С? С К3 кодируется некоторым центральным элементом wq Є RSGn (см. теорему 2.1а). Заузленный граф G жестко изотопен своему зеркальному образу тогда и только тогда, когда в полугруппе RSGn имеем Wq = Pti(wg)-
б) Пусть заузленный n-граф G С К3 кодируется некоторым центральным элементом vg Є NSGn (см. теорему 2.2). Заузленный граф G нежестко изотопен своему зеркальному образу тогда и только тогда, когда в полугруппе NSGn имеем vg = єп(ус)-
Следствие 2.2. а) При любых п > т > 2 естественное отображение RSGm —> RSGn является мономорфизмом полугрупп. Группа всех обратимых элементов полугруппы RSGn изоморфна группе И. А. Дынникова DG.
б) При любых п > т > 2 естественное отображение NSGm —> NSGn является мономорфизмом полугрупп. Группа всех обратимых элементов полугруппы NSGn изоморфна группе DG.
Метод трехстраничных вложений И. А. Дынникова можно применить также и к произвольным заузленным J-графам.
Следствие 2.3. а) Центр полугруппы RSGj (соответственно, NSGj) взаимно однозначно кодирует с точностью до жесткой (соответственно, нежесткой) объемлющей изотопии все заузленные J-графы в R3. Алгоритм, определяющий, является ли элемент w Є RSGj (соответственно, v Є NSGj) центральным, имеет линейную сложность по его длине.
б) Пусть заузленный J-граф G С I3 кодируется некоторым центральным
элементом wg Є RSGj (соответственно, vq Є NSGj). Заузленный граф G
жестко (соответственно, нежестко) изотопен своему зеркальному образу тогда
и только тогда, когда в полугруппе RSGj имеем wg = Pj{wg) (соответственно,
в полугруппе NSGj имеем vG = j{vg))-
в) Для любого подмножества К С J естественные отображения RSGk —>
RSGj и NSGk —> NSGj являются мономорфизмами полугрупп. Группы всех
обратимых элементов полугрупп RSGj и NSGj изоморфны группе DG.
Например, центр полугруппы RSG^ = SK из [3] взаимно однозначно кодирует все неориентированные сингулярные узлы в R3. А центр полугруппы NSG{4} взаимно однозначно кодирует (с точностью до нежесткой изотопии) все заузленные 4-валентные графы. Следующее следствие является обобщением (при / = 0) теоремы Брюнна [15], где впервые фигурируют вложения узлов в книжку со страницами.
Следствие 2.4. Любой заузленный J-граф Get3, рассматриваемый с точностью до нежесткой изотопии, можно спроектировать на плоскость М2 с единственной особой точкой.
В первой главе диссертации рассматриваются базисные вложения графов в книжку со страницами К х T„jm. А что можно сказать о топологических вложениях конечных графов в те же книжки? Оказывается, решение этой задачи вытекает из доказательства теоремы 2.1а. В следующем утверждении конечный граф G может иметь и висячие вершины.
Следствие 2.5. Любой конечный граф G топологически вкладывается в книжку R х Т3_о всего с тремя страницами (а значит, и в любую книжку Ех Тп^т при п + 2т > 3).
Все утверждения в диссертации имеют двойную нумерацию. Первое число (1 или 2) обозначает номер главы, а второе — номер соответствующего утверждения внутри главы. Главные результаты диссертации — это теоремы 1.1 и 2.1-2.2. К основным выводам также относятся следствия 1.1-1.3 и 2.1. Промежуточные результаты названы предложениями, леммами и утверждениями (по убыванию важности). Диссертация содержит 15 предложений, 18 лемм и 20 утверждений. Благодаря такому разбиению вывод каждого вспомогательного результата занимает не более полутора страниц. Кроме того, для удобства читателя текст снабжен 45 примерами и 25 рисунками. Список литературы содержит 43 наименования, общий объем текста 105 страниц.
Благодарности. Автор признателен своим научным руководителям Виктору Матвеевичу Бухштаберу и Аркадию Борисовичу Скопенкову за постановку задач и внимание к исследованиям. Автор благодарен Ивану Алексеевичу Дын-никову и Владимиру Валентиновичу Вершинину за многократные обсуждения результатов и ряд ценных замечаний. Диссертант благодарит РФФИ и фонд ИНТАС за частичную финансовую поддержку во время написания диссертации. Автор выражает свою признательность за гостеприимство университетам Монпелье, Ливерпуля, Дижона, Тулузы и Парижа, а также лично — Владимиру Вершинину, Хью Мортону, Луису Пари, Степану Оревкову и Пьеру Вожелю, работавшим вместе с диссертантом в рамках гранта ИНТАС YS 2001/2-30.
Необходимые условия базисной вложимости
Всюду в параграфах 1.2-1.5 целые числа п,т 0 (п + 2т 2) будут считаться фиксированными. В этом параграфе доказывается необходимость в теореме 1.1. А именно, ограничение на первое число Бетти b(G) проверяется в предложении 1.1 (пункт 1.2.2). Ограничения на дефект 6(G) следуют из частных случаев предложений 1.2, 1.3 и 1.4 (см. пункт 1.2.4). Для доказательства этих утверждений (пункты 1.2.5-1.2.6) вводится понятие схлопывания базисного вложения (пункт 1.2.3). Все рассуждения основаны на геометрическом критерии базисной вложимости из пункта 1.2.1. Пусть X, Y, Z — конечные графы. Через рх,ру обозначим естественные проекции рх : X Определение 1.7 (операция Е и молния). Для графа Z С X xY положим2 2Через \W\ обозначается количество элементов множества W. Будем говорить, что операция Е стирает или удаляет точки z Є Z—E(Z) либо горизонтальными сечениями X х pyz, либо вертикальными сечениями pxz х Y. Множество {ai,..., ап} G X xY называется молнией, если при каждом і имеем йі ф а-і+і, кроме того, рхйі = рхйі+і при нечетных і (или, соответственно, при четных г), и руйі = руаі+і при четных г (соответственно, при нечетных г). Пример 1.13 (молнии). Во вложенном графе Т4]о С 1x1с рисунка 1.76 из пункта 1.1.1 три точки (1,0),(0,0),(0,1) образуют молнию. Заметим, что все точки молнии не обязаны быть различными, только соседние не могут совпадать. Поэтому вершины единичного квадрата с рисунка 1.7в составляют бесконечную молнию. Множество точек {а;} из примера 1.4 представляет собой другой тип бесконечной молнии. Теорема IE (Штернфельд-Скопенков [38, лемма 2.23(ііі) на стр. 14], [36, критерий GC на стр. 33]). Вложение Z С X х Y не является базисным тогда и только тогда, когда выполняется одно из следующих эквивалентных условий: (El) Ek(Z) ф 0 при всех fceN; (Е2) для каждого к Є N граф Z содержит некоторую молнию из к точек. Теорему IE проще применять для распознавания базисного вложения в конкретных случаях, чем функциональное определение 1.1. Этот критерий будет использоваться и в доказательстве теоремы 1.1. Проиллюстрируем его действие на уже разобранных примерах 1.1-1.4. Пример 1.14 (операция Е).
Для графа X Сь X х У, вложенного на первый сомножитель (см. пример 1.1), уже первая операция Е стирает все его точки. Для графа Т о из примера 1.2 первое применение операции Е оставляет только его центр О. Поэтому в примерах 1.1 и 1.2 описанные вложения являются базисными по теореме IE. Вершины единичного квадрата с рисунка 1.7в не могут быть удалены никакой операцией Е. Из молнии {(} на рисунке 1.7г к-е применение операции Е стирает только первые к точек. Значит, по теореме IE вложения из последних двух примеров не являются базисными. 1.2.2. Ограничение на первое число Бетти графа. Для доказательства ограничения на первое число Бетти b(G) из теоремы 1.1 проверим следующую лемму. Лемма 1.1. Окружность S1 не вкладывается базисно в книжку R х ГП)о. Доказательство. Допустим от противного, что S1 Сь R х Тп о- Множества pxSx и PyS1 имеют конечное число граничных точек. Для каждой внутренней точки а Є Int PxS1 (соответственно, для b Є Int PyS1) сечение a x ГП)0 (соответственно, E x b) содержит минимум две точки данной окружности S1. Поэтому дополнение S1 — E{SX) — конечно, т.е. на первом шаге операция Е удаляет конечное множество точек (не более п + 2). На втором шаге операция Е может стереть только те точки, которые лежат на сечениях Ш х руа и рха х Тп о, где а Є S1 — (51)) т.е. опять конечное число точек. Далее ситуация не изменится, т.е. операция Е на каждом шаге может стереть лишь конечное множество то чек. Значит, при всех / Є N имеем El(Sl) ф 0, что по теореме IE противоречит базисности вложения S1 Сь Е х T„i0. Точку а графа G назовем неособой, если она не является вершиной графа G. Неособая точка а Є G называется разбивающей, если граф G — а имеет на одну связную компоненту больше, чем G. Благодаря лемме 1.1 в следующем предложении можно считать т 1. Предложение 1.1. Если граф G базисно вкладывается віх Тп т; то его первое число Бетти b(G) т. Доказательство. Допустим от противного, что G Сь Е х Тп т и b(G) т+ 1. Пусть G\ — объединение всех циклов (подграфов, гомеоморфных S1) графа G. Тогда b(Gi) = b(G) m + 1. Кроме того, выбрасывание любой неособой точки графа G\ уменьшает первое число Бетти b(G\) на 1. Допустим, что найдется такая неособая точка а Є G\, что а 0 ЖхО и3 а — С\П(Шхруа). В таком случае пусть G-1 — объединение циклов в графе G\ — а. Тогда 6(( = b{G\) — 1 т и G2 Сб lx Tn+2,m-i. Здесь книжка Rx T„+2,m-i получилась из исходной книжки IK х ТПгГП выбрасыванием прямой К х руа, т.е. цилиндр Rx S1 распался на две страницы Е х (51 - руа) ЙЕХ Г2і0. Продолжая этот процесс получим либо окружность, базисно вложенную в книжку Е х Tn+2mio, что противоречит лемме 1.1, либо на каком-то шаге по явится базисно вложенный граф Gk Сь Ex Tn+2k,m-k, Для всех неособых точек а которого пересечение Gk П (Е х руа) содержит минимум две точки. Поскольку Gk — это объединение всех циклов в графе Gk-i (где Go = G), граф Gk не имеет разбивающих точек. Тогда для любой неособой точки а Є Gk с условием рха Є Int pxGk пересечение Gk П (рха х Тп+2к,т-к) тоже содержит минимум две точки. Значит, на первом шаге операция Е может стереть лишь конечное чи сло точек графа Gk, а именно только вершины графа Gk и те точки, которые проектируются в граничные точки множеств pxGk и pyGk- Далее ситуация не изменится аналогично доказательству леммы 1.1, т.е. для любого І Є N допол нение Gk — El(Gk) конечно. Тогда при всех І є N получим El(Gk) ф 0, что по теореме IE противоречит базисности вложения Gk Сь Е х Тп+2к,т-к- П До конца параграфа 1.2 считается, что (с точностью до гомеоморфизма) все рассматриваемые графы не имеют вершин степени 2. Дугой считается множество, гомеоморфное отрезку [0,1]. Пусть X, Y, Z — конечные графы. Определение 1.8 (подходящие дуги и схлопывания).
Дугу I графа Z С XxY назовем горизонтальной (соответственно, вертикальной), если проекция 3Геометрически это означает, что вертикальное сечение К х руа пересекает граф G\ только в точке а. Ру1 С У (соответственно, рх1 С X) является точкой. Горизонтальные и вертикальные дуги будем называть подходящими. Пусть ZCXXYHICZ — подходящая дуга (например, горизонтальная). Охлопывание, порожденное дугой 7, — это отображение р/ = 7Г/ х idY : X х У — (Х/рх1) х У, где 7Г/ : X — Х/рх1 — естественная проекция. Аналогично определяется схлопывание, порожденное вертикальной дугой J: pj = idx х TTJ : X х Y - X х {Y/pyJ). Пример 1.15 (схлопывания). Возьмем дугу 7 = [(0,0), (1,0)] С Т4)0 СДх! в кресте из примера 1.2 (см. рисунок 1.76). Дуга I является горизонтальной, и схлопывание по ней дает триод T3jo = (Т4 о —7)и(0, 0), также базисно вложенный в R х R. Дуга J = [(0, 0), (0,1)] С T3io Сь Ш х Е — вертикальная, и схлопывание по ней приводит к дуге [(-1,0),(0,0)] U [(0,0), (0,—1)], по-прежнему базисно вложенной BRXR. Лемма 1.2 (о схлопываниях). Пусть X,Y,Z — конечные графы, Z Сь ХхУ, 7 С Z — подходящая дуга (для определенности — горизонтальная). а) Имеется базисное вложение pi(Z) Сь (X/pxI) х У. Ограничение pi\z-i является гомеоморфизмом. б) Если дуга I содержит не более одной вершины графа Z, то графы pi(Z) и Z гомеоморфны. Иначе графы pi(Z) и Z негомеоморфны. в) Если дуга I содержит больше одной вершины графа Z и не является ви сячим ребром, то 5(pi(Z)) S(Z). Наконец, если новый граф pi(Z) содержит висячее ребро, то в исходном графе Z будет точно такое же. Доказательство, а) Если новое вложение pi(Z) С (Х/рхІ) х У не является базисным, то для любого к Є N граф Pi{Z) содержит некоторую молнию {ai,... ,a,k} С pi(Z). В каждом прообразе pjl(at) С Z фиксируем произвольную точку ЬІ Є Z С X х У. В силу горизонтальности дуги / если рущ = руа \, то pybi = Pybi+i. Если рхаі = рхаі+х, но pxb{ ф pxbi+1, то bi,bi+i Є (рхІ) х У. Тогда пару {ЬІА+І} С Z можно дополнить до молнии {ЬІ, b t, b", Ь +і} С Z точками b\ = І П (pxbi xY),b" = І П (pxbi+i x У) є I С Z. Множество {6,} вместе с добавленными точками b {, b" образует молнию в графе Z, содержащую по крайней мере к точек. Так как число к Є N выбрано произвольно, по теореме IE получается противоречие с базисностью вложения Z Сь X х У. Если ограничение pi\z-i не является гомеоморфизмом, то оно склеивает какую-то пару точек a, b Є Z — 7, т.е. а, 6 Є (рх1) х У и руа = руЬ. Тогда найдутся точки с = 7 П (X х руа), d = I П (X х руЬ) Є 7 С Z. Четверка точек а, Ь, с, d образует замкнутую (а тогда и бесконечную) молнию в графе Z, что опять противоречит базисности вложения Z Сь X х У. б) Если дуга 7 содержит не более одной вершины графа Z, то схлопывание Pi стягивает часть какого-то ребра в графе Z. Поэтому полученный граф pj(Z) гомеоморфен исходному графу Z. Если же дуга 7 содержит больше одной вершины графа Z, то схлопывание pi склеит несколько вершин графа Z в одну4. 8 этом случае графы pi(Z) и Z будут негомеоморфны. 4Считается, что граф Z (с точностью до гомеоморфизма) не содержит вершин степени 2.
Построение базисного вложения
Проекции квадрата [О, I]2 на его горизонтальную и вертикальную стороны обозначаются через рх,Ру соответственно. Если a, b — различные точки некоторого связного дерева К, то под [а, Ь] понимается единственная дуга дерева К с концами в точках a, Ь. Ключевая идея следующей леммы — удобное расположение специальных дуг сердцевины, содержащих замечательные и хорошие точки. Такое расположение позволит продолжить вложение на универсальные листья и тонкие ветви в леммах 1.8 и 1.10. Лемма 1.7 (вложение сердцевины). Пусть I — сердцевина с корнем г, концом е и удовлетворительными точками V\,... ,vs Є I. Тогда существует совершенно базисное вложение19 где щ,... ,и„ Є (0,1), щ щ. Доказательство. Упорядочим все удовлетворительные точки данной сердцевины / от корня до конца: г = VQ,V\,. .. ,vs,e = fs+i- Выберем возрастающую последовательность чисел щ ... us из интервала (0,1). Для каждого г = 1,..., s в точку (щ, 0) на нижней стороне квадрата [0,1]2 посадим удовлетворительную точку i/j, корень г = VQ — в точку (0, 0), конец е — в точку (1,0). Осталось продолжить это вложение на любую дугу [г і, г і] С / между двумя соседними точками , +1 Є I- Каждую такую дугу вложим в квадрат [0,1]2 в виде шапочки из трех отрезков так, чтобы (см. рисунок 1.9): 1.4 Построение базисного вложения. (1.7а) проекция г-й шапочки рх : \щ, v i] —» [щ, щ+і] (а тогда и вся проекция рх : / — рж/) взаимно однозначна; (1.76) замечательные и хорошие точки из дуги [vi,vi+i] лежат на среднем отрезке г-й шапочки выше (г 4- 1)-й шапочки. На рисунке 1.9 роль единичного квадрата [О, I]2 играет плоско лежащий пря моугольник [vo, D2] х D. Сердцевина I имеет корень г, удовлетворительную точ ку v\ и конец е = v-i- Она выделена самыми жирными линиями. Построенное вложение / Срь [О, I]2 совершенно базисно. Действительно, для любого є О по свойству (1.7а) уже первая операция РЕЕ стирает всю сердцевину вертикаль ными отрезками х х [0,1], где х Є [0,1], т.е. PEe(I) = 0. Условие (1.76) будет использоваться далее.
Определение 1.20 (тень множества). Пусть U, W С R х Т о — произвольные множества. Тогда пересечение множества U с множеством (pxW х Tk,o) U (R х pyW) называется тенью множества W на множестве U. Пример 1.23 (тени). Пусть W С [О, I]2 — средний отрезок одной из шапочек в лемме 1.7, см. рисунок 1.9. Тогда множество (pxW х Т о) U(Rx PyW) — это "тень", которую отбрасывает отрезок W, если смотреть в горизонтальном и вертикальном направлениях. Из условия (1.76) следует, что средние отрезки всех шапочек на рисунке 1.9 не "затеняют" друг друга, т.е. тень любого из них не пересекается с остальными отрезками. Это геометрическое свойство позволит продолжить базисное вложение на тонкие ветви в леммах 1.8-1.9. Ключевая идея следующей леммы — сохраняющая свойство базисности вставка маленьких элементов, вложения которых уже построены. Лемма 1.8 (вложение тонкой ветви без точки разрыва). Пусть Д — тонкая ветвь (без точки разрыва) с корнем г и удовлетворительными точками v\,... ,vs Є Д. Тогда существует совершенно базисное вложение20 Доказательство. Пусть / — сердцевина тонкой ветви Д. Возьмем совершенно базисное вложение / Срь [0,1]2 из леммы 1.7. Продолжим это вложение на универсальный лист 4(Р)(М) и висячее ребро Н, приклеенные в замечательной точке р Є /. Из леммы 1.6 возьмем совершенно базисное вложение листа 4(P)(R) в квадрат S. Этот квадрат S можно пропорционально уменьшить (что не повлияет на базисность вложения) и поместить его в данный квадрат [0,1]2, приклеив нижнюю левую вершину квадрата 5 к замечательной точке р Є I. На рисунке 1.9 верхняя правая четверть квадрата S изображена в виде черного квадратика S . Вложим висячее ребро Н в качестве маленького горизонтального отрезка, лежащего на нижней стороне квадрата 5". Степень малости вложенного квадрата S и ребра Н определяется следующими условиями: (1.8а) тень квадрата S на сердцевине / не содержит никаких отмеченных точек (отличных от р) из ветви Д; (1.86) вертикальные полосы рхН х [0,1] и pxS х [0,1] не пересекаются. Выберем такое є 0, чтобы тени окрестности D и квадрата S на сердцеви не / не пересекались. Тогда имеем PE (IUUk(R)UH) С 4(К). Действительно, в силу условий (1.7а) и (1.8а) сначала операция РЕ вертикальными отрезками стирает всю сердцевину / (кроме тени квадрата S на ней). На втором шаге по свойству (1.76) операция РЕе удаляет эту тень горизонтальными отрезками и остается только лист 4(P)(R) с ребром Н. Дуга, соединяющая точку р с ква дратом S , исчезает на третьем шаге, а на четвертом — ребро Н (благодаря условию (1.86)). Далее операция РЕе за конечное число шагов стирает оста ток базисно вложенного листа {/ (М) в квадратике 5". Аналогично построенное вложение продолжается на листья и висячие ребра, приклеенные к остальным замечательным точкам из данной ветви Д. Образно говоря, операция РЕЕ съе дает сначала сердцевину, а затем — приклеенные листья. 1.4 Построение базисного вложения. Теперь разберем пример вложения специальной тонкой ветви.
При этом фактически будет построено базисное вложение универсального графа 4(51) для цилиндра (см. определение 1.11) в цилиндр R х S1. Пример 1.24 (базисное вложение универсального графа 4(51)). Возьмем тонкую ветвь из примера 1.196 пункта 1.3.2. Эта ветвь Д имеет корень г с оснащением 0, точку разрыва е и ровно к замечательных точек. Тогда приклейка к корню г одной дуги с точкой разрыва даст пример 1.206 толстой ветви из пункта 1.3.3. Наконец, заклейка двух точек разрыва дугой разрыва приведет к универсальному графу 4(51) для цилиндра (см. пример 1.226 из пункта 1.3.5). Можно сразу отождествить корень г с точкой разрыва е и получить тот же граф 4(51) = Д/{г, е}. Забудем, что точка е была точкой разрыва и будем считать ее концом ветви Д. Из леммы 1.8 возьмем совершенно базисное вложение Д Срь [0,1]2, при котором конец е попадает в правый нижний угол квадрата, а корень г — в левый нижний угол. Склеим вертикальные стороны единичного квадрата. При этом он превратится в цилиндр [0,1] х S1, а ветвь Д — в граф 4(51). Базисность вложения сохранится при такой операции. Итак, построено базисное вложение универсального графа 4(51) Cf, К х 51. В общем случае с точками разрыва придется работать аккуратнее. Букет Тп+2т,о можно считать вложенным в плоскость R2, ортогональную оси R х О. В леммах 1.6-1.8 вложения строились в квадрат [0,1]2, отождествленный с прямоугольником [0, l]xD С MxTn+2m,o- Страница RxD окажется плацдармом, с которого растет базисное вложение универсального графа. Определение 1.21 (граничная прямая). Если с Є T„+2m,o — висячая вершина букета, то прямую Ехс назовем граничной. Ключевая идея следующей леммы — вынос точек разрыва на граничные прямые, где их будет удобно соединить дугами разрыва, см. окончание доказательства предложения 1.5 в пункте 1.4.7. Лемма 1.9 (вложение тонкой ветви с точкой разрыва). Пусть її — тонкая ветвь с точкой разрыва в\. Тогда существует такое совершенно базисное вложение Д Срь Ш х Tn+2m,0; что корень г є Д и все удовлетворительные точки ветви Д лежат на оси Жх О, а тючка разрыва е\ — на некоторой граничной прямой книжки Кх Tn+2m,o- Кроме того, можно считать, что вся ветвь Д (кроме окрестности точки е\) лежит в полосе21 [0,+оо) х D. Доказательство. Сначала разберем простейший случай короткой тонкой ветви Д [0,1] из примера 1.19а (пункт 1.3.2). Линейно вложим дугу Д в полосу [0, +оо) х D, отождествляя корень г Є Д с точкой ОхО бМхОи помещая точку разрыва в\ Є Д в некоторую точку и х с (и 0) граничной прямой Ехс. Тогда проекция рх : Д — [0, и] взаимно однозначна, т.е. дуга Д стирается вертикальными сечениями уже первой операцией РЕе. 21Висячее ребро D букета Г„+2т,о было фиксировано в начале пункта 1.4.1. Пусть / — сердцевина данной тонкой ветви Д. По определению 1.13 рядом с точкой разрыва е\ Є Д на сердцевине / лежит некоторая удовлетворительная точка V2 с оснащением 0. В отличие от разобранного выше случая короткой тонкой ветви теперь можно предполагать г ф v2. Временно перестанем считать точку е\ точкой разрыва. Тогда ветвь Д будет тонкой ветвью без точки разрыва. При этом к последней удовлетворительной точке V2 приклеено висячее ребро [г 2, ег] (играющее роль универсального листа Uo(M)). Из леммы 1.8 возьмем вложение (Д,г 2) CPb ([0,1]2, (u, 0)) с параметром є 0, см. рисунок 1.9. Ограничим это вложение на множество Д — (г е . Осталось перестроить вложение дуги [v2, Єї] так, чтобы ее конец Єї оказался на некоторой граничной прямой Ехси свойство базисности сохранилось. Дуга [и2, е\\ и будет той окрестностью точки разрыва еь которая не поместится в полосу [0, +оо) х D. Пусть b — точка граничной прямой Мхе книжки К х Т„+2т,0) которая про ектируется в нижний правый угол прямоугольника [0,1] х D, т.е. рхЬ = 1x0. Вложим дугу [г 2, е{\ в виде отрезка, соединяющего точки Ь = ei и uxO = v2 (см. рисунок 1.9). По построению точка рхЬ лежит на оси Ж х О правее множества Px(h — ( 2, Єї]). Поэтому на первом шаге операция РЕе стирает отрезок [гі2,еі] вертикальными сечениями х х Тп+2т,о (где х Є [и, 1]), т.е. РЕє(Іі) С 1\ — (V2, Єї]. Значит, вложение всей ветви Д Срь К х Тп+2т,о будет совершенно базисным. Кратко говоря, дуга с точкой разрыва, вынесенная в дополнительную страни цу, исчезает первой, а потом — остальная ветвь.
Достраивание тонкой и толстой ветвей
В этом пункте, начиная с сердцевины I С К, будут строиться тонкая и толстая ветвь, содержащие сердцевину /. Посмотрим на замечательные точки выделенной сердцевины I. По построению (первый случай из пункта 1.5.4) к каждой такой точке р Є I примыкает некоторый лист Lp и (возможно) висячее ребро. По утверждению 1.3 лист Lp содержится в некотором универсальном листе C4(j,)(R). В каждой замечательной точке р Є I заменим лист Lp на С4(Р)(К) и приклеим висячее ребро (если оно отсутствовало в дереве К). Если конец е сердцевины I совпадает с удовлетворительной точкой, к которой примыкает некоторый лист Le С 4(е)(К), то заменим лист Le на C/fc(e)(K). Корень г сердцевины I будем считать корнем тонкой ветви /і. Полученное дерево Д D I является тонкой ветвью в смысле определения 1.13 (пункт 1.3.2). Заметим, что тонкая ветвь Д уже не обязательно содержится в исходном дереве К, т.к. некоторые листья L С К были заменены на универсальные листья 4(R) Э L. С помощью такого рода замен в пункте 1.5.6 будет получено универсальное дерево К , содержащее данное дерево К. Посмотрим на хорошие точки сердцевины /. По построению (второй случай из пункта 1.5.4) к каждой такой точке q Є І в дереве К примыкает ровно одна ветвь / , содержащая корень г, и (возможно) висячее ребро. Пойдем от вершины q по ребру из ветви / С К. Аналогично предыдущим рассуждениям выделим из Г сердцевину и достроим / до тонкой ветвь І2 D Г. Приклеим к тонкой ветви І\ в точке q новую тонкую ветвь її и висячее ребро (если его не было в дереве К). Далее возьмем следующую хорошую точку из ветви Д (или /2) и достроим примыкающую к ней тонкую ветвь и т.д. до исчерпания всех хороших точек дерева К. В результате получится какое-то поддерево J С К. Полученное дерево J является толстой ветвью в смысле определения 1.14 (пункт 1.3.3). Корень г тонкой ветви Д будет считаться корнем толстой ветви J. Пример 1.26 (тонкая и толстая ветвь). На рисунке 1.9 выделенная в примере 1.25 сердцевина / содержит единственную замечательную точку р. Значит, для образования тонкой ветви надо добавить к сердцевине / универсальный лист (содержащий квадратик S на рисунке 1.9) и висячее ребро Н. Получен 33Считается, что к вершине г 2 примыкает минимум 4 ветви, на рисунке 1.9 показана только часть универсального графа. ная ветвь 1\ имеет две хороших точки q,q . От первой вытягивается короткая тонкая ветвь до точки разрыва Є2, а от второй — тонкая ветвь с удовлетворительной точкой г з и листом на конце. Сначала закончим проверку частного случая предложения 1.6. Корень, отмеченные точки и оснащения были введены в пункте 1.5.3.
По определению корня г Є К к нему примыкает /(г) + 1 ветвей и листьев, не пересекающих первой достроенной толстой ветви J (см. пункт 1.5.5). Перебирая эти ветви, заменяем их на достроенные толстые ветви. В полученном дереве J\ точно также поступаем с каждой удовлетворительной точкой v (перебираем f(v) отходящих от v ребер). Затем повторяем этот процесс для всех удовлетворительных точек из достроенных ветвей и т.д. до исчерпания всех удовлетворительных точек дерева К. Поскольку новые висячие ребра могли приклеиваться только к замечательным и хорошим точкам дерева К, дефект построенного дерева К D К остался прежним 5V(K ) = 5у(К) = п + 2т — 1. К точкам разрыва дерева К ничего не приклеивалось, поэтому свойство универсальности для дерева К следует прямо из условий частного случая предложения 1.6. Итак, данное дерево К достроено до универсального дерева К в смысле определения 1.15 из пункта 1.3.4. Доказательство частного случая предложения 1.6 закончено. Теперь достаточность в теореме 1.1 следует из предложений 1.5 и 1.6. Необходимость была доказана в параграфе 1.2 (см. пункт 1.2.4). Доказательство следствия 1.1. Алгоритм распознавания базисной вложи-мости заключается в вычислении первого числа Бетти b(G) и дефекта 5(G). Занумеруем все вершины графа G числами 1,...,М. Тогда комбинаторная структура графа G задается матрицей размера М х М, где на пересечении г-й строки и j-ro столбца стоит количество ребер, соединяющих вершины i,j. При вычислении дефекта 5(G) для каждой вершины v Є G 1) находим количество примыкающих к вершине v ребер, т.е. степень degw; 2) если degt 5, то вершина v является сложной, вычисляем ее вклад в дефект 5(G); 3) если degt; = 4, то обходим четыре вершины, соседние с v; если все они — не висячие, то вершина v является сложной и ее вклад в дефект равен 2. Для каждой вершины v Є G первый этап требует О(М) операций, а второй и третий — только 0(1), т.е. для всех вершин графа G алгоритм использует 0(М2) операций. На вычисление количества #G связных компонент графа G тратится 0(М2) операций — перебор всех вершин вместе с их соседями. Первое число Бетти считается так: #G — М+ YLi=i deg vi — эт0 еЩе 0(М2) операций. Значит, описанный алгоритм имеет сложность 0(М2). После нахождения b(G) и 5(G) вывод о базисной вложимости графа G делается сразу из теоремы 1.1 Доказательство следствия 1.2. Сначала для произвольных конечных графов X, У построим конечный граф, который нельзя вложить базисно в произведение X х У. Пусть u,v — вершины максимальной степени в графах X, У соответственно, deg и = р 2, deg г; = q 2. Докажем, что граф T2pq+1)o не вкладывается базисно в X х У. Если имеется базисное вложение Т2Рд+і,о С& X х Y, то для достаточно маленькой открытой окрестности U центра О Є T2pq+ito в произведении X х Y возможны только следующие случаи: 1) окрестность U гомеоморфна области на плоскости; 2) окрестность U гомеоморфна книжке R х Тп 0 (где п max{p,q}); 3) окрестность U гомеоморфна произведению34 ТПіо х Т 0 (п р и k q). Поскольку degO = 2pq + 1 5, в первом случае получается противоречие с базисной вложимостью пентода T5i0 С Т2рд+і,о Л[/ в плоскость, см. пример 1.17в из пункта 1.2.5. Во втором случае в силу deg О 2pq+l 3max{p, q}+l 3n+l найдется крест T4i0 С T2Pq+xto П U, базисно вложенный в одну из п страниц книжки К х ТПі0 (причем центр
Построение трехстраничного вложения
О попадает на ось Е х О книжки). Последний вывод противоречит примеру 1.176. В третьем случае по неравенству deg О = 2pq + 1 Ink + 1 возникнет триод Г3,о С Т2р9+1]0 П U базисно вложенный в один из пк квадрантов35 произведения Tnfl х Т о (причем центр О попадает в вершину квадранта). Такое базисное вложение невозможно по примеру 1.17а. Итак, не существует базисного вложения T2Pg+i,o Сь X х У. Теперь проверим вторую часть следствия 1.2. Пусть G — данный конеч ный граф с первым числом Бетти b(G) и дефектом 5(G). Положим т = b(G). Если все сложные вершины графа G являются разветвленными, то возьмем п = max{0,5(G) - 2b(G) + 1}, иначе п = max{0,5(G) - 26(G)}. Тогда граф G и пара п,т удовлетворяют всем условиям теоремы 1.1. Значит, данный граф G базисно вкладывается в книжку К. х Тп т. Кроме того, число m уменьшить нельзя, поскольку должно быть b(G) га. А при фиксированном m число п также минимально возможное. Для 1 к Ц пару (п, га) можно заменить на пару (п — 2к, га + к). При этом две страницы вида Е х Г2]о склеиваются в один цилиндр Е х Тод « R х 51. П Пример 1.27 (базисные вложения графов Tfc); и Т к1). В примере 1.7 (см. пункт 1.1.2) были вычислены первые числа Бетти и дефекты графов T i и Т к1. Согласно следствию 1.2, чтобы базисно вложить графы Tk+iti и Т к1 (при к + 21 4) в книжку Е х ТП]ГП достаточно взять га = I и п = тах{0, к — 1}. Граф Т0і2 базисно вкладывается в книжку Ех То)2, графы Т2і\,Т[ 1 — в цилиндр Е х S1, а графы Г4)о, Тд 0 — в плоскость Е х Е. 34В случаях 2) и 3) ребра книжек ГПіо и Tj. считаются лучами [0,+оо). 35Квадрант — это прямоугольник вида I х J, где I,J — висячие ребра букетов Tnio,T)t о соответственно. Вершина квадранта — это точка 0\ хОг, где Оі,Ог — центры букетов Tn Tj o соответственно. Пример 1.28 (базисные вложения графов Кр и Kpq). В примере 1.8 (пункт 1.1.2) были вычислены первые числа Бетти и дефекты графов Кр и КРЛ. Согласно следствию 1.2, чтобы базисно вложить граф Кр (при р 5) в книжку Их Tn m достаточно взять т = р у и п = 0. Аналогично для графа Kp q (при р 4 или 5 4) достаточно взять т = (р — l)(q — 1) и п = 0. Графы i 4 и /С3,з базисно вкладываются в книжку Ш х Т0 3, а граф А з — в книжку 1х То,2. Графы Хз, - 2,2 (окружность) базисно вкладываются в цилиндр Ex S1. 1.6.2. Доказательство следствия 1.3. Перед доказательством следствия 1.3 в явном виде опишем запрещенные графы для базисных вложений в книжку R х Тп т при фиксированных п, т. Определение 1.24 (запрещенные графы). Рассмотрим все конечные графы G, удовлетворяющие неравенству (1) и одному из условий (2), (3), (4): (1) дефект 5(G) 2п + 4т; (2) первое число Бетти b(G) — т + 1; (3) первое число Бетти b(G) т и дефект 6(G) п + 2т; (4) первое число Бетти b(G) т, дефект 6(G) = п + 2т и все сложные вершины графа G являются разветвленными. Из всех этих графов выберем минимальные по вложению и назовем полученные графы запрещенными (для базисных вложений віх Тп т). Введенные выше графы не удовлетворяют условиям теоремы 1.1, поэтому они входят в запрещенное семейство из определения 1.4 (см. пункт 1.3 введения). Ниже в предложении 1.7 будет доказано, что эти графы исчерпывают все запрещенное семейство в смысле определения 1.4. Пример 1.29 (запрещенные графы). Перечислим простейшие запрещенные графы из определения 1.24. Во-первых, это графы Тп+2т+з,о, Т 2т+20 и Г0іт+і. Далее разберем стандартные частные случаи. а) Для плоскости RxR(n = 2,m = 0) запрещенными графами из определе ния 1.25 являются графы S1, Т 40, Т5,о и Т А0 UT4 0 (см. рисунок 1.3 в пункте 1.3 введения). Действительно, минимальным (по вложению) графом с условиями b(G) = 1 и 5(G) 4 будет окружность S1. Минимальное дерево с дефектом 5(G) = 2 и разветвленной сложной вершиной совпадает с Т 0. Минимальные графы G с b(G) = 0 и дефектом 3 5(G) 4 исчерпываются Г5!о, T[Q U T[Q и T[fiUT[fi. Т.к. граф T AQ уже учтен, графы T 4fiUT iQ и T QUT O можно не считать запрещенным. Полученный результат совпадает с критерием А. Б. Скопенко ва [36, теорема 1]: графы S1, Т А0 и Т5 о образуют запрещенное семейство для базисных вложений в плоскость Кхів смысле определения 1.4. б) Для пар (п,т) = (0,1), (3, 0), (1,1) графы с рисунков 1.1, 1.3 и 1.5 соответ ственно являются запрещенными в смысле определения 1.24. Неравенство (1) из определения 1.24 нельзя усилить, т.к. граф T5ioUT5]o с рисунка 1.3 должен быть запрещен для базисных вложений віх Тз,о иіх Тхд.
