Меню

Главная
Случайная статья
Настройки
Граф Аполлония
Материал из https://ru.wikipedia.org

Граф Аполлония[1] — неориентированный граф, образованный рекурсивным процессом подразделения треугольника на три меньших треугольника. Графы Аполлония можно эквивалентно определить как планарные 3-деревья, как максимальные планарные хордальные графы, как однозначно 4-раскрашиваемые планарные графы или как графы блоковых многогранников. Графы названы именем Аполлония Пергского, изучавшего связанные построения упаковки кругов.

Содержание

Определение

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

Примеры

Полные графы с тремя и четырьмя вершинами, K3 и

Граф Голднера — Харари является графом Аполлония, а также наименьшим негамильтоновым максимальным планарным графом[2]. Другой, более сложный граф Аполлония, использовал Нишизеки[3] как пример 1-жёсткого негамильтонова максимального планарного графа.

Теоретические свойства

Поскольку графы Аполлония определяются рекурсивным подразделением треугольников, они имеют другие математические описания. Графы являются хордальными максимальными планарными графами, хордальными полиэдральными графами и планарными 3-деревьями. Графы являются однозначно 4-раскрашиваемыми планарными графами и планарными графами с уникальной декомпозицией в лес Шнайдера, состоящий из трёх деревьев. Графы являются максимальными планарными графами с древесной шириной три, классом графов, которые можно описать их запрещёнными графами или их сведением путём Y- преобразований. Графы являются максимальными планарными графами с вырожденностью три. Графы являются также планарными графами с данным числом вершин, которые имеют наибольшее возможное число треугольников, наибольшее возможное число тетраэдральных подграфов, наибольшее возможное число клик и наибольшее возможное число частей после разложения на отдельные треугольники.

Хордальность

Графы Аполлония являются примерами максимальными планарными графами, в которые нельзя добавить ребро без нарушения планарности, или, эквивалентно, графами, которые могут быть нарисованы на плоскости так, что любая грань (включая внешнюю грань) является треугольником. Графы являются также хордальными графами, в которых каждый цикл из четырёх или более вершин имеет диагональное ребро, соединяющее две вершины цикла, не являющиеся последовательными в цикле, а порядок, в котором вершины добавляются в процессе построения графа Аполлония, является порядком исключения в хордальном графе. Это свойство даёт альтернативное описание графов Аполлония — это в точности хордальные максимальные планарные графы или, эквивалентно, хордальные полиэдральные графы[4].

В графе Аполлония любая максимальная клика — это полный граф с четырьмя вершинами, образованный выбором любой вершины и трёх ближайших соседей. Любой минимальный кликовый сепаратор (клика, удаление которой разбивает граф на два несвязных графа) — это один из разделённых треугольников. Хордальный граф, в котором все максимальные клики и все минимальные кликовые сепараторы имеют один и тот же размер, является k-деревом, а графы Аполлония являются примерами 3-деревьев. Не все 3-деревья планарны, но планарные 3-деревья — это в точности графы Аполлония.

Единственность раскраски

Любой граф Аполлония имеет единственную 4-цветную раскраску. Поскольку граф планарен, из теоремы о четырёх красках следует, что граф имеет раскраску четырьмя цветами, но поскольку цвета начального треугольника фиксированы, имеется единственная возможность выбора цвета для новой вершины, так что с точностью до перестановки цветов раскраска графа будет единственной. Труднее показать, но это также верно, что любой планарный граф с единственной раскраской является графом Аполлония. Таким образом, граф Аполлония может быть охарактеризован как планарный граф с единственной 4-цветной раскраской[5]. Графы Аполлония дают примеры планарных графов, имеющих минимальное число k-раскрасок для k > 4[6]

Также графы Аполлония — это в точности максимальные планарные графы, которые (если фиксировать внешнюю грань) имеют единственный лес Шнайдера, разбиение рёбер графа на три дерева с корнями в вершинах внешней грани[7][8].

Древесная ширина

