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

• Облаков, Константин Игоревич
• кандидат физико-математических наук
• 2012

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

Введение.

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 сколь угодно малым изменением может быть превращено в такое вложение fe: X —» Ж3, что на всякой прямой в К3 будет лежать не более четырех точек образа ¡£{Х) компакта X. Укажем, что существование таких „экономичных вложений" доказал также Гудселл [5]. Оказывается, что число 4 не может быть уменьшено не только на уровне теоремы плотности „экономичных" отображений, но и на уровне теоремы существования. Именно, Живалевич доказал, что для всякого вложения К^ а в Е3 существует прямая, пересекающая граф не менее чем по четырем точкам [6]. В данной работе результат усилен. Найден другой класс 3-невложимых графов — несвязные объединения графов Куратовского-Понтрягина, в частности, граф K^ß U К33, являющийся собственным подграфом .Кб,б- Доказано, что эти графы являются минимальными в том смысле, что при удалении любой точки из такого графа оставшееся множество может быть 3-вложено в пространство (теорема 1).

Результат о 3-невложимости несвязного объединения графов Куратовского-Понтрягина может быть также выведен как следствие из теорем 2 и 3 из работы Р.Н. Карасева [24]. При доказательстве этих теорем использовалась эквивари-антность отображений взрезанных полиэдральных квадратов графов. Авторское решение получено независимо и использует утверждение, работающее также и в случае не эквивариантных отображений, хотя при переходе к степеням отображений в данном частном случае была использована эквивариантность.

Вторая часть посвящена так называемой проблеме Штей-нера — задаче нахождения минимальной по длине сети (одномерного связного континуума), затягивающей данное конечное множество точек на плоскости [12, 13]. Эта задача имеет широкое практическое применение: транспортная задача, разводка микросхем, построение филогенетических деревьев. Оказалось, что удобно рассматривать не только кратчайшие (т.е. глобально минимальные), но и локально-минимальные сети. Локально-минимальная сеть в евклидовой метрике состоит из отрезков прямых (ребер), угол между любыми двумя смежными ребрами не менее 120° [14]. Jlo-кально-минимальных сетей для данного набора точек может быть несколько. Возможно даже существование нескольких глобально минимальных деревьев. Если они не сонаправле-ны в граничных вершинах, то малым шевелением граничных вершин можно добиться того, что только одно из деревьев останется глобально минимальным. Используя это свойство А.О. Иванов и A.A. Тужилин доказали [15], что множество таких расположений точек, для которых не существует двух глобально минимальных деревьев открыто и всюду плотно в множестве всех расположений. Они опирались на утверждение, гласящее что не существует двух глобально минимальных деревьев, сонаправленных в вершинах. Их доказательство этого утверждения оказалось чрезвычайно громоздким. Во второй части данной работы дается простое доказательство более сильного утверждения: не существует двух локально-минимальных деревьев, сонаправленных в вершинах (теорема 4). Данный результат распространен на случай локально-минимальных сетей на цилиндре с илокой метрикой и на конусе с углом развертки, кратным 60° (теорема 6). Доказано, что для случая плоского тора аналогичное утверждение не верно — пострен пример локально-минимальных сетей, сонаправленных в вершинах.

На вложения, рассматриваемые в третьей части, накладываются более слабые и в некотором смысле более общие условия чем /¿-регулярность — ограничивается количество точек, которые может содержать произвольная гиперплоскость. Практически единственным результатом, касающимся этого семейства вложений, является теорема Мэрхьюбера о том, что любое компактное множество в п-мерном пространстве, содержащее не более п точек на любой гиперплоскости, является гомеоморфным образом замкнутой части окружности [17]. В третьей части дается оценка минимального числа точек, принадлежащих одной гиперплоскости при вложении в п-мерное пространство сверху и снизу (теоремы 10 и 12). Оценки зависят от размерности пространства и комбинаторных характеристик графа. Доказано, что используемые при конструировании примеров вложения графов с помощью кривых Безье не нарушают общности: при любом вложении графа можно заменить образы ребер кривыми Безье так, что максимальное число точек, принадлежащих гиперплоскости, будет не увеличено (теорема 11).

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

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

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

3. Borsuk К. On the k-independent subsets of the Euclidean space and of the Hilbert space. Bull. Acad. Sci. Pol., 1957, V. 5 №4 P. 351-356

4. Богатый C.A. Цветная теорема Тверберг. Вести. Моск. Ун-та, сер. 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. Антонова Т.А., Облаков К.И. Специальные влоэюения графов в трехмерное пространство Вестн. Моск. Унта, сер. 1, математика, механика, 2008, №6, с. 26-31.

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

9. В.В. Прасолов, Элементы комбинаторной и дифференциальной топологии Москва, Издательство МЦНМО, 2004, стр.178

10. Р.Е. Conner, Е. Е. Floyd Fixed Point Free Involutions And Equivariant Maps Bull. Amer. Math. Soc., 1960, v.66, №6, p. 416-441

11. Semeon A. Bogatyi Finite-to-One Maps Topology and it's applications, 2008

12. Cieslik D. The Steiner Ratio of Metric Spaces. Preprint, Inst, of Math, and CS, Ernst-Moritz-Arndt Univ., Greifswald, Germany.

13. Cieslik D. Steiner Minimal Trees. London: Kluwer Academic Publishers, 1998

14. Ivanov A.O. Tuzhilin A. A. Minimal Networks. The Steiner Problem and Its Generalisation. N.W., Boca Raton, Florida: CRC Press, 1994.

15. Иванов A.O, Тужилин А.А. Единственность минимального дерева Штейнера для границы общего положения Матем. сб. 2006. 197, №10, стр. 55-90.

16. Дискретная математика и ее приложения: Сб. лекций/под редакцией О.Б. Лупанова. Изд-во Центра прикладных исследований при механико-математическом факультете МГУ, 2001, 3-25.

17. J.C. Mairhuber On Haar's theorem concerning Cheby-shev approximation problems having unique solutions Proc. Amer. Math. Soc. 1956 7 № pp. 609-615

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

19. R. P. Dilworth A Decomposition Theorem for Partially Ordered Sets. The Annals of Mathematics, Second Series 1960. v. 51 №1 pp. 161-166

20. В. Г. Болтянский, С. С. Рышков, Ю. А. Шашкин О k-регулярных вложениях и их применении к теории приближения функций. УМН 1960 т. 15 №6 стр. 125-132

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

22. В. Ю. Протасов Максимумы и минимумы в геометрии М. Издательство московского центра непрерывного образования, 2005

23. Математическая энциклопедия. М.: Советская энциклопедия. И. М. Виноградов. 1977-1985.

24. Roman N. Karasev Tverberg's Transversal Conjecture and Analogues of Nonembeddability Theorems for Transversals Discrete & Computational Geometry v. 38 №3 pp. 513-525

25. Фокс А., Пратт M.Вычислительная геометрия — применение в проектировании и на производстве. М. Мир, 1982