Минимально-линейные вложения графов тема диссертации и автореферата по ВАК РФ 01.01.04, кандидат физико-математических наук Облакова, Татьяна Александровна

• Облакова, Татьяна Александровна
• кандидат физико-математических наук
• 2013

Оглавление диссертации кандидат физико-математических наук Облакова, Татьяна Александровна

Содержание

Введение

1 Минимизация количества точек образа графа на прямой

1.1 Основные определения

1.2 Зацепленные окружности

1.3 «Шапочка» и графы Петерсена

1.4 Доказательства вспомогательных лемм и утверждений

1.5 2-вложимость

1.6 Несколько примеров

1.7 Конструкция с «кепочкой»

1.7.1 Конструирование почти выпуклой пленки

1.7.2 Конструирование «кепочки»

1.7.3 Трехузловые графы

1.8 О конкретных примерах 4-вложений графов

2 Минимизация числа точек графа, принадлежащих гиперплоскости

2.1 Необходимые определения и свойства

2.2 Верхняя оценка числа гиперпланарности для случая деревьев

2.3 Ассимптотические свойства оценок

3 Случай четырехмерного пространства

3.1 Постановка задачи

3.2 Графы с наименьшим числом 2-планарности

3.3 Конструирование поверхности с малым числом 2-планарности

3.4 Вложение планарных графов

3.5 Минимальность пары триодов

Введение диссертации (часть автореферата) на тему «Минимально-линейные вложения графов»

Введение.

Темой данной работы являются минимально-линейные вложения графов. Рассматриваются такие вложения графов в евклидово пространство, при которых наименьшее число точек образа принадлежит линейному подпространству, то есть, в общем случае, задача состоит в поиске таких вложений графов в п-мерное евклидово пространство, при которых максимальное число точек, принадлежащих одной к-мерной плоскости, минимально. Эта обширная тема рассматривается для трех случаев: случай пересечения образа графа прямой в трехмерном пространстве (в пространствах больших размерностей задача тривиальна), пересечение образа графа двумерной плоскостью при вложениях в четырехмерное пространство и случай пересечения образа графа гиперплоскостью.

Вопросы вложения графов являются важной частью теории графов. Известно, что любой граф можно вложить в М3. Часто бывает важно среди всех вложений графа в евклидово пространство выделить множество некоторых специальных вложений. В задаче суперпозиции возникают базисные вложения [1]. В задачах интерполяции и аппроксимации возникают /с-регулярные вложения [2]. Вложения, рассматриваемые в первом разделе диссертации — вложения графов, при которых минимальное число точек образа принадлежит прямой — являются обобщением /¿-регулярных вложений. Богатый [3] доказал, что всякое отображение /: X —> К3 одномерного компакта в М3 сколь угодно малым изменением может быть превращено в такое вложение /е: X —>• К3, что на всякой прямой в М3 будет лежать не более четырёх точек образа /£(Х) компакта X. Укажем, что существование таких «экономичных вложений» доказал также Гудселл [5]. Оказывается, что число 4 не может быть уменьшено не только на уровне теоремы плотности «экономичных» отображений, но и на уровне теоремы существования. Именно, Живалевич доказал, что для всякого вложения в К3 существует прямая, пересекающая граф не менее чем по четырем точкам [6]. Автором доказано наличие такой прямой для меньших графов (граф К4.4 без ребра является подграфом -К'б.б), таким образом усилен результат Живалевича.

Вторая часть посвящена числу гиперпланарности графа — минимальному по всем вложениям графа в Евклидово пространство заданной размерности числу точек образа графа, принадлежащих одной гиперплоскости. Получена верхняя оценка числа гиперпланарности для деревьев, линейно зависящая от размерности пространства и комбинаторных характеристик графа. Для пространств больших размерностей эта оценка совпадает с нижней оценкой, полученной К. Облаковым. Кроме результатов К. Облакова, практически единственным результатом, касающимся этого семейства вложений, является теорема Мэрхьюбера о том, что любое компактное множество в п-мерном пространстве, содержащее не более п точек на любой гиперплоскости, является гомеоморфным образом замкнутой части окружности [18].

В третьей части рассматриваются вложения графов в четырехмерное Евклидово пространство, при которых минимальное число точек принадлежит двумерной плоскости. Этот вопрос представляет собой обширную область для изучения. Из результата Богатого из [3] следует, что любой граф можно вложить в четырехмерное пространство таким образом, что на любой двумерной плоскости содержится не более шести точек. Для выведения оценок числа точек образа графа, принадлежащих двумерной плоскости при вложениях в четырехмерное пространство также может быть использована теорема Скопенкова (см. [17], теорема 1.4.1). Автором доказано, что любой планарный граф может быть вложен в четырехмерное пространство таким образом, что любая двумерная плоскость содержит не более четырех точек образа. Также получены вложения окружности и графа т—

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

1 Минимизация количества точек образа графа на прямой.

1.1 Основные определения

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

Определение 1. Граф называется п-вложимым, если существует вложение в М3 такое, что на любой прямой находится не более п точек графа.

Очевидно, что если граф п-вложим, то он /с-вложим для любого к > п. Будем называть п-прямой прямую, содержащую п точек образа графа.

В данной работе мы рассматриваем вопрос п-вложимо-сти графов для различных п.

4-вложимость всех графов следует из теорем, доказанных в [4], [5].

Случаю 3-вложимости посвящены теоремы 2 и 5. Харак-теризация всех 2-вложимых графов дается в теореме 10.

1.2 Зацепленные окружности.

Сформулируем необходимое условие 3-вложимости графа.

Теорема 2. Для любого вложения двух окружностей в К3 с ненулевым числом зацепления имеется 4-прямая.

Доказательство теоремы 2. Пусть это вложение : 5'1и и 51 —»• М3. Обозначим через X, У образы окружностей в пространстве. Через Т обозначим тор, являющийся прямым произведением окружностей X и У. Обозначим через А множество таких точек (х,у) С Т, что на луче (х, у) за точкой у найдётся еще хотя бы одна точка X. Множество пар (х, у) на торе таких, что на луче (у, х) за точкой х найдётся точка У обозначим через В. Если мы докажем, что А и В пересекаются, это будет означать наличие 4-прямой, причём эти четыре точки «зацеплены», то есть будут чередоваться точки окружностей X и У. Однократные обходы X и У являются образующими фундаментальной группы тора Т.

Воспользуемся следующими леммами, доказательства которых приведены после доказательства теоремы:

Лемма 3. Носитель замкнутого пути на торе, нетривиально обходящий вдоль У, содержит точку А, и носитель замкнутого пути, нетривиально обходящий вдоль X, содержит точку В.

Лемма 4. Множества А «В замкнуты.

Теперь докажем теорему от противного. Предположим, что А и В не пересекаются. Так как они замкнуты, расстояние между ними ненулевое и равно некоторому числу <5. Выберем на торе конечное число параллелей и меридианов таким образом, чтобы расстояние от каждой точки тора до ближайшей параллели и ближайшего меридиана не превышало <5/12. Дополнение объединения этих параллелей и меридианов на торе представляет собой несвязное объединение открытых множеств — будем называть их клетками. Клетки, замыкания которых пересекаются, будем называть соседними. Так как диаметр каждой клетки меньше 6, ни одна клетка не может содержать как точки множества А, так и точки множества В. Более того, в силу выбора расстояния между параллелями и меридианами не может быть и двух соседних клеток таких, что одна из них содержит точку множества А, а другая — точку множества В.

Обозначим за А замыкание объединения всех клеток, содержащих точки множества А, аналогично введем множество В. Из вышесказанного следует, что множества А и В не пересекаются. Так как А £ А, и В € В, носитель замкнутого пути на торе, нетривиально обходящий вдоль V, содержит точку А, и носитель замкнутого пути, нетривиально обходящий вдоль X, содержит точку В. Введем еще одно обозначение: О = Т \ (А У В).

Для заданного разбиения тора на конечное число клеток существует конечное число разбиений этих клеток на множества А, В и Назовем допустимым такое разбиение, для которого выполняются следующие свойства:

1) нет соседних клеток, таких что одна из них принадлежит А, а другая В.