Графы Аполлония не образуют семейство графов, замкнутого относительно операции взятия миноров графа, так как при удалении рёбер, но не вершин, получим граф, не являющийся графом Аполлония. Тем не менее, семейство планарных частичных 3-деревьев, подграфов графов Аполлония, является минорно замкнутым семейством. Таким образом, согласно теореме Робертсона — Сеймура, они могут быть охарактеризованы конечным числом запрещённых миноров. Минимальные запрещённые миноры для планарных частичных 3-деревьев — это четыре минимальных графа для планарных графов и частичных 3-деревьев: полный граф

Преобразование Y-, заменяющее вершину степени три на треугольник, соединяющий соседей, достаточно (вместе с операцией удаления кратных рёбер) для сведения графа Аполлония к единственному треугольнику. Планарные графы, которые могут быть сведены к единственному ребру с помощью преобразования Y-, удаления кратных рёбер, удаления вершин степени 1 и заменой вершины степени 2 вместе с рёбрами на одно ребро, это в точности планарные частичные 3-деревья. Двойственные графы планарных частичных 3-деревьев образуют другое замкнутое относительно взятия миноров семейство графов, которое является в точности теми графами, которые можно свести к единственному ребру с помощью преобразования -Y, удаления кратных рёбер, удаления вершин степени 1, и избавления от вершин степени 2[10].

Вырожденность

В любом подграфе графа Аполлония последняя добавленная вершина имеет степень три, так что графы Аполлония имеют вырожденность три. Порядок, в котором вершины добавляются при создании графа, таким образом, являются порядком вырождения и графы Аполлония совпадают с 3-вырожденными максимальными планарными графами.

Экстремальность

Другое свойство, характеризующее графы Аполлония, связано со связностью. Любой максимальный планарный граф может быть разложен на вершинно 4-связные максимальные планарные подграфы путём разделения вдоль треугольников (не являющихся гранями графа) — если имеется треугольник, не являющийся гранью, можно образовать два меньших максимальных планарных графа, один состоит из части, находящейся внутри треугольника, другой состоит из внешней по отношению к треугольнику части. Максимальные планарные графы без разделяющих треугольников, которые образуются многократным разбиением такого рода, иногда называют блоками, хотя то же имя используется и для компонент двусвязности графа, который сам по себе двусвязным не является. Граф Аполлония — это максимальный планарный граф, в котором все блоки изоморфны полному графу

В экстремальной теории графов графы Аполлония — это в точности планарные графы с n вершинами, в которых число блоков достигает максимального значения

Геометрические реализации

Построение из упаковки кругов

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

Если процесс построения сетки Аполлония остановить, нарисовав лишь конечное число окружностей, то граф, имеющий вершину для каждой окружности и ребро для любых двух касающихся окружностей, и есть граф Аполлония[12]. Существование множества касающихся окружностей, касания которых представляют граф Аполлония, определяется теоремой Кёбе — Андреева — Тёрстона, которая утверждает, что любой планарный граф может быть представлен касающимися окружностями[13].

Многогранники

Графы Аполлония — это планарные вершинно 3-связные графы, и потому, по теореме Штайница, могут быть всегда представлены как графы выпуклых многогранников. Выпуклый многогранник, представляющий граф Аполлония — это 3-мерный блоковый многогранник. Такие многогранники могут быть получены из тетраэдра многократным приклеиванием дополнительных тетраэдров (по одному) к треугольным граням многогранника. Таким образом, графы Аполлония могут быть определены как графы блоковых 3-мерных многогранников[14]. Можно найти представление любого графа Аполлония как выпуклого 3-мерного многогранника, в котором все координаты являются целыми числами полиномиальной величины, что лучше, чем для других планарных графов[15].

Треугольные сетки

