Минимально-линейные вложения графов

• Автор: Облакова, Татьяна Александровна
• Шифр специальности: 01.01.04
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 44 с. : ил.

Содержание
Введение.
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 -> I3 одномерного компакта в Ж3 сколь угодно малым изменением может быть превращено в такое вложение /е: X —>■ К3, что на всякой прямой в Ж3 будет лежать не более четырёх точек образа /£(Х) компакта X. Укажем, что существование таких «экономичных вложений» доказал также Гудселл [5]. Оказывается, что число 4 не может быть уменьшено не только на уровне теоремы плотности «экономичных» отображений, но и на уровне теоремы существования. Именно, Живалевич доказал, что для всякого вложения в Ж3 существует прямая, пересекающая граф не менее чем по четырем точкам [6]. Автором доказано наличие такой прямой для меньших графов (граф Каа без ребра является подграфом А^.б), таким образом усилен результат Живалевича.

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

3 Случай четырехмерного пространства.
3.1 Постановка задачи.
Этот раздел посвящен минимально-линейным вложениям графов в четырехмерное пространство. Этот вопрос разделяется на три случая: пересечение графа прямой, двумерной плоскостью и гиперплоскостью. Случай пересечения графа гиперплоскостью рассмотривается в предыдущем разделе.
Случай прямой исчерпывающе описывается следующим утверждением:
Утверждение 33. Любой граф можно вложить в п-мерное пространство при п > 3 так, что на любой прямой содержится не более двух точек образа графа.
Доказательство. При и > 3 единичная сфера в п-мерном пространстве по меньшей мере трехмерна, а значит, в нее можно вложить любой граф. Любая прямая пересекает единичную сферу, а значит, и образ графа, не более чем по двум точкам. Утверждение доказано.
Наибольший интерес представляет пересечение образа графа в четырехмерном пространстве двумерной плоскостью. Числом 2-планарности произвольного множества в четырехмерном пространстве назовем число точек этого множества, содержащихся в одной двумерное плоскости. Ясно, что число 2-планарности множества, содержащего более двух точек, не может быть меньше трех, так как любые три точки задают двумерную плоскость. Будем называть числом 2-планарности графа минимальное по всем вложениям данного графа в четырехмерное пространство число 2-планарности образа.
3.2 Графы с наименьшим числом 2-планарности.
Утверждение 34. Число 2-планарности окружности равно трем.
Доказательство. Рассмотрим замкнутую кривую в четырехмерном пространстве ОХУЛЦ, заданную параметри-