2) Носитель любого замкнутого пути на торе, нетривиально обходящего вдоль Y, содержит точку А, а нетривиальный обходящий вдоль X, содержит точку В.

Из сделанного выше предположения следует, что как минимум одно допустимое разбиение существует. Введем на множестве допустимых разбиений следующую функцию: Ф = L(A) + L(B) + L(Q), где функция L(C) — число компонент линейной связности множества С. Функция определена на непустом конечном множестве, а значит, достигает минимума. Будем в дальнейшем рассматривать разбиение £ — одно из тех разбиений, на которых функция Ф достигает минимум.

_ Пусть е — минимальная длина стороны клетки. Пусть А — объединение множества А и всех точек тора, находящихся на расстоянии < е/4 от множества А. Граница дА этого множества представляет собой несвязное объединение гладких Жордановых кривых, лежащих в множестве Q. Пусть 7 — одна из них. Так как разбиение £ допустимо, кривая 7 не может содержать нетривиального обхода вдоль X или Y. Пусть С — та из компонент связности множества Т \ 7, которая гомеоморфна двумерному диску. Рассмотрим два случая:

1) множество С содержит компоненту линейной связности А или В. В таком случае построим разбиение £1, отличающееся от £ тем, что клетки, входящие в эту компоненту, будут отнесены к множеству Q.

2) множество С входит в il Построим разбиение £1, отличающееся от £ тем, что все клетки, имеющие непустое пересечение с С, будут отнесены к множеству А

В обоих случаях легко проверить, что разбиение £1 допустимо, и что Ф(£г) < Ф(0- Полученное противоречие с минимальностью £ доказывает теорему 2 □

1.3 «Шапочка» и графы Петерсена.

Теорема 2 позволяет во многих случаях доказывать отсутствие 3-вложения. В работах [7]. [8], [10], [11] описаны все

графы, всякое вложение которых в К3 имеет пару окружностей с ненулевым числом зацепления. Именно, дан полный список минимальных графов, влекущих наличие окружностей с ненулевым числом зацепления. Такой полный список графов образуют графы семейства Петерсена (см. рис. 1). Так как теорема 2 даёт необходимое условие 3-вложимости, то графы Петерсена не являются 3-вложимыми, но вопрос о минимальности этих графов (с точки зрения существования 3-вложимости) и полноты этого списка остаётся открытым. Следующая теорема показывает, что все эти графы минимальны.

Теорема 5. Все графы семейства Петерсена являются минимальными Ъ-невложимыми графами.

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

Определение 6. Конструкция с «шапочкой» — это объединение единичной сферы и сегмента сферы большего радиуса, граничная окруэюиостъ которого лежит на единичной сфере.

Граничную окружность сегмента будем называть границей «шапочки». Она разбивает единичную сферу на две части. Объединение той из частей, которая выпукла в ту же сторону, что и сегмент, с самим сегментом, будем называть, собственно, «шапочкой». Сегмент сферы большого радиуса будем называть нижним слоем «шапочки», сегмент единичной сферы — верхним слоем, а часть сферы, не входящую в «шапочку» — внешностью «шапочки». Сформулируем утверждение, доказательство которого дадим позже:

Утверждение 7. Вложение любой фигуры в конструкцию с «шапочкой», образ которой, пересеченный с самой «шапочкой» является подмножеством одной из фигур, изображенных на рис. 2, является 3-вложением.

Изображены проекции конструкций на плоскость а. содержащую границу «шапочки». Пунктирные линии принадлежат нижнему слою «шапочки», а сплошные — верхнему.

Рис. 1. Семейство графов Петерсена: граф К§ и графы образованные из него операциями ДY и YД.

а) б) в) г) д) е)

Рис. 2. 3-вложимые конфигурации на „шапочке"

Изображенные в виде отрезков линии на «шапочке» являются дугами больших окружностей соответствующих сфер. Доказательство теоремы 5. 3-невложимость графов Пе-терсена является очевидным следствием теоремы 2, так как, согласно теореме Робертсона-Сеймура-Томаса, все они имеют пару зацепленных окружностей при любом вложении в М3. Для доказательства минимальности этих графов вложим каждый из графов Петерсена без одного ребра в одну из 3 вложимых конструкций на «шапочке».