Рекурсивное разделение треугольников на три меньших треугольников исследовали Элкок, Гаргантини и Волш в качестве техники сегментации изображения в компьютерном зрении[16]. В этом контексте они называют такое разделение тройным неравносторонним разложением на треугольники. Они заметили, что при добавлении каждой новой вершины в центроид в треугольник треугольники триангуляции будут иметь одинаковые площади, хотя они и не одинаковой формы. Более обще, графы Аполлония можно нарисовать на плоскости с любой заранее заданной площадью каждой грани. Если площади заданы как рациональные числа, такими будут и координаты вершин[17].

Можно провести процесс деления треугольников при построении графа Аполлония таким образом, что на каждом шаге длины рёбер будут рациональными числами. Неизвестно, можно ли нарисовать любой планарный граф с теми же свойствами[18]. За полиномиальное время можно найти рисунок планарного 3-дерева с целыми координатами с минимальной площадью ограничивающего прямоугольника и проверить, можно ли нарисовать заданное планарное 3-дерево с вершинами на заданном множестве точек[19]

Свойства и приложения

Графы без совершенного паросочетания

Пламмер[20] использовал графы Аполлония для построения бесконечного семейства максимальных планарных графов с чётным числом вершин, не имеющих совершенного паросочетания. Графы Пламмера строятся в два этапа. На первом этапе, начиная с треугольника

Хотя сами по себе графы Аполлония не могут иметь совершенных паросочетаний, двойственные графам Аполлония графы являются 3-регулярными графами без разрезающих рёбер, так что по теореме Петерсена[21] они обязательно имеют по меньшей мере одно совершенное паросочетание. Для графов Аполлония известно даже больше — двойственные графам Аполлония графы имеют экспоненциально большое число совершенных паросочетаний[22]. Ласло Ловас и Майкл Д. Пламмер высказали гипотезу, что аналогичная экспоненциальная нижняя граница должна существовать для всех 3-регулярных графов без разрезающих рёбер, что было позднее подтверждено.

Степенной закон графов

Ж. Андраде, Г. Геррманн, Р. Андраде и Л. де Сильва[12] изучали степенные законы последовательностей степеней специальных видов графов этого вида, образованных делением всех треугольников одинаковое число раз. Они использовали эти графы для моделирования заполнения пространства частями различного размера. Основываясь на их работе, другие авторы предложили случайные графы Аполлония, получаемые случайным выбором грани для деления, и показали, что для этих графов выполняется степенной закон в распределении степеней вершин[23], а также показали, что эти графы имеют малые расстояния[24][25]. Фриз и Тсоуракакис анализировали наибольшие степени вершин и собственные значения случайных графов Аполлония[26]. Ж. Андраде, Г. Геррманн, Р. Андраде и Л. де Сильва заметили также, что их графы удовлетворяют эффекту «мир тесен» (теория шести рукопожатий), то есть что все вершины находятся на близком расстоянии друг от друга. Основываясь на численных экспериментах, они оценили среднее расстояние между случайно выбранными парами вершин в графе с n вершинами как пропорциональное (log n)3/4, но дальнейшие исследования показали, что среднее расстояние на самом деле пропорционально log n[27][28].

Распределение углов

Батлер и Грэм[29] заметили, что если каждая новая вершина помещается в точку пересечения биссектрис треугольника, то множество троек углов треугольников в подразделении, если их интерпретировать как барицентрические координаты точек в правильном треугольнике, в пределе образует треугольник Серпинского при росте уровня подразделения.

Гамильтоновость

Такео[30] ошибочно утверждал, что все графы Аполлония имеют гамильтоновы циклы, однако граф Голднера–Харари служит контрпримером. Если граф Аполлония имеет жёсткость, большую единицы (что означает, что при удалении любого числа вершин из графа в графе остаётся связных компонент меньше, чем число удалённых вершин), он обязательно гамильтонов, но существуют негамильтоновы графы Аполлония, если жёсткость равна единице[31]

Перечисление

