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

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

Содержание
Введение

1 Пересечение графа прямой

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

1.2 Несвязные объединения графов Куратовского-

Понтрягина

1.3 Утверждение о 3-вложимости собственных подграфов

1.4 Отображение поверхностей в касательное пространство сферы

1.5 Доказательство теоремы о графах Куратов-

ского-Понтрягина

1.6 Обобщение результата

2 Невозможность существования двух локально-минимальных сетей Штейнера, сонаправ-ленных в вершинах
2.1 Введение. О задаче Штейнера
2.2 Основные определения
2.3 Постановка и решение задачи
3 Сети Штейнера на многообразиях с плоской метрикой
3.1 Формулировка теоремы
3.2 Развитие аппарата
3.3 Доказательство основной теоремы
3.4 Сети Штейнера на торе
4 Пересечение графа гиперплоскостью
4.1 Основные определения
4.2 Обобщенная момснтная кривая
4.3 Ветвящаяся моментная кривая
4.4 Теорема о ветвящейся моментной кривой
4.5 Число минимаксного сечения
4.6 Верхняя оценка числа гиперпланарности графов
4.7 Об улучшении вложений с помощью момснт-
ных кривых
4.8 Нижняя оценка в общем случае

Список публикаций автора
Список литературы

Введение.
Работа посвящена минимальным вложениям графов в евклидово пространство.
В этой работе рассматриваются вложения, являющиеся минимальными по трем различным характеристикам. Во-первых, это вложения, при которых минимальное число точек образа графа лежит на одной прямой (раздел 1). Во-вторых, рассматриваются сети Штейнера — минимальные по длине связные континуумы, затягивающие заданное конечное множество точек на плоскости (разделы 2 и 3). В-третих, рассматриваются вложения графов в евклидово пространство, при которых наименьшее число точек образа принадлежит гиперплоскости (раздел 4).
Различные вложения графов рассматривались в математике в течение последнего полувека. Классическими стали теоремы о вложении произвольного графа в трехмерное пространство, о минимальности и полноте семейства графов Ку-ратовского с точки зрения невложимости в плоскость.
В задаче суперпозиции возникают базисные вложения [1]. К.Борсуком было введено понятие -регулярных вложений компактов [3]. Эти вложения возникают в задачах интерполяции и аппроксимации. Болтянский, Рышков и Шишкин исследовали -регулярные вложения для случая полиэдров [20]. Также ими занимались С. А. Богатый и В. М. Вылов [2], [21].
Вложения, рассматриваемые в первой части, являются обобщением -регулярных вложений. Богатый [4] доказал, что всякое отображение /: X —> Ж3 одномерного компакта в К3 сколь угодно малым изменением может быть превращено в такое вложение /с: X —> К3, что на всякой прямой в Ж3 будет лежать не более четырех точек образа /£{Х) компакта X. Укажем, что существование таких „экономичных вложений“ доказал также Гудселл [5]. Оказывается, что число 4 не может быть уменьшено не только на уровне теоремы плотности „экономичных“ отображений, но и на уровне теоремы существования. Именно, Живалевич доказал, что для всякого вложения /А;д в Ж3 существует прямая, пересекающая граф не мепее чем по четырем точкам [6]. В данной работе результат усилен. Найден другой класс 3-невложимых графов

части контуров ОцОу и ООіі не пересекают граф, так как их координаты z равны г и 22 соответственно. Часть 02іОц у контуров общая. Части у них получаются па-
раллельным переносом друг из друга в случае цилиндра. В случае же конуса граф пересекает отрезки О12О22 и ОщОтл с одинаковыми кодирующими векторами в силу того, что углы векторов кодирующих пересечение Є и Ь-2, Ь'А в точках с одинаковой координатой 2 отличаются на 6а, где а — угол развертки конуса, а так как а кратен я/З, то 6а кратно 2л. В обоих случаях буквы, задающие пересечение графа с контуром, не изменятся.
Пусть теперь Сі = {(2, ф) € Сг<р Є (<р2, <Ач]}- Вычислим сумму эйлеровых характеристик этих множеств. Пусть Л/(.5,;) — замыкание внутренности .ч,-. Легко понять, что множества Сі представляют собой разность части графа Сг, попавшей в М(в2) и части Оі, попавшей в М(яі). Так как значение /(гв(5г)) равно сумме эйлеровых характеристик частей графов С і и (?2, попавших во внутренность контура ,чг, получаем х(@і) + х(Фг) = ДЧ)) -/(Ч5і)ДНо гфі) и Ч5г) — одно и то же слово, откуда у(6’і ) + у(6*2) = 0.
Теперь вернемся к пространству X. Легко заметить, что при отображении р множества С и С2 шестикратно накрывают (її и С-2 соответственно. Значит, верно равенство ДСтНДСг) = 6(х(Сі)+х(С2))- Получаем х(Сі)+х(Фг) = = 6-0 = 0. С другой стороны, так как графы Сі не содержат циклы, и хотя бы один их них не гіуст, то х(Сі) +х(Дг) > 0. Полученное противоречие с отсутствием циклов у одноцветных графов Сі и С2 доказывает теорему.
3.4 Сети Штейнера на торе.
На плоском торе аналог теорем 5 и 6 неверен. На рисунке 9 показаны красное и синее деревья без циклов на торе с углами, кратными 60°. Пользуясь идеями, обозначенными этим примером, можно построить и локально минимальные сети Штейнера — сам пример не годится, так как эйлеровы характеристики Сг различны. Но так как для этого требуются слишком громоздкие геометрические построения, на этом рисунке только обозначено, как обходятся условия доказанных теорем.