Заметим, что у К§ все ребра эквивалентны друг другу, и потому не важно, которое из них мы удалим. Для 3-вложения К§ без ребра воспользуемся конструкцией д) на «шапочке». Вершины 1 и 2 поместим, соответственно, на верхний и нижний слои «шапочки». Ребро 5-6 отсутствует (см. рис. 4 а)).

Аналогичным образом на рис. 4 изображены 3-вложения графов Петерсена без всех возможных ребер с помощью 3-вложимых конфигураций на «шапочке». На рисунках окружность всегда изображает только границу «шапочки», пунктирными линиями изображено то, что лежит на нижнем слое «шапочки», сплошные линии внутри круга изображают содержимое верхнего слоя, сплошные линии вне круга изображают содержимое внешности «шапочки» . Минимальность графов Петерсена доказана. □

1.4 Доказательства вспомогательных лемм и утверждений

Доказательство леммы 3. Предположим противное: пусть существует замкнутый путь 7: [0,1] —> Т, нетривиально обходящий У и не содержащий точек множества А.

Рассмотрим функции 7!: [0,1] —> X, 72: [0,1] —> У, являющиеся проекциями пути 7 на X и У. Заметим, что отображения 72 и /1: 51 —» X имеют ненулевое число зацепления. Действительно, число зацепления 72 и /1 равняется произведению числа зацепления X и У на кратность обхода путем 72 окружности У. Оба сомножителя ненулевые.

Пусть отображение К\ [0,1] х [0, оо) —>■ М3 построено следующим образом: /2.(5, ¿) = 72(5) + I • 71(5)72(5). При этом

5 —>

Без ребра 5-6.

Без ребра 3-5. Без ребра 5-7. Без ребра 1-3.

Г" :;2,зб|

гЛ ;

Без ребра 1-5. Без ребра 4-8.

Без ребра 6-7. Без ребра 1-5.

\6

Без ребра 5-6. Без ребра 3-4. Без ребра 1-7.

3

Рис. 3. 3-вложения графов Петерсена без ребра

/¿(5,0) = 72(5), и уходит на бесконечность при Ь -л

—> оо. Исходя из определения множества А, для каждой точки (х,у) = (71(5),72(5)) £ Т носителя пути 7 на луче (х, у) за точкой у не найдется других точек X. Потому образ /¿(5, £) не пересекает X. Мы построили гомотопию отображения 72 в отображение на бесконечность, не пересекая отображения /1: 51 —>■ X. Это означает, что число зацепления /1 и 72 стало нулевым. Противоречие. Для X и В доказывается аналогично. □

Доказательство леммы 4. Рассмотрим последовательность (хг,уг) С А, (хг,уг) —> (х,у). Пусть хг — точка множества X, лежащая на луче (хг,уг) за точкой уг. Так как {¿г} — бесконечная последовательность на компакте X, то у неё есть сходящаяся подпоследовательность. Без ограничения общности считаем, что это {¿г}.

Прямые хгуг = хгхг сходятся к прямой ху, откуда следует, что Х\ лежит на ху за точкой у, так как соотношение хгхг =

А • хгуг (Л > 1) сохраняется и в пределе.

Полученное включение (ж, у) £ А, и означает, что А — замкнуто. Замкнутость В доказывается аналогично. □

Для доказательства утверждения 7 потребуется следующее утверждение:

Утверждение 8. Прямая пресекает конструкцию с «шапочкой» не более чем по 4 точкам, и 4-прямой может стать только прямая, пересекающая в двух точках верхний, и в двух точках — нижний слой «шапочки».

Доказательство утверждения 8. Если прямая I имеет точку М на внешности «шапочки», то она не может пересечь нижний слой более чем в одной точке, значит, 4-прямой она не является, откуда и получаем утверждение. □

Из этого утверждения тривиально следует, что любое вложение графа в конструкцию с «шапочкой» — 4-вложение. Доказательство утверждения 7. От противного, пусть 4-прямая нашлась. Рассмотрим проекцию получившейся картинки на плоскость а, содержащую границу «шапочки». Пользуясь утверждением 8 и тем, что проекции пересекающихся множеств на любую плоскость пересекаются, получим, что проекция 4-прямой обязана в двух точках пересечь

проекцию части образа, попавшей на верхний слой «шапочки», и в двух — попавшей на нижний слой. Причем обе точки нижнего слоя обязательно должны быть расположены между двумя точками верхнего слоя. Для фигур на рис. 2 6), в), г), д) таких прямых не существует.

В случае 2 а) 4-прямой может стать только прямая, проектирующаяся в пунктирный отрезок. Выберем радиус сферы, являющейся нижним слоем «шапочки» таким большим, чтобы вершина конуса, касающегося нижнего слоя по границе «шапочки», лежала между верхнем и нижним слоями «шапочки». Тогда ширину полосы на верхнем слое можно выбрать так, чтобы никакая прямая, пересекающая дугу на нижнем слое в двух точках, не пересекала полосу. Возможность такого выбора ширины очевидна, если рассмотреть сечение конструкции плоскостью /3, перпендикулярной а и содержащей дугу на нижнем слое (см рис. 5).

Осталось рассмотреть фигуру на рис. 2 е). Рассмотрим только план решения, так как технические детали полного доказательства требуют большого количества не предства-ляющих интереса рассуждений.

Очевидно, что если 4-прямая нашлась, то ее проекция либо совпадает с одним из прямолинейных отрезков, либо пересекает два или три из них. Первый случай противоречит утв. 8, так как каждый прямолинейный отрезок на рис. 2 д) пересекает пунктир только в одной точке. Докажем, что кривые на нижнем слое можно разместить так, чтобы 4-прямой не возникло. Обозначим за Г объединение трех дуг большой окружности на верхнем слое «шапочки», а за 7 одну (произвольную) из них. За Ь(7) обозначим множество прямых (х,у), где х Е 7 и у Е (Г\7) (при х = у мы считаем прямую касательной к верхнему слою, но, возможно, в любом направлении). В силу компактности 7 и (Г\7), а также объединения нижнего слоя с границей «шапочки», множество точек на нижнем слое «шапочки», не лежащих на прямых из Ь{7) — открыто. И так как проекция 7 лежит в этом множестве (при большом радиусе сферы нижнего слоя), то можно выбрать близкий путь 7' из той же точки на границе «шапочки» в центр нижнего слоя, не пересекающий 7, но по прежнему лежащий в этом множестве. Чтобы такие пути для разных дуг не пересекались, их можно располагать строго по

