Вікіпедія

Граф Аполлонія

неорієнтований граф, утворений рекурсивним поділом трикутника на три менші трикутники
Не плутати з Сітка Аполлонія.

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

Граф Аполлонія
Граф Голднера — Харарі, негамільтонів граф Аполлонія

Визначення

ред.

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

Приклади

ред.

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

Граф Голднера — Харарі є графом Аполлонія, а також найменшим максимальним негамільтоновим планарним графом[1]. Інший, складніший граф Аполлонія, використав Нішизекі[2] як приклад 1-жорсткого негамільтонового максимального планарного графа.

Теоретичні властивості

ред.

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

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

ред.

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

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

Єдиність розфарбування

ред.

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

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

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

ред.
Докладніше: Деревна ширина (теорія графів)

Графи Аполлонія не утворюють сімейства графів, замкненого щодо операції взяття мінорів графа, оскільки при видаленні ребер, але не вершин, отримаємо граф, який не є графом Аполлонія. Проте, сімейство планарних часткових 3-дерев, підграфів графів Аполлонія, є мінорно замкнутим сімейством. Таким чином, згідно з теоремою Робертсона — Сеймура, їх можна охарактеризувати скінченним числом заборонених мінорів. Мінімальні заборонені мінори для планарних часткових 3-дерев — це чотири мінімальні графи для планарних графів і часткових 3-дерев: повний граф K5, повний двочастковий граф K3,3, граф октаедра та граф п'ятикутної призми. Графи Аполлонія є максимальними графами, які не містять цих чотирьох графів як мінорів[8].

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

Виродженість

ред.

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

Екстремальність

ред.

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

В екстремальній теорії графів графи Аполлонія — це точно планарні графи з n вершинами, в яких число блоків досягає максимального значення n − 3, та планарні графи, в яких число трикутників максимальне і дорівнює 3n − 8. Оскільки кожен підграф K4 планарного графа має бути блоком, на цих графах досягається максимум числа підграфів K4 (це число дорівнює n − 3). На цих же графах досягається найбільша кількість клік будь-якого типу (число клік дорівнює 8n − 16)[10].

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

ред.

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

ред.
 
Приклад сітки Аполлонія
 
Побудова графа Аполлонія з упакованих кіл

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

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

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

ред.
 
Триакістетраедр — реалізація графа Аполлонія з 8 вершинами у вигляді многогранника

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

Трикутні сітки

ред.

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

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

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

ред.

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

ред.

Пламмер[19] використав графи Аполлонія для побудови нескінченного сімейства максимальних планарних графів із парним числом вершин, що не мають досконалого парування. Графи Пламмера будуються в два етапи. На першому етапі, починаючи з трикутника abc, багато разів повторюється поділ трикутної грані, що містить ребро bc. Отриманий граф містить шлях з a до кінцевої вершини поділу та кожна вершина цього шляху з'єднана ребрами з вершинами b і c. На другому етапі кожна (трикутна) грань отриманого планарного графа ще раз розбивається. Якщо шлях з a до кінцевої вершини розбиття першого етапу має парну довжину, загальна кількість вершин графа теж парна. Однак приблизно 2/3 вершин, вставлених на другому етапі, утворюють незалежну множину і не можуть утворювати парувань між собою, а решти вершин для утворення досконалого парування недостатньо.

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

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

ред.

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

Розподіл кутів

ред.

Батлер і Ґрем[28] помітили, що якщо кожну нову вершину поміщати в точку перетину бісектрис трикутника, то множина трійок кутів трикутників у поділі, якщо їх інтерпретувати як барицентричні координати точок у правильному трикутнику, при зростанні рівня поділу в границі утворює трикутник Серпінського.

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

ред.

Такео[29] помилково стверджував, що всі графи Аполлонія мають гамільтонові цикли, проте граф Голднера-Харарі є контрприкладом. Якщо граф Аполлонія має жорсткість, більшу від 1 (що означає, що при видаленні будь-якого числа вершин із графа в ньому залишається зв'язних компонентів менше, ніж число видалених вершин), він обов'язково гамільтонів, але існують негамільтонові графи Аполлонія, жорсткість яких дорівнює одиниці[30].

Перелік

ред.

Комбінаторну задачу підрахунку аполлонієвих тріангуляцій вивчав Такео[29]. Він показав, що для числа тріангуляцій існує проста твірна функція 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 вершинами — три утворюються розбиттям зовнішнього трикутника з подальшим розбиттям двох з отриманих трикутників і ще дев'ять утворюються розбиттям зовнішнього трикутника і розбиттям одного з отриманих трикутників із подальшим розбиттям одного з малих трикутників.

Історія

ред.

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

Геометричні структури, близькі до графів Аполлонія, вивчалися в комбінаториці многогранників від початку 1960-х років, коли Ґрюнбаум[32] використав їх для опису графів, які можна реалізувати у многогранниках у єдиний спосіб за розмірністю і з точки зору комбінаторики. Їх використали також Мун та Мозер[33] для пошуку симпліційних многогранників без довгих шляхів. У теорії графів тісний зв'язок між планарністю і деревною шириною простежується до статті Робертсона і Сеймура 1984 року[34], які показали, що замкнене відносно взяття мінорів сімейство графів або має обмежену деревну ширину, або містить усі планарні графи. Планарні 3-дерева, як клас графів, розглядали Хакімі і Шмайхель[35], Алон і Каро[36], Патіл[37] та багато інших авторів.

Назву «граф Аполлонія» запропоновано в статті Ж. Андраде, Г. Геррманна, Р. Андраде та Л. де Сільви[11] для графів, у яких рівень поділу трикутників однорідний. Геометрично ці графи відповідають блоковим многогранникам (многогранникам Клі)[32][38]. Інші автори використовували термін для ширшого класу графів, планарних 3-дерев, з метою узагальнення моделі на випадкові графи Аполлонія[23][24]. Тріангуляцію, отриману в такий спосіб, також назвали «блоковою тріангуляцією»[36][39][40][6][26][7][21].

Див. також

ред.

Примітки

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

Література

ред.

Посилання

ред.
Отримано з https://uk.wikipedia.org/w/index.php?title=Граф_Аполлонія&oldid=43675331