Минимальные вложения графов тема автореферата и диссертации по математике, 01.01.04 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В. ЛОМОНОСОВА

На правах рукописи 00504ВЧ»*

Облаков Константин Игоревич МИНИМАЛЬНЫЕ ВЛОЖЕНИЯ ГРАФОВ 01.01.04 — геометрия и топология

лГ .л

!

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 о ЯНВ 2013

Москва 2012

005048199

Работа выполнена на кафедре общей топологии и геометрии Механико-математического факультета Московского государственного университета имени М. В. Ломоносова.

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук, профессор Богатый Семеон Антонович

Агеев Сергей Михайлович доктор физико-математических наук, профессор (Беларусский университет, кафедра геометрии, топологии и методики преподавания математики)

Редкозубое Вадим Виталиевич кандидат физико-математических наук ассистент (Московский физико-технический институт)

ГБОУ ВПО „Московский городской педагогический университет".

Защита диссертации состоится 18 января 2013 г. в 16 ч. 45 м. на заседании диссертационного совета Д. 501.001.84 при Московском государственном университете имени М.В. Ломоносова по адресу 119991, Москва, ГСП-1, Ленинские горы, д.1, МГУ, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан 18 декабря 2012 года.

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ доктор физико-математических наук, профессор

/Ы

Иванов Александр Олегович

Общая характеристика работы

Актуальность темы.

Работа представляет собой исследование в области геометрии и топологии Евклидовых пространств и теории графов, вложениями графов в евклидово пространство.

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

В задаче суперпозиции возникают базисные вложения1. К. Борсуком было введено понятие ¿-регулярных вложений компактов2. Эти вложения возникают в задачах интерполяции и аппроксимации. Болтянский, Рышков и Шашкин исследовали fc-регулярные вложения для случая полиэдров3. Также ими занимались С.А. Богатый и В.М. Вылов4>5.

Вложения, рассматриваемые в первой главе, являются обобщением к-регулярных вложений. Богатый6 доказал, что всякое отображение /: X -»

R3 одномерного компакта в R3 сколь угодно малым изменением может быть превращено в такое вложение /£: X —> R3, что на всякой прямой в Ж3 будет лежать не более четырех точек образа fe(X) компакта X. Укажем, что существование таких „экономичных вложений" доказал также Гудселл7.

Оказывается, что число 4 не может быть уменьшено не только на уровне теоремы плотности „экономичных" отображений, но и на уровне теоремы существования. Именно, Живалевич8 доказал, что для всякого вложения Kßß в R3 существует прямая, пересекающая граф не менее чем по четырем точкам.

'Р. Ostrand Dimension of metric spaces and Hilbert's problem 13. Bull. Amer. Math. Soc, 1965, v. 7, pp. 61^-622.

2K. Borsuk On the k-independent subsets of the Euclidean space and of the Hilbert space. Bull. Acad. Sei. Pol., 1957, v. 5, №4, pp. 351-356

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

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

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

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

7T.H. Goodsell Strong general position and Menger curses Topol. Appl., 2002, v. 120, №1-2, pp. 47-55.

SR.T. 2ivaljevii The Tverberg- Vrecica problem and the combinatorial geometry on vector bundles. Israel

J. Math., 1999, v. Ill, pp. 53-76.

В первой главе изучается проблема существования „экономичных" вложений в R3, и, в частности, усилен результат Живалевича.

Вторая и третья главы посвящены так называемой проблеме Штейне-ра — задаче нахождения минимальной по длине сети (одномерного связного континуума), затягивающей данное конечное множество точек на плоскости9'10. Эта задача имеет широкое практическое применение: транспортная задача, разводка микросхем, построение филогенетических деревьев. Оказалось, что удобно рассматривать не только кратчайшие (т.е. глобально минимальные), но и локально-минимальные сети. Локально-минимальных сетей для данного набора точек может быть несколько. Возможно даже существование нескольких глобально минимальных деревьев. Если они не сонаправлены в граничных вершинах, то малым шевелением граничных вершин можно добиться того, что только одно из деревьев останется глобально минимальным. А.О. Иванов и A.A. Тужилин доказали11, что множество таких расположений точек, для которых не существует двух глобально минимальных деревьев открыто и всюду плотно в множестве всех расположений. Они опирались на утверждение, гласящее что не существует двух глобально минимальных деревьев, сонаправленных в вершинах. В данной работе получено обобщение этого утверждения на случай локально минимальных деревьев.

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

Цель работы

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

9D. Cieslik The Steiner Ratio of Metrie Spaces. Preprint, Inst, of Math, and CS, Ernst-Moritz-Arndt Univ., Greifewald, Germany.

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

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

13J.C. Mairhuber On Soar's theorem concerning Chebyshev approximation problems having unique solutions Proc. Amer. Math. Soc. 1956, 7, №4, pp. 609-615

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

Научная новизна

Результаты диссертации являются новыми, за исключением открытого независимо с Р.Н. Карасевым результата о вложениях несвязных графов в трехмерное Евклидово пространство (глава 1). Укажем наиболее важные результаты:

• Описано семейство графов, каждое вложение которых в трехмерное Евклидово пространство содержит четыре точки образа, принадлежащие одной прямой, и доказана их минимальность.

• Доказано, что на плоскости не существует двух локально минимальных сетей Штейнера для данного множества точек, «»направленных в вершинах;