а) К6

Без ребра 5-6.

.6

Без ребра 3-5. Без ребра 5-7. Без ребра 1-3.

Г"

-»• к: гЛ ;'

Без ребра 1-5. Без ребра 4-8.

Без ребра 6-7. Без ребра 1-5.

Без ребра 5-6. Без ребра 3-4. Без ребра 1-7.

д)

3

3 3

Рис. 4. 3-вложения графов Петерсена без ребра

определенную сторону от проекций дуг, как это и показано на рис. 2 е). Теперь 3-вложимость очевидна — прямая, пересекающая две различные дуги на верхнем слое «шапочки», не может на нижнем слое пересечь пути, лежащие близко к их проекциям, а третью дугу нижнего слоя может пересечь не более чем в одной точке. □

Замечание 9. К рисункам б), в), г), д), е) можно добавить на верхнем слое малый диск в центре. Действительно, как при доказательстве для пункта а), выберем радиус сферы, являющейся нижним слоем «шапочки», таким большим, чтобы вершина конуса, касающегося нижнего слоя по границе «шапочки», лежала между верхнем и нижним слоями «шапочки». Прямая, пересекающая малый диск на верхнем слое в двух точках, не пересечет нижний слой.

1.5 2—вложимость.

Теорема 10. 2-вложимость графа в М3 эквивалентна его планарности.

Доказательство: 4= Так как плоскость гомеоморф-на открытому диску, а двумерная сфера содержит диск, из планарности графа следует его вложимость в сферу. Любая прямая пересекает сферу не более чем по двум точкам, и потому вложение графа в единичную сферу будет 2-вложением в Е3.

