Jump to content

Аполлоническая сеть

Аполлоническая сеть
Граф Гольднера – Харари , негамильтонова аполлонова сеть.

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

Определение

[ редактировать ]

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

с Полные графы тремя и четырьмя вершинами K 3 и K 4 являются аполлоновыми сетями. K 3 формируется путем начала с треугольника без выполнения каких-либо делений, а K 4 формируется путем выполнения одного деления перед остановкой.

Граф Гольднера – Харари — это аполлонова сеть, образующая наименьший негамильтонов максимальный планарный граф. [1] Другая, более сложная аполлонова сеть была использована Нишизеки (1980), чтобы предоставить пример 1-жесткого негамильтонова максимального планарного графа.

Теоретико-графовые характеристики

[ редактировать ]

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

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

[ редактировать ]

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

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

Уникальная возможность окрашивания

[ редактировать ]

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

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

Ширина дерева

[ редактировать ]

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

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

Вырождение

[ редактировать ]

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

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

[ редактировать ]

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

В экстремальной теории графов аполлоновы сети также представляют собой планарные графы с n - вершинами, в которых количество блоков достигает максимума, n - 3 , и плоские графы, в которых количество треугольников достигает максимума, 3 n - 8 . Поскольку каждый подграф K 4 планарного графа должен быть блоком, это также планарные графы, в которых количество подграфов K 4 достигает максимума, n − 3 , и графы, в которых количество клик любого типа достигает своего максимума. максимум, 8 n − 16 . [8]

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

[ редактировать ]

Конструкция из круглых насадок

[ редактировать ]
Пример аполлонической прокладки
Построение аполлоновой сети из упаковки кругов.

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

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

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

[ редактировать ]
Триакис тетраэдр , многогранная реализация 8-вершинной аполлоновой сети.

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

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

[ редактировать ]

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

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

Свойства и применение

[ редактировать ]

Графики без совпадений

[ редактировать ]

Пламмер (1992) использовал аполлоновы сети для построения бесконечного семейства максимальных планарных графов с четным числом вершин, но без идеального сопоставления . Графики Пламмера формируются в два этапа. На первом этапе, начиная с треугольника abc , многократно разбивается треугольная грань подразделения, которое содержит ребро bc : в результате получается граф, состоящий из пути от a до конечной вершины подразделения вместе с ребром от каждой вершины пути до каждый из b и c . На втором этапе каждая из треугольных граней полученного плоского графа подразделяется еще раз. Если путь от a до конечной вершины подразделения первого этапа имеет четную длину, то количество вершин в общем графе также четное. Однако примерно 2/3 вершин — это те, которые вставляются на втором этапе; они образуют независимый набор и не могут быть сопоставлены друг с другом, а вне независимого набора недостаточно вершин, чтобы найти совпадения для всех из них.

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

Графики степенного закона

[ редактировать ]

Андраде и др. (2005) изучали степенные законы в последовательностях степеней частного случая сетей этого типа, образованных разделением всех треугольников одинаковое количество раз. Они использовали эти сети для моделирования упаковки пространства частицами разных размеров. На основе своей работы другие авторы представили случайные аполлоновы сети, сформированные путем многократного выбора случайного лица для разделения, и показали, что они также подчиняются степенным законам в распределении степеней. [17] и имеют небольшие средние расстояния. [18] Алан М. Фриз и Харалампос Э. Цуракакис проанализировали высшие степени и собственные значения случайных аполлонических сетей. [19] Андраде и др. также заметил, что их сети удовлетворяют эффекту маленького мира , когда все вершины находятся на небольшом расстоянии друг от друга. Основываясь на числовых данных, они оценили среднее расстояние между случайно выбранными парами вершин в n -вершинной сети этого типа как пропорциональное (log n ) 3/4 , но позже исследователи показали, что среднее расстояние на самом деле пропорционально log n . [20]

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

[ редактировать ]

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

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

[ редактировать ]

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

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

[ редактировать ]

Комбинаторная задача подсчета аполлоновых триангуляций была изучена Такео (1960) , который показал, что они имеют простую производящую функцию 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-вершинных аполлонических сетей: три образованы путем разделения внешнего треугольника один раз, а затем разделения двух полученных треугольников,и девять, образованные путем разделения внешнего треугольника один раз, разделения одного из его треугольников, а затем разделения одного из получившихся меньших треугольников.

Биркгоф (1930) — ранняя статья, в которой используется двойная форма аполлоновых сетей, плоские карты, образованные путем многократного размещения новых регионов в вершинах более простых карт, как класс примеров плоских карт с небольшим количеством раскрасок.

Геометрические структуры, тесно связанные с аполлоновыми сетями, изучаются в полиэдральной комбинаторике , по крайней мере, с начала 1960-х годов, когда они использовались Грюнбаумом (1963) для описания графов, которые могут быть реализованы как граф многогранника только одним способом, без размерности или комбинаторные неоднозначности, а также Мун и Мозер (1963) для поиска симплициальных многогранников без длинных путей. В теории графов тесная связь между планарностью и шириной дерева восходит к Робертсону и Сеймуру (1984) , которые показали, что каждое малозамкнутое семейство графов либо имеет ограниченную древовидную ширину, либо содержит все плоские графы. Плоские 3-деревья как класс графов подробно рассматривались Хакими и Шмейхелем (1979) , Алоном и Каро (1984) , Патилом (1986) и многими авторами после них.

