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

Работа посвящена минимальным вложениям графов в евклидово пространство.

В этой работе рассматриваются вложения, являющиеся минимальными по трем различным характеристикам. Во-первых, это вложения, при которых минимальное число точек образа графа лежит на одной прямой (раздел 1). Во-вторых, рассматриваются сети Штейнера — минимальные по длине связные континуумы, затягивающие заданное конечное множество точек на плоскости (разделы 2 и 3). В-третих, рассматриваются вложения графов в евклидово пространство, при которых наименьшее число точек образа принадлежит гиперплоскости (раздел 4).

Различные вложения графов рассматривались в математике в течение последнего полувека. Классическими стали теоремы о вложении произвольного графа в трехмерное пространство, о минимальности и полноте семейства графов Ку-ратовского с точки зрения невложимости в плоскость.

В задаче суперпозиции возникают базисные вложения [1]. К. Борсуком было введено понятие /¿—регулярных вложений компактов [3]. Эти вложения возникают в задачах интерполяции и аппроксимации. Болтянский, Рышков и Шаш-кин исследовали^{-регулярные} вложения для случая полиэдров [20]. Также ими занимались С. А. Богатый и В. М. Вылов [2], [21].

Вложения, рассматриваемые в первой части, являются обобщением^{-регулярных} вложений. Богатый [4] доказал, что всякое отображение /: X —одномерного компакта в К3 сколь угодно малым изменением может быть превращено в такое вложение fe: X —" Ж3, что на всякой прямой в К3 будет лежать не более четырех точек образа ¡-£{Х) компакта X. Укажем, что существование таких &bdquo-экономичных вложений" доказал также Гудселл [5]. Оказывается, что число 4 не может быть уменьшено не только на уровне теоремы плотности &bdquo-экономичных" отображений, но и на уровне теоремы существования. Именно, Живалевич доказал, что для всякого вложения К^ а в Е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).

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.