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

Визначення Граф Аполлонія можна отримати з трикутного графа, вкладеного в евклідову площину, шляхом неодноразового вибору трикутної грані вкладення, додання нової вершини в цю трикутну грань і з'єднання нової вершини з кожною вершиною грані. В результаті грань ділиться на три менші трикутники, які, у свою чергу, можна поділити в такий самий спосіб.

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

Граф Голднера — Харарі є графом Аполлонія, а також найменшим максимальним негамільтоновим планарним графомЦей граф названо іменами авторів статті . Однак він і раніше з'являвся в літературі, наприклад у Ґрюнбаума , стор. 357.. Інший, складніший граф Аполлонія, використав Нішизекі як приклад 1-жорсткого негамільтонового максимального планарного графа.

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

Хордальність Графи Аполлонія є прикладами максимальних планарних графів, у які не можна додати ребро без порушення планарності, або, еквівалентно, графами, які можна намалювати на площині так, що будь-яка грань (зокрема й зовнішня) є трикутником. Графи є також хордальними графами, в яких кожен цикл із чотирьох або більше вершин має діагональне ребро, що з'єднує дві вершини циклу, які не є послідовними в циклі, а порядок, у якому вершини додаються в процесі побудови графа Аполлонія, є порядком виключення в хордальному графі. Ця властивість дає альтернативний опис графів Аполлонія — це точно хордальні максимальні планарні графи або, еквівалентно, хордальні многогранні графиЕквівалентність планарних 3-дерев і хордальних максимальних планарних графів припустив без доведення Патіл . Доведення див. у статиі Маркензона, Джустела і Пакіорніка . Загальніший опис хордальних планарних графів та ефективного алгоритму їх розпізнавання див. у статті Кумара й Мадгавана . Що будь-який хордальний поліедричний граф є максимальним планарним, зауважив Герлах ..

У графі Аполлонія будь-яка максимальна кліка — це повний граф із чотирма вершинами, утворений вибором будь-якої вершини та трьох найближчих сусідів. Будь-який мінімальний кліковий сепаратор (кліка, видалення якої розбиває граф на два незв'язні графи) — це один із розділених трикутників. Хордальний граф, у якому всі максимальні кліки і всі мінімальні клікові сепаратори мають однаковий розмір, є k-деревом, а графи Аполлонія є прикладами 3-дерев. Не всі 3-дерева планарні, але планарні 3-дерева — це точно графи Аполлонія.

Єдиність розфарбування Будь-який граф Аполлонія має єдине 4-колірне розфарбування. Оскільки граф планарний, з теореми про чотири фарби випливає, що граф має розфарбування чотирма кольорами, але, оскільки кольори початкового трикутника фіксовані, є єдина можливість вибору кольору для нової вершини, тому з точністю до перестановки кольорів розфарбування графа буде єдиним. Складніше показати, але це також істинне, що будь-який планарний граф із єдиним розфарбуванням є графом Аполлонія. Таким чином, граф Аполлонія можна охарактеризувати як планарний граф з єдиним 4-колірним розфарбуванням. Графи Аполлонія дають приклади планарних графів, що мають найменше число k-розфарбувань для k > 4Факт, що графи Аполлонія мінімізують число розфарбувань із числом кольорів більшим від 4 показав Біркгоф у двоїстій формі розфарбування карт ..

Також графи Аполлонія — це точно максимальні планарні графи, які (якщо фіксувати зовнішню грань) мають єдиний ліс Шнайдера, розбиття ребер графа на три дерева з коренями у вершинах зовнішньої грані.

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

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

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

Екстремальність Інша властивість, що характеризує графи Аполлонія, стосується зв'язності. Будь-який максимальний планарний граф можна розкласти на 4-вершинно-зв'язні максимальні планарні підграфи поділом уздовж трикутників (які не є гранями графа) — якщо є трикутник, що не є гранню, можна утворити два менших максимальних планарних графи: один з частини, що міститься в трикутнику, інший — із зовнішньої відносно нього частини. Максимальні планарні графи без розділювальних трикутників, утворені багаторазовим розбиттям такого роду, іноді називають блоками, хоча так називають і компоненти двозв'язності графа, який сам по собі двозв'язним не є. Граф Аполлонія — це максимальний планарний граф, у якому всі блоки ізоморфні повному графу .

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

Геометричні реалізації

Побудова з упакованих кіл

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

Якщо процес побудови сітки Аполлонія зупинити, намалювавши лише скінченне число кіл, то граф, який має вершину для кожного кола і ребро для будь-яких двох дотичних кіл і є графом Аполлонія. Існування сножини дотичних кіл, дотики яких подають граф Аполлонія, визначає теорема Кебе — Андрєєва — Терстона, яка стверджує, що будь-який планарний граф можна подати дотичними колами.

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

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

Трикутні сітки Рекурсивний поділ трикутників на три менші трикутники досліджували Елкок, Гаргантіні і Волш як техніку сегментації зображення в комп'ютерному зорі. У цьому контексті вони називають такий поділ потрійним нерівностороннім розкладанням на трикутники. Вони помітили, що при додаванні кожної нової вершини в центроїд трикутника, трикутники тріангуляції матимуть однакові площі, хоча вони й різну форму. Загальніше, графи Аполлонія можна намалювати на площині з будь-якою заздалегідь заданою площею кожної грані. Якщо площі задано як раціональні числа, такими будуть і координати вершин.

Можна провести процес поділу трикутників при побудові графа Аполлонія так, що на кожному кроці довжини ребер будуть раціональними числами. Невідомо, чи будь-який планарний граф можна намалювати із такими самими властивостямиДля поділу трикутника з раціональними довжинами сторін так, щоб отримані трикутники теж мали раціональні сторони, див. статтю Альмеринга . Щодо загальної проблеми пошуку планарного графа з раціональними довжинами сторін див. статтю Гілена, Гуо та Маккіннона .. За поліноміальний час можна знайти малюнок планарного 3-дерева з цілими координатами з мінімальною площею обмежувального прямокутника і перевірити, чи можна намалювати задане планарне 3-дерево з вершинами на заданій множині точокЩодо малювання з цілими координатами див. статтю Мондала, Нішата, Рахмана й Алама . Щодо малювання на заданій множині вершин див. статтю Нішата, Мондала й Рахмана ..

Властивості та застосування

Графи без досконалого парування