Граф АполлонияНа английском существует два термина — Apollonian network и Apollonian gasket, оба термина на русский можно перевести как сеть Аполлония. Для второго термина есть статья «Сетка Аполлония». Для первого термина в данной статье используется название «Граф Аполлония»  — неориентированный граф, образованный рекурсивным процессом подразделения треугольника на три меньших треугольника. Графы Аполлония можно эквивалентно определить как планарные 3-деревья, как максимальные планарные хордальные графы, как однозначно 4-раскрашиваемые планарные графы или как графы блоковых многогранников. Графы названы именем Аполлония Пергского, изучавшего связанные построения упаковки кругов.

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

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

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

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

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

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

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

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

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

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

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

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

В экстремальной теории графов графы Аполлония — это в точности планарные графы с n вершинами, в которых число блоков достигает максимального значения , и планарные графы, в которых число треугольником максимально и равно . Поскольку каждый подграф планарного графа должен быть блоком, на этих графах достигается максимум числа подграфов (это число равно ). На этих же графах достигается максимальное число клик любого типа (число клик равно )Для описания в терминах максимального числа треугольников в планарном графе смотрите статью Хакими и Шмейхеля . Алон и Саро цитируют этот результат и показывают описание в терминах изоморфизма классов блоков и числа блоков . Граница общего числа клик довольно просто следует из границы числа теугольних подграфов и подграфов K4 и приведена в явном виде у Вуда , который использовал графы Аполлония в качестве примера, показывающего строгость границы. Обобщение этих границ для непланарных поверхностей смотрите статью Дуймовича, Фиявжа, Жоре и Вуда .

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

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

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

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

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

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

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