Задачу комбинаторики подсчёта аполлониевых триангуляций изучал Такео[30]. Он показал, что для числа триангуляций существует простая производящая функция f(x), описываемая равенством f(x) = 1 + x(f(x))3. В этой производящей функции член степени n содержит число графов Аполлония с внешним треугольником и n + 3 вершинами. Число графов Аполлония (с внешним треугольником) и 3, 4, 5, … вершинами:
1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, … (последовательность A001764 в OEIS).


Эта же последовательность задаёт число троичных деревьев[англ.] и число разбиений выпуклого многоугольника на многоугольники с нечётным числом сторон. Например, существует 12 графов Аполлония с 6 вершинами — три образуются разбиением внешнего треугольника с последующим разбиением двух из полученных треугольников и ещё девять образуются разбиением внешнего треугольника и разбиением одного из полученных треугольников с последующим разбиением одного из маленьких треугольников.

История

У Биркгофа[32] есть ранняя статья, в которой используется двойственная форма графов Аполлония, планарные карты, образованные многократным помещением новых областей в вершинах более простых карт, в качестве примера класса планарных графов с малым числом цветов.

Геометрические структуры, близкие графам Аполлония, изучались в комбинаторике многогранников с начала 1960-х годов, когда их использовал Грюнбаум[33] для описания графов, которые можно реализовать в многогранниках единственным образом по размерности и с точки зрения комбинаторики. Их использовали также Мун и Мозер[34] для поиска симплициальных многогранников без длинных путей. В теории графов тесная связь между планарностью и древесной шириной прослеживается к статье Робертсона и Сеймура 1984 года[35], которые показали, что замкнутое относительно взятия миноров семейство графов либо имеет ограниченную древесную ширину, либо содержит все планарные графы. Планарные 3-деревья, как класс графов, рассматривали Хакими и Шмайхель[36], Алон и Каро[37], Патил[38] и многие другие авторы вслед за ними.

Название «граф Аполлония» было предложено в статье Ж. Андраде, Г. Геррманна, Р. Андраде и Л. де Сильва[12] для графов, в которых уровень деления треугольников однороден. Геометрически эти графы соответствуют блоковым многогранникам (многогранникам Кли)[33][39]. Другие авторы использовали термин для более широкого класса графов, планарных 3-деревьев, с целью обобщения модели на случайные графы Аполлония[24][25]. Трианкуляризация, полученная таким образом, была также названа «блоковой триангуляризацией»[37][40][41][7][27][8][22].

См. также