Название «аполлоническая сеть» было дано Андраде и др. (2005) к изученным ими сетям, в которых уровень подразделения треугольников одинаков по всей сети; эти сети геометрически соответствуют типу сложенного многогранника, называемому Клитопом . [22] Другие авторы в более широком смысле применили то же название к плоским трехмерным деревьям в своей работе, обобщающей модель Андраде и др. случайным аполлоновым сетям. [18] Триангуляции, созданные таким образом, также получили название «сложные триангуляции». [23] или «стек-триангуляции». [24]

См. также

[ редактировать ]

Примечания

[ редактировать ]
  1. ^ Этот график назван в честь работы Голднера и Харари (1975) ; однако в литературе оно появляется раньше, например, у Грюнбаума (1967) , с. 357.
  2. ^ Эквивалентность плоских 3-деревьев и хордальных максимальных планарных графов была без доказательства установлена ​​Патилом (1986) . Доказательство см. в Markenzon, Justel & Paciornik (2006) . Более общую характеристику хордальных плоских графов и эффективный алгоритм распознавания этих графов см. в Kumar & Madhavan (1989) . Наблюдение о том, что каждый хордальный многогранный граф является максимально планарным, было явно сформулировано Герлахом (2004) .
  3. ^ Фаулер (1998) .
  4. ^ Тот факт, что аполлоновы сети минимизируют количество раскрасок с более чем четырьмя цветами, был показан в двойственной форме для раскрасок карт Биркгофом (1930) .
  5. ^ Фельснер и Зикфельд (2008) ; Бернарди и Бонихон (2009) .
  6. ^ Два запрещенных минора для плоских графов определяются теоремой Вагнера . О запрещенных минорах для частичных трехдеревьев (которые включают также непланарный граф Вагнера ) см. Arnborg, Proskurowski & Corniel (1986) и Bodlaender (1998) . Прямые доказательства того, что октаэдрический граф и граф пятиугольной призмы являются единственными двумя плоскими запрещенными минорами, см. в Dai & Sato (1990) и El-Mallah & Colbourn (1990) .
  7. ^ Политоф (1983) ввел приводимые Δ-Y плоские графы и охарактеризовал их в терминах запрещенных гомеоморфных подграфов. Двойственность между приводимыми графами Δ-Y и Y-Δ, запрещенные второстепенные характеристики обоих классов и связь с плоскими частичными трехмерными деревьями — все это из El-Mallah & Colbourn (1990) .
  8. ^ Характеризацию с точки зрения максимального количества треугольников в плоском графе см. в Hakimi & Schmeichel (1979) . Алон и Каро (1984) цитируют этот результат и дают характеристики с точки зрения классов изоморфизма блоков и количества блоков. Ограничение общего числа клик легко следует из границ треугольников и K4 подграфов , а также явно сформулировано Вудом (2007) , который приводит аполлонову сеть в качестве примера, показывающего, что эта граница точна. Обобщения этих границ на неплоские поверхности см. в Dujmović et al. (2009) .
  9. ^ Андраде и др. (2005) .
  10. ^ Терстон (1978–1981) .
  11. ^ См., например, Ниже, Де Лоера и Рихтер-Геберт (2000) .
  12. ^ Демейн и Шульц (2011) .
  13. ^ Бидл и Руис Веласкес (2010) .
  14. ^ О разделении треугольника с рациональными длинами сторон так, чтобы меньшие треугольники также имели рациональные длины сторон, см. Almering (1963) . О ходе решения общей проблемы поиска плоских чертежей с рациональной длиной ребер см. в Geelen, Guo & McKinnon (2008) .
  15. ^ Рисунки с целочисленными координатами см. Mondal et al. (2010) , а рисунки заданного набора вершин см. в Nishat, Mondal & Rahman (2011) .
  16. ^ Хименес и Киви (2010) .
  17. ^ Цуракакис (2011)
  18. ^ Jump up to: а б Чжоу и др. (2004) ; Чжоу, Ян и Ван (2005) .
  19. ^ Фриз и Цуракакис (2011)
  20. ^ Альбенке и Маркерт (2008) ; Чжан и др. (2008) .
  21. ^ См . Нишизеки (1980) для 1-жесткого негамильтонового примера, Бёме, Харанта и Ткача (1999) для доказательства того, что аполлоновы сети с большей жесткостью являются гамильтоновыми, и Герлаха (2004) для распространения этого результата на более широкий класс плоских графов.
  22. ^ Грюнбаум (1963) ; Грюнбаум (1967) .
  23. ^ Алон и Каро (1984) ; Зикфельд и Зиглер (2006) ; Бадент и др. (2007) ; Фельснер и Зикфельд (2008) .
  24. ^ Альбенке и Маркерт (2008) ; Бернарди и Бонихон (2009) ; Хименес и Киви (2010) .
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 4d347a4be8c59d46ced8f6630b7161c2__1699370100
URL1:https://arc.ask3.ru/arc/aa/4d/c2/4d347a4be8c59d46ced8f6630b7161c2.html
Заголовок, (Title) документа по адресу, URL1:
Apollonian network - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)