• Доказано, что на цилиндре с плоской метрикой и конусе с углом развертки, кратным 60 градусам, также не существует двух сетей Штейнера, сонаправленных в вершинах.

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

Методы исследования

В работе применялись методы дифференциальной геометрии и топологии, общей теоретико-множественной топологии.

Теоретическая и практическая ценность

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

Аппробация диссертации

Результаты диссертации неоднократно докладывались на научно-исследовательских семинарах.

1. научно-исследовательский семинар по общей топологии им. П. С. Александрова (семинар кафедры общей топологии и геометрии механико-математического факультета МГУ) неоднократно (2007, 2008, 2009, 2011)

2. XV международная конференция студентов, аспирантов и молодых ученых "Ломоносов-2008"

3. Семинар кафедры дифференциальной геометрии и приложений. (2011)

4. Специальный семинар "Теория экстремальных сетей", (кафедра дифференциальной геометрии и приложений механико-математического факультета МГУ) (2007)

Публикации

По теме диссертации автором опубликовано 4 работы. Список приведен в конце автореферата [1-4].

Структура и объем работы

Диссертация изложена на 61 странице и состоит из введения, 4 глав и списка литературы,включающего 25 наименований.

Содержание работы

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

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

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

Теорема 1. Несвязное объединение графов Куратовского-Понтрягина (К$11 и Къ и Яз,з "Л" Яз)3 и АГ3,з) является минимальным не 5-вложимым графом.

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

Утверждение 1 (Антонова). Если граф вкладывается в плоскость с одним самопересечением типа ребро-ребро или ребро-вершина, то его можно 3-вложить в пространство.

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

Утверждение 2. Для двух непрерывных отображений ді, замкнутых компактных ориентируемых п-мерных многообразий Мі, М2 в касательное пространство сферы £(£>") имеет место равенство

ооіп(й, д2) = х(5") deg(pg1) <і сфдг),

гдер: Ь(вп) —> 5" — естественная проекция.

Вторая глава посвящена сетям Штейнера на плоскости.

Теорема 2. На плоскости не существует двух локально-минимальных деревьев с одним и тем же граничным множеством и сонаправленных в граничных вершинах.

Приведенное в этой главе доказательство по сути доказывает более сильную теорему:

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

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

В третьей главе результат второй главы распространен на некоторые многообразия с плоской метрикой.

Определение 2. Обозначим за К множество цилиндров или конусов с углом развертки кратным 60°, с заданной на них плоской метрикой. Будем говорить, что поверхность является К-поверхностью, если она принадлежит К.

Теорема 4. На К-поверхности не существует двух локально-минимальных деревьев с одним и тем же граничным множеством и сонаправлен-ных в граничных вершинах.

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

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

Четвертая глава посвящена верхней и нижней оценкам числа гипер-планарности графов.

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

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

Рассмотрим некоторую нумерацию вершин графа. Для данной нумерации вершин введем частичный порядок на ребрах: ребро, соединяющее вершины г'і и ¿2 „не больше" ребра между вершинами ^ и j2, когда выполняются одновременно четыре неравенства: < ¿2 ^ іі, г'і < ¿2 ^ 32- Каждой нумерации поставим в соответствие „число максимального сечения" — максимальное число несравнимых ребер. Оптимальной нумерацией назовем такую нумерацию вершин графа, при которой „число максимального сечения" минимально. Если таких нумераций несколько, будем считать оптимальной одну из них. Последовательность ребер в грат фе назовем „согласованным с нумерацией путем", если каждое следующее (по порядку прохождения) ребро „не больше" предыдущего. Такой „путь" может быть несвязен.

Числом ветвистости графа назовем минимальное такое число I, что граф можно полностью покрыть I „путями", согласованными с оптимальной нумерацией.

Теорема 8. При п > 2 любой граф можно вложить в п-мерное пространство так, что число гипєрпланарности образа будет не более чем пі, где І — число ветвистости.

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

Теорема 9. Для любого вложения /: С? —> К" графа 6? с конечным числом гипєрпланарности образа существует вложение /' этого графа, такое что:

• образы вершин графа при вложениях / и /' — одни и те же точки;

• образ каждого ребра под действием /' представляет собой полиномиальную кривую;

• на каждой гиперплоскости точек образа графа под действием /' не больше, чем под действием /.

Для получения нижней оценки также использовались комбинаторные свойства графа:

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

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

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

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

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

Теорема 10. Кратность одномерной проекции оценивает число гипер-планарности снизу.

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

Работы автора по теме диссертации

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

Автором диссертации получено доказательство 3-вложимости конфигураций г) и е) на "шапочке".

2) Облаков К.И. Невозможность существования различных сонаправ-ленных локально минимальных деревьев на плоскости. Вестн. Моск. Ун-та, сер. 1, математика, механика, 2009, №2, стр. 21-25.

3) Облаков К.И., ОблаковаТ.А. Специальные вложения некоторых несвязных графов в трехмерное пространство. Вестн. Моск. Ун-та, сер. 1, математика, механика, 2011, №2, стр. 54-56.

Все результаты, кроме утверждения 2, получены автором диссертации.

4) Облаков К.И., ОблаковаТ.А. Вложения графов в евклидово пространство, при которых число точек, принадлежащих гиперплоскости, минимально. Матем.сб., 201:10 (2012), 145-160

Автором получены верхняя и нижняя оценки числа гиперпланарности в общем случае.

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж ЮО экз. Заказ №

Введение.

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).

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