=>■ Для доказательства планарности всех 2-вложимых графов, ссылаясь на теорему Куратовского, достаточно доказать, что графы К5 и 7^,3 не являются 2-вложимыми. От противного. Пусть С — граф или К^з 2-вложенный в I3, А — некоторая фиксированная вершина. Обозначим через {а,г} образы середин входящих в неё рёбер, {В^} — вторые концы этих ребер. Пусть С — образ графа без полурёбер {Аа{}. Спроецируем С на единичную сферу с центром в точке А по лучам, выходящим из неё же. Так как на любой прямой содержится не более двух точек графа С, то на любой прямой, проходящей через А, содержится не более одной точки С, потому такая проекция будет вложением (? в

сферу. Пусть б? — образ С на сфере, точки {аг} — образы {аг}, точки {Вг} — образы {Вг}. Образ С графа разбивает сферу на конечное число компонент связности. Покажем, что точки {Вг} можно соединить с некоторой точкой одной из компонент дополнения. Докажем для этого, что существует компонента дополнения, на границе которой лежат все точки {Вг}.

Будем пользоваться тем, что С \ и™=1АВг не содержит висячих вершин. В таком случае границей каждой компоненты связности на сфере будет образ некоторого цикла графа, а значит, по известной теореме Римана это будет некоторая замкнутая Жорданова кривая^

Так как граф компактен, С отдален от точки А на некоторое расстояние. Для любого числа г найдется такая малая окрестность 11£ точки А, что для любой точки А\ £ 11£ при проекировани на £феру из точки А\ вместо точки А образ каждой точки из С передвинется не более чем на е (расстояние измеряется в трехмерном пространстве для множеств, расположенных на единичной сфере в точке А и единичной сфере в точке Ах, соответственно). Выберем число меньшее минимума из расстояний от каждой точки аг до множества С \ /г, где 1г — образ полуребра агВг. В таком случае при проекции из любой точки множества /7| точки

аг останутся в тех же компонентах связности дополнения С, что и при проекции из А.

Докажем, что {аг} лежат в одной компоненте связности. Выбрав точку ие на ребре АВ\, спроектируем из нее на сферу не только С, но и все точки С\ А\. Такая проекция тоже будет вложением. На сфере появился образ точки А, и он соединен со всеми точками {аг}, кроме ах - Значит, {аг}(г ф 1) лежат в одной компоненте связности. Выбрав точку А2 £ ие на ребре АВ2, аналогичным образом получим, что точки {аг}(г ф 2) лежат в одной компоненте связности. Таким образом, так как степень вершины А не меньше трех, получаем, что все {аг} лежат в одной компоненте связности.

Обозначим за 7 границу той компоненты связности, в которой лежат все аг. Так как 7 — замкнутая жорданова кривая, то существует гомеоморфизм отображающий од-носвязную область, ограниченную кривой 7, на единичный

круг, и этот гомеоморфизм продолжается на границу. Возьмем в круге отрезки {0(р(В{)}. Обозначим ср~1(0) = А, прообразы отрезков станут рёбрами {АВ¿}. Граф О \ и^Да^ вместе с А и прообразами указанных отрезков гомеоморфен С и вложен в сферу. Так как С — это или К3 3 получаем противоречие с теоремой Куратовского, из чего делаем вывод, что и все другие непланарные графы 2-

вложимыми не являются. □

1.6 Несколько примеров.

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

Предложение 11. Букет двух графов Куратовского 3-вложим.

Доказательство Воспользуемся конструкцией на рис. 2 г) и предложением 1.4. На рис.6, 7 и 8 показаны искомые 3-вложения. Для каждого из графов общая точка может быть вершиной либо точкой ребра. На каждом из рисунков образ одного графа полностью расположен слева от центра, а образ другого — справа. При изображении графа вершины первой доли изображены закрашенными точками, а вершины второй доли — пустыми. Изображены не все возможные варианты, оставшиеся строятся аналогично.

Предложение 12. Графы для п ^ 6 являются 3-

вложимыми.

Доказательство. Воспользуемся конструкцией на рис. 2 е). Одну из вершин первой доли поместим в центр верхнего слоя «шапочки», вторую в центр нижнего слоя, а третью — на внешность, (см. рис. 9)

Гипотеза 13. Граф К37 не является Ъ-вложимым.

Рис. 6. 3-вложения букетов графов Куратовского-Понтрягина V К5 и V в конструкцию с "шапочкой"

1.7 Конструкция с «кепочкой».

Приведем еще один пример 3-вложения — 3-вложение графов Куратовского-Понтрягина с кратными ребрами с помощью конструкцией с «кепочкой». Основной конструкцией, используемой при конструировании примера, является почти выпуклая пленка.

1.7.1 Конструирование почти выпуклой пленки.

Выпуклой кривой будем называть замкнутую связную часть границы строго выпуклого множества на плоскости. Выпуклая кривая имеет две граничные точки, одну из которых будем называть началом, другую концом. Натягиванием выпуклой кривой I на отрезок АВ в полуплоскость а (отрезок АВ принадлежит прямой, ограничивающей полуплоскость) будем называть отображение / : I —»• ск, такое, что кривая

Рис. 7. 3-вложение букета графов Куратовского-Понтрягина К3.3 V ^3.3 в конструкцию с

"шапочкой"

Рис. 8. 3-вложения букетов графов Куратовского-Понтрягина V и К^ V А^з, общая точка для одного из графов является точкой ребра

/(/) подобна I, причем начало кривой I отображается в точку А, а конец в точку В.

Выберем две выпуклые кривые 1(Ь) и ¿(¿) . Натянем кривую /(£) на отрезок ОА, О = (0,0,0), А = (1,0,0) в полуплоскость г = 0, у > 0, Объединение полученной кривой с

Рис. 9. 3-вложение графа в конструкцию с "шапочкой".

отрезком OA будем называть первичным контуром. Заметим, что каждая прямая, за исключением оси X, пересекает контур не более чем по двум точкам.

Введем функцию р(х), сопоставляющую каждому значению xq отрезок, концами которого являюся точки, по которым прямая х = xq, z = 0 пересекает первичный контур. Если прямая не пересекает первичного контура, считаем отрезок пустым. Для каждого xq на отрезок р{хо) в полуплоскость х = Xq, z > 0 натянем кривую s(t). Образ кривой s(t) под действием этого натягивания обозначим sXo(ty Легко убедиться, что объединение кривых sx для всех значений х представляет собой непрерывную поверхность. Будем называть такую поверхность почти выпуклой пленкой, а кривые l{t) и s(t) — первой и второй порождающей кривой почти выпуклой пленки.

Лемма 14. Почти выпуклая пленка строго выпукла, за исключением единичного отрезка оси X. (Любая прямая, кроме оси ОХ, пересекает почти выпуклую пленку не более чем по двум точкам.)

Доказательство. Рассмотрим пару точек А(х\,у\, z\) и В(х2, У2, Z2), лежащих на почти выпуклой пленке 7г. Докажем, что отрезок АВ лежит ниже почти выпуклой пленки. Возможны два случая.

Первый случай: х\ = хч- В этом случае утверждение очевидно следует из выпуклости кривой s(t).

Второй случай: х\ ^ Х2■ Соединим концы отрезков р{х\) р{х2). Полученная обобщенная трапеция будет лежать внутри первичного контура по построению кривой l(t). Обозначим эту обобщенную трапецию за Т. Для каждого 23 такого, что х\ < .тз < Х2 на отрезке, по которому прямая

х = £з, 2 — 0 пересекает трапецию Т, построим кривую с концами в концах отрезка, являющуюся образом кривой s(t) под действием гомотетии. Так как обобщенная трапеция лежит внутри порождающего отрезка, а кривая s(t) выпукла, полученная пленка ф будет лежать не выше 7г.

Заметим теперь, что пленка ф является частью поверхность обобщенного усеченного конуса либо обобщенного цилиндра. Из этого и из выпуклости кривой s(t) следует выпуклость пленки ф. Так как точки А и В лежат на ф, внутренние точки отрезка АВ лежат ниже ф, а значит, и ниже тт. Случай разобран. Выпуклость доказана.

1.7.2 Конструирование «кепочки».

Построим почти выпуклую пленку 7Гх описанным выше способом, в качестве первой и второй порождающих кривых будем использовать дуги окружностей с углами а\ и ¡3\ соответственно. Пленка 7Г2 получается из пленки 7Гх отражением относительно плоскости z = 0. Объединение пленок 7Гх и 7Г2 предстваляет собой поверхность, топологически эквивалентную сфере. Обозначим эту поверхность за 7г.

Пусть ф\ — почти выпуклая пленка, первой и второй порождающими кривыми которой являются дуги окружностей с углами СК2 > «1 и > А- Пусть пленка Ф2 получается из пленки ф\ отражением относительно плоскости z = 0. По аналогии с тт2 поверхностями 7г построим поверхности Ф2 и ф. Так как а.2 > сх.\ и /З2 > /Зх, несложно убедиться что вся поверхность 7г, за исключением отрезка АВ, лежит внутри части пространства, ограниченной поверхностью ф.

Построим двугранный угол, ребром которого является ось ОХ, величина которого /Зх, одной гранью которого является плоскость XOY, а другая грань лежит в полупространстве z > 0. За ф обозначим ту часть пленки ф\, которая лежит вне этого угла.

Определение 15. Конструкцией с «кепочкой» будем называть объединение двух почти выпуклых пленок и 7Т2, называемых верхним и нио/снем слоем «кепочки», и поверхности ф, являщейся фрагментом почти выпуклой пленки, называемой «козырьком».

Докажем основное свойство конструкции с «кепочкой».

Лемма 16. Любая прямая, кроме оси ОХ, пересекает конструкцию с «кепочкой» не более чем по трем точкам.

Доказательство. Рассмотрим произвольную прямую /, не совпадающую с осью ОХ. Несложно убедиться, что поверхность 7г является выпуклой за исклювением отрезка АВ, и потому любая прямая, не совпадающая с осью ОХ, пересекает 7г не более чем по двум точкам. Так как поверхность ф также является выпуклой везде за исключением отрезка АВ, прямая I пересекает ф не более чем по двум точкам. Рассмотрим три случая.

Первый случай: прямая I имеет не более одной общей точки с «козырьком». Так как прямоя не может иметь более двух общих точек с поверхностью 7г, число точек пересечения прямой I с кепочкой не превышает трех.

Второй случай: прямая I пересекает «козырек» по двум точкам Р и <5, точка Р лежит на отрезке АВ. В этом случае прямая может иметь не более одной отличной от Р общей точки с поверхностью 7г. Прямая I имеет не больше трех точек пересечения с «кепочкой».

Третий случай: прямая I пересекает «козырек» по двум точкам Р и (5, не лежащим на отрезке АВ. Заметим, что отрезок Р(^ полностью находится вне двугронного угла, использовавшегося при построении «кепочки», а значит, отрезок РС} не пересекает тт. Дополнение отрезка РС} на прямой I находится вне поверхности ф. Так как поверхность 7г находится внутри ф: за исключением отрезка АВ, прямая I не пересекает 7г.

Видим, что во всех случаях прямая I имеет не более трех общих точек с «кепочкой». Лемма доказана.

1.7.3 Трехузловые графы.

Приступим к главному — к 3-вложениям графов с помощью «кепочки».

Определение 17. Граф С называется трехузловым, если у него имеются вершины А, В, С, такие, что существует разбиение графа С на подграфы С\ и С?, не обязательно связные, со следующими свойствами:

• вершины А, В и С явлются единствеными общими точками подграфов;

• подграф С\ является планарным графом;

• существует такое вложение подграфа С1 в плоскость, что вершины А, В и С можно соединить линией, не пересекающей образ графа в других точках;

• подграф можно вложить в полуплоскость так, что на прямой, ограничивающей полуплоскость, будут лежать вершины А, В и С и только они.

Теорема 18. Трехузловость графа эквивалентна его 3-вложимости в конструкцию с «кепочкой».

Доказательство.

Пусть граф С является трехузловым. Докажем, что он 3-вложим в конструкцию с «кепочкой». Пусть А, В, С — вершины, и (?2 - подграфы графа С из оперделения трехузловости. По определению, граф является планарным графом. Совокупность верхнего и нижнего слоя «кепочки» топологически эквивалентна плоскости. Расположим на этой поверхности граф поместив на ось ОХ вершины А, В и С и только их. Это возможно по определению трехузловости. Так как «козырек» топологически эквивалентен полуплоскости, мы можем расположить подграф на «козырьке». Вложение графа получено. Так как на оси ОХ расположены только три точки образа графа, это вложение является 3-вложением.

Докажем обратное. Пусть граф С 3-вложим в конструкцию с «кепочкой». Рассмотрим его 3-вложение. Если на оси ОХ расположено меньше трех точек, то граф С планарен. Если на оси ОХ расположены три точки, обозначим их А, В и С. Легко убедиться, что эти вершины обладают свойствами, необходимыми для трехузловости графа. Теорема доказана.

Теорема 19. Граф, полученный из графа Куратовского-Понтрягина увеличением кратности ребер, является 3— вложимым.

Доказательство.

Докажем, что существует 3-вложение такого графа в конструкцию с «кепочкой». Докажем для этого, что графы Куратовского-Понтрягина являются трехузловыми. Действительно, обозначим за, А к В любые две вершины графа в случае и две вершины из разных долей в случае Кз;з_ В качестве выступит кратное ребро АВ, вся остальная часть графа — в качестве Известно, что графы Куратовского-Понтрягина без ребра вкладываются в плоскость. Кратности ребер этого свойства не изменят. На рис. 10 показаны для случая и .Кз.з такие вложения Сх в плоскость, какие требуются в определении трехузловости. Очевидно, что удовлетворяет требованию из определения трехузловости. Графы Куратовского-Понтрягина с кратными ребрами являются трехузловыми, а значит, 3-вложимы. Теорема доказана.

1.8 О конкретных примерах 4-вложений графов.

Опишем способы получения особых вложений для любого графа с помощью конструкции с «шапочкой» и конструкции с «кепочкой».

Лемма 20. Любой граф можно вложить в объединение трех полуплоскости с общей границей.

Доказательство. Известно, что любой граф можно отобразить в плоскость с конечным числом самопересечений. Пусть / — отображение заданного графа С в плоскость ХОУ с конечным числом точек самопересечения. Малым

шевелением можно добиться того, чтобы все точки самопересечения имели различную координату у. Существует полином Ньютона р(х), график у = р{х) которого проходит через все точки самопересечения образа графа. Применим к плоскости диффеоморфизм х, у) = (х,у—р(х)). После этого преобразования получим отображение ё, о /, при котором все точки самопересечения графа лежат на оси ОХ.

Построим вложение графа С в объединение трех полуплоскостей: ХОУ, у > 0; ХОУ, у < 0; ХОг, г > 0. Для этого достаточно изменить отображение о? о / в окрестности каждой точки самопересечения следующим образом (см. рис. 11). Вложение получено. Теорема доказана.

Утверждение 21. Любой граф является 4~вложимым.

Доказательство. Конструкция с шапочкой содержит топологические три полуплоскости с общей границей. Из леммы 20 вытекает, что любой граф вкладывается в конструкцию с «шапочкой», и следовательно 4-вложим.

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

Доказательство. Аналогично предыдущему доказательству получаем, что граф можно вложить в конструкцию с «кепочкой», возможно с большим числом точек на отрезке пересечения «козырька» и плёнок. За исключением этой прямой, все остальные пересекают образ графа не более чем по трем точкам по лемме 16.

Рис. 11. Разведение самопересечения

2 Минимизация числа точек графа, принадлежащих гиперплоскости

2.1 Необходимые определения и свойства

Максимальное число точек некоторого множества на гиперплоскости назовем числом гиперпланарности данного множества. Так как любые п точек задают гиперплоскость, понятно, что число гиперпланарности любого множества, содержащего по крайней мере п точек, не может быть меньше п.

Числом п-гиперпланарности графа будем называть минимум по всем вложениям данного графа в п-мерное пространство числа гиперпланарности образа. Если размерность пространства ясна из контекста, это число называется просто числом гиперпланарности графа. Для оценки сверху числа гиперпанарности построим вложения с малым числом гиперпланарности.

Основной конструкцией для анализа вложений с малым числом гиперпланарности является моментная кривая {£, £2, ¿3,..., рассматриваемая в теории многограников [9]. Она обладает очень важным свойством с точки зрения рассматриваемых вложений - любая гиперплоскость пересекает ее не более, чем по п точкам.

Предложение 23. Две различные полиномиальные кривые могут иметь не более чем п2 точек пересечения.

Доказательство. Рассмотрим две различные полиномиальные кривые и Пусть О2,..., От — их точки пересечения. Пусть {х\,х2, ..^х^} — система координат, в которой кривая /(£) является моментной, а {у\, ..., уп} — система координат, в которой кривая является моментной.

Рассмотрим случай, когда оси х\ и у\ параллельны. В таком случае можно обе кривые привести к параметру х\. Получим: ¿(£1) = {XI, х2г,..., ж?}, ¿(хО = {XI, Р2{х 1),..., Рп(х 1)}, где Рг — линейно независимые полиномы степени не выше п.

Заметим, что для каждой точки 0{ с координатами х2..., хп^)

верны равенства:

Х1,г = Рз(х1л)-

Так как степень каждого не превышает п, при т > п + 1 совпадение х\ г и Р3{х\^) в т точках Ог означает, что Р3 = х\. Это противоречит тому, что кривые I и в различны. Значит, в рассматриваемом случае число точек пересечения кривых не может превышать п, и тем более п2. Для случая параллельности осей х\ и г/1 предложение доказано.

Пусть теперь оси Х\ и у\ не параллельны. Выразим единичный вектор по оси у\ через вектора системы {жг}. Получим соотношение: у\ = + а\Х\ + 0,2X2 + ... + апхп. Заметим, что для каждой точки па кривой I верны соотношения Х2 = х2ъ — ..хп = х™. Значит, каждая точка Ог удовлетворяет уравнению у\ = а^ + а\Х\ + а<2х\ + ... + апХ™. Так как оси не параллельны, это уравнение не является линейным.

Проведем аналогичные рассуждения для кривой и координат уг. Получим: хх = 60 + Ъхух + Ъ2у2 + • • • + Ьпуп. Для каждой точки кривой и в частности для точек Ог получим соотношение Х\ = 6д + 612/1 + 622/1 + • • • + ЬпуЭто уравнение также не является линейным.

Теперь подставим одно из полученнных равенств для точек Ог в другое. Получим, что для всех точек Ог верно равенство:

= 60+61 • .+апХ1)+Ъ2(аъ+а1Х1+а2х\+.. ,+апХ1)2+...

... + 6п(а0 + а\Х\ + а2х\ + ... + ОпЖ™ )п.

Из нелинейности уравнений у\ = ао + £¿1X1 + а,2х\ + ... + апХ1 и х\ = 6о + Ъ\у\ + ¿>22/1 + ... + Ьпу1 следует, что полученное уравнение не является тождеством. Перенеся х\ в правую часть равенства, получим полином степени не более п2. Ясно, что значений х\, удовлетворяющих этому равенству, не более п2. Так как различные точки кривой I не могут иметь одинаковую координату из этого следует, что точек пересечения кривых не больше чем п2. Предложение доказано.

Предложение 24. Любые п касательных векторов к мо-ментной кривой, взятые в различных точках, линейно независимы.

Доказательство. Касательный вектор к моментной кривой в точке t = ¿о имеет вид (1, 2¿0, 3ig, • • nig-1). Докажем, что определитель, составленный из п касательных векторов к моментной кривой в различных точках не равен нулю. Это равносильно линейной независимости векторов.

Легко заметить, что матрица, составленная из координат этих векторов является матрицей Вандермонда, а потому ее определитель — определитель Вандермонда:

П ^г-tj)-

Он равен нулю тогда и только тогда, когда есть tt — t3, i ^ Ф j. Значит он не равен нулю, так как все числа t% различны. Линейная независимость векторов доказана.

2.2 Верхняя оценка числа гиперпланарно-сти для случая деревьев.

Теорема 25. Для любого дерева G при п > 3 сущеетвеут вложение в п-мерное пространство такое, что число ги-перпланарности образа не превосходит n+k—l, где к — минимальное число отрезков Аг, которыми моэюно покрыть дерево G так, что любые два отрезка могут пересекаться только по вершине графа.

Замечание 26. В этой теореме рассматривается "алгебраическое число пересечения" — каждая точка гиперплоскости считается столько раз, на каком числе отрезков она лежит.

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

Предложение 27. Пусть для двух непересекающихся отрезков на оси t Т\ = [¿1, ¿i] и Т2 = [¿2,^2] выделены отрезки I|п и 1\г2 моментной кривой. Пусть к ним применены параллельные переносы h\ и h2 соответственно, так что получены кривые l\ = h\(l\Tl) и /2 = hx{l\T2). Пусть на кривой

/2 отмечена некоторая точка А, являющаяся общей точкой кривых. Тогда существует такой невырожденный отрезок Т2 С 72, что кривые 1\ и 12 = Ь2(1\т2) будут пересекаться только в точке А, причем свойство точки А быть внутренней или граничной точкой кривой сохранится.

Доказательство По предложению 23, число точек пересечения кривых ¿1 и ¿2 конечно. Из этого факта очевидно следует существование подотрезка Т2, не содержащего других точек пересечения, кроме А, такого что для кривой ¿2 сохранено свойство точки А быть граничной либо внутренней точкой. Предложение доказано.

Рассмотрим классическую моментную кривую /(£) = (£, £2,..., ¿п). Заметим что каждый отрезок г на оси £ порождает кривую в пространстве I\Т. Выберем на оси £ отрезок т\. Зададим произвольный гомеоморфизм между А\ и 1\.

Рассмотрим случай, когда один из отрезков А^ пересекается с А\. Без ограничения общности можем считать, что это А2. Так как С является деревом, точка перечечения А\ и А2 единственна. Выберем произвольный отрезок Т2 на оси не пересекающийся с т\. Можно аналогичным образом задать соответствие между /2 = 1\т2 и ^2- Совместим образы вершины А\[~\А2, применив к 12 параллельный перенос. Из предложения 27 вытекает, что выбором Т2 мы можем обеспечить отсутствие пересечения 1\ и /2, за исключением образа вершины А\ Р| Ач-

Рассмотрим случай, когда с А\ не пересекается не один из Аг. Выберем произвольный отрезок Т2 на оси ¿, не пересекающийся с т\ и зададим соответствие между /2 = Цт2 и ^2-Параллельно перенесем 12 так, чтобы 1\ и ¿2 не пересекались. Для обоих случаев построено вложение А\ и А2 в пространство.

Аналогичным образом по индукции добавим к конструкции все остальные ^ — образы А^ сохраняя тополгию их объединения на каждом шаге. Получим вложение дерева (7 в пространство.

Докажем, что число гиперпланарности образа при полученном вложении не превышает п + к — 1. Пусть некая гиперплоскость а пересекает образ графа по г точкам. Пусть а пересекается с Ц по точкам. Тогда если р^ > 1 то из

непрерывности следует существование рг — 1 касательных векторов к 1г: параллельных а. Если рг < 1, таких касательных векторов > 0 > рг — 1. Суммируя полученные неравенства по всем г, получаем, что число д касательных векторов ко всем ¿г, параллельных а, удовлетворяет неравенству д > Х^О9« — I) = г — к. По предложению 24, <7 < п — 1 (так как касательные вектора к 1г равны касательным векторам к I). Из г — /с < д < п — 1 получаем г < п + к — 1. Теорема доказана.

2.3 Ассимптотические свойства оценок

Перейдем к доказателству ассимптотических свойств последней полученной оценки. Приведем результат К. Обла-кова.

Определение 28. Выберем на графе С п точек, которые далее будем называть "выделенными". Назовем отображение графа С в прямую корректным, если:

• все выделенные точки отобразились в начало координат;

• если образы концов ребра не совпали, ребро линейно отображается в отрезок, соединяющий образы концов;

• если образы концов ребра совпали, выделим на этом ребре дополнительную точку, называемую серединой. Середина обязана отобразиться в точку прямой, не совпадающую с образом ни одной из вершин. Половины ребра линейно отображаются в отрезок, соединяющий образ середины с образом концов.

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

Теорема 29. (Облаков) Кратность одномерной проекции оценивает число гиперпланарности снизу.

Вычислим эту оценку для случая дерева.

Теорема 30. Пусть задано дерево с вершинами г>1, г>2 ..., уг, Пусть размерность пространства не меньше числа вершин дерева степени 3 и выше. В таком случае кратность одномерной проекции этого дерева не меньше следующей величины:

Е

¿е§г;г>3

С^ Уг

Список литературы диссертационного исследования кандидат физико-математических наук Облакова, Татьяна Александровна, 2013 год

Список литературы

[1] Ostrand P. Dimension of metric spaces and Hilbert's problem 13. Bull. Amer. Math. Soc, 1965, V. 7, P. 619-622.

[2] Богатый С.А. Гипотеза Борсука, препятствие Рыжкова, интерполяция, аппроксимация Чебышева, транс-версальная теорема Тверберга, задачи. Труды матем. ин-та им. В.А. Стеклова, 2002, т. 239, с. 63-82.

[3] С. А. Богатый, В. М. Вылов Вложения Робертса и обращение трансверсалъной теоремы Тверберга Матем. сб. 2005, т. 196 №11 стр. 33-52

[4] Богатый С.А. Цветная теорема Тверберг. Вести. Моск. Ун-та, сер. 1, математика, механика, 1999, №3, с. 14-19.

[5] Goodsell Т.Н. Strong general position and Menger curses Topol. Appl., 2002, V. 120, №1-2, P. 47-55.

[6] Zivaljevic R.T. The Tverberg-Vrecica problem and the combinatorial geometry on vector bundles. Israel J. Math., 1999, V. Ill, P. 53-76.

[7] Conway J., Gordon.C. Knots and links in spatial graphs. J. Graph Theory, 1983, V. 7, P. 445-453.

[8] Sachs H. On spatial representation of finite graphs. Finite and Infinite Sets (Eger, 1981), 1984, North-Holland, Amsterdam-New York, P. 649-662.

[9] А. Брёнстед Введение в теорию выпуклых многогранников. М. Мир 1988

[10] Seymour P.D. Progress on the Four Color Theorem. Proceeding of the International Congress of Mathematicans, Zurich, Switzerland, 1994, V. 1, P. 183— 195.

[11] Robertson N., Seymour P.D., Thomas R. Sachs' linkless embedding conjecture. J. Combin. Theory, Ser B, 1995, V. 64, P. 185-227.

[12] Антонова Т.А., Облаков К.И. Специальные вложения графов в трехмерное пространство, //Вестн. Моск. Унта. Матем. Механ. 2008. N6. 26-31.

[13] Дубровин. Б. А., Новиков С.П., Фоменко А. Т. Современная геометрия. Методы и приложения. Т.2: Геометрия и топология многообразий. М.: Эдиториал УРСС, Добро-свет, 2001.

[14] Прасолов В. В. Элементы комбинаторной и дифференциальной топологии. М.:МЦНМО, 2004.

[15] Conner Р. Е., Floyd, Е.Е. Fixed point free involutions and equivariant maps //Bull. Amer. Math. Soc. 1960. 66. N6. 416-441.

[16] Bogatyi S.A. Finite-to-One Maps. //Topol. and Appl. 2008. N155. 17-18.

[17] M. Skopenkov Embedding products of graphs into Euclidean spaces.// Fundamenta Mathematicae 179 (2003), 191Ц197. Перевод на русский язык: arXiv:0808.1199vl [math.GT],

[18] J.С. Mairhuber On Haar's theorem concerning Cheby-shev approximation problems having unique solutions Proc. Amer. Math. Soc. 1956 7 №4 pp. 609-615