Примечания
  1. На английском существует два термина — Apollonian network и Apollonian gasket, оба термина на русский можно перевести как сеть Аполлония. Для второго термина есть статья «Сетка Аполлония». Для первого термина в данной статье используется название «Граф Аполлония»
  2. Этот граф назван именами авторов статьи(Goldner, Harary 1975). Однако он и раньше появлялся в литературе, например у Грюнбаума (Grnbaum 1967), стр. 357.
  3. Nishizeki, 1980.
  4. Эквивалентность планарных 3-деревьев и хордальных максимальных планарных графов высказал без доказательства Патил (Patil 1986). Для доказательства смотри статью Маркензона, Джустела и Пакиорника (Markenzon, Justel, Paciornik 2006). Для более общего описания хордальных планарных графов и эффективного алгоритма их распознавания смотрите статью Кумара и Мадхавана (Kumar, Madhavan 1989). Что любой хордальный полиэдральный граф является максимальным планарным, заметил Герлах (Gerlach 2004).
  5. Fowler, 1998.
  6. Факт, что графы Аполлония минимизируют число раскрасок с числом цветов большим четырёх был показан Биркгофом в двойственной форме раскраски карт (Birkhoff 1930).
  7. 1 2 Felsner, Zickfeld, 2008.
  8. 1 2 Bernardi, Bonichon, 2009.
  9. Два запрещённых минора для планарных графов даёт теорема Вагнера. О запрещённых минорах частичных 3-деревьев (которые включают также непланарный граф Вагнера) смотрите статьи Арнборга, Проскуровски, Корниела (Arnborg, Proskurowski, Corniel 1986) и Бодлаендера (Bodlaender 1998). Прямое доказательство того, что граф октаэдра и пятиугольной призмы являются единственными двумя планарными запрещёнными минорами, смотрите статьи Даи, Сато (Dai, Sato 1990) и Эль-Маллаха, Колбоурна (El-Mallah, Colbourn 1990).
  10. Политоф (Politof 1983) ввёл сводимые -Y планарные графы и описал их в терминах запрещённых гомеоморфных подграфов. Двойственность между -Y и Y- сводимыми графами, описание обоих классов запрещёнными минорами и связь с планарными частичными 3-деревьями взяты из статьи Эль-Маллаха и Колбоурна (El-Mallah, Colbourn 1990).
  11. Для описания в терминах максимального числа треугольников в планарном графе смотрите статью Хакими и Шмейхеля (Hakimi, Schmeichel 1979). Алон и Саро цитируют этот результат и показывают описание в терминах изоморфизма классов блоков и числа блоков (Alon, Caro 1984). Граница общего числа клик довольно просто следует из границы числа теугольних подграфов и подграфов K4 и приведена в явном виде у Вуда (Wood 2007), который использовал графы Аполлония в качестве примера, показывающего строгость границы. Обобщение этих границ для непланарных поверхностей смотрите статью Дуймовича, Фиявжа, Жоре и Вуда (Dujmovi, Fijav, Joret, Wood 2009).
  12. 1 2 3 Andrade, Herrmann, Andrade, da Silva, 2005.
  13. Thurston, 1978–1981.
  14. См., например, статью Белова, Де Лоэра и Рихтер-Геберта (Below, De Loera, Richter-Gebert 2000)
  15. Demaine, Schulz, 2011.
  16. Elcock, Gargantini, Walsh, 1987.
  17. Biedl, Ruiz Velzquez, 2010.
  18. Для деления треугольника с рациональными длинами сторон так, чтобы полученные треугольники тоже имели рациональные стороны, смотри статью Альмеринга (Almering 1963). Относительно общей проблемы поиска планарного графа с рациональными длинами сторон смотри статью Гилена, Гуо и Маккиннона (Geelen, Guo, McKinnon 2008).
  19. Для рисования с целыми координатами смотри стать. Мондала, Нишата, Рахмана и Алама (Mondal, Nishat, Rahman, Alam 2010). Для рисования на заданном множестве вершин смотри статью Нишата, Мондала и Рахмана (Nishat, Mondal, Rahman 2011).
  20. Plummer, 1992.
  21. Petersen, 1891.
  22. 1 2 Jimnez, Kiwi, 2010.
  23. Tsourakakis, 2011.
  24. 1 2 Zhou, Yan, Zhou, Fu, Wang, 2004.
  25. 1 2 Zhou, Yan, Wang, 2005.
  26. Frieze, Tsourakakis, 2011.
  27. 1 2 Albenque, Marckert, 2008.
  28. Zhang, Chen, Zhou, Fang, 2008.
  29. Butler, Graham, 2010.
  30. 1 2 Takeo, 1960.
  31. См. статью Нишизеки (Nishizeki 1980) с примером негамильтонов графа, имеющего жёсткость 1 и статью Бёме, Харанта и Ткача (Bhme, Harant, Tk 1999) с доказательством, что графы Аполлония с большей жёсткостью являются гамильтоновыми. См. статью Герлаха (Gerlach 2004) с обобщением этого результата на более широкий класс планарных графов.
  32. Birkhoff, 1930.
  33. 1 2 Grnbaum, 1963.
  34. Moon, Moser, 1963.
  35. Robertson, Seymour, 1984.
  36. Hakimi, Schmeichel, 1979.
  37. 1 2 Alon, Caro, 1984.
  38. Patil, 1986.
  39. Grnbaum, 1967.
  40. Zickfeld, Ziegler, 2006.
  41. Badent, Binucci, Di Giacomo, Didimo, 2007.


Литература

Ссылки
Downgrade Counter