Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

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

Мережа Аполлонія

Мережа Аполлонія
Не плутати з Сітка Аполлонія.

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

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

Визначення

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

Приклади

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Перелік

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

Історія

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

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

Назву «граф Аполлонія» запропоновано в статті Ж. Андраде, Г. Геррманна, Р. Андраде та Л. де Сільви для графів, у яких рівень поділу трикутників однорідний. Геометрично ці графи відповідають блоковим многогранникам (многогранникам Клі). Інші автори використовували термін для ширшого класу графів, планарних 3-дерев, з метою узагальнення моделі на випадкові графи Аполлонія. Тріангуляцію, отриману в такий спосіб, також назвали «блоковою тріангуляцією».

Див. також

  •  — інший метод поділу трикутника на менші трикутники
  • [en] — ще один метод поділу трикутника на менші трикутники

Примітки

  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.

Література

  • Marie Albenque, Jean-François Marckert. Some families of increasing planar maps // Electronic Journal of Probability. — 2008. — Т. 13. — С. 1624–1671. — arXiv:0712.0593. — DOI:10.1214/ejp.v13-563.
  • Almering. Rational quadrilaterals // . — 1963. — Т. 25. — С. 192–199..
  • N.Alon, Y. Caro. Convexity and Graph Theory: proceedings of the Conference on Convexity and Graph Theory, Israel, March 1981 / M. Rosenfeld, J. Zaks. — Elsevier, 1984. — С. 25–36. — (Annals of Discrete Mathematics 20, North-Holland Mathematical Studies 87) — .
  • José S. Andrade (Jr), Hans J. Herrmann, Roberto F. S. Andrade, Luciano R. da Silva. Apollonian Networks: Simultaneously Scale-Free, Small World, Euclidean, Space Filling, and with Matching Graphs // Physical Review Letters. — 2005. — Т. 94. — С. 018702. — arXiv:cond-mat/0406295. — DOI:10.1103/physrevlett.94.018702.
  • S. Arnborg, A. Proskurowski, D. Corniel. Forbidden Minors Characterization of Partial 3-trees. — Dept. of Computer and Information Science, University of Oregon, 1986. — (Technical Report CIS-TR-86-07). Как процитировано в статье Эль-Маллаха и Колбоурна (El-Mallah, Colbourn, 1990).
  • Melanie Badent, Carla Binucci, Emilio Di Giacomo, Walter Didimo, Stefan Felsner, Francesco Giordano, Jan Kratochvíl, Pietro Palladino, Maurizio Patrignani, Francesco Trotta. Canadian Conference on Computational Geometry. — 2007.
  • Alexander Below, Jesús A. De Loera, Jürgen Richter-Gebert. The Complexity of Finding Small Triangulations of Convex 3-Polytopes. — 2000.
  • Olivier Bernardi, Nicolas Bonichon. Intervals in Catalan lattices and realizers of triangulations // . — 2009. — Т. 116, вип. 1. — С. 55–75. — (Series A). — DOI:10.1016/j.jcta.2008.05.005.
  • Therese Biedl, Lesvia Elena Ruiz Velázquez. Graph Drawing, 17th International Symposium, GD 2009, Chicago, IL, USA, September 22–25, 2009, Revised Papers. — Springer-Verlag, 2010. — Т. 5849. — С. 316–322. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-11805-0_30.
  • George D. Birkhoff. On the number of ways of colouring a map // Proceedings of the Edinburgh Mathematical Society. — 1930. — Т. 2. — С. 83–91. — ((2)). — DOI:10.1017/S0013091500007598.
  • Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth // Theoretical Computer Science. — 1998. — Т. 209, вип. 1–2. — С. 1–45. — DOI:10.1016/S0304-3975(97)00228-4.
  • Thomas Böhme, Jochen Harant, Michal Tkáč. More than one tough chordal planar graphs are Hamiltonian // Journal of Graph Theory. — 1999. — Т. 32, вип. 4. — С. 405–410. — DOI:10.1002/(SICI)1097-0118(199912)32:4<405::AID-JGT8>3.3.CO;2-Q.
  • S. Butler, Ron Graham. Fete of Combinatorics and Computer Science / G. Katona, A. Schrijver, T. Szonyi. — Heidelberg : Springer-Verlag, 2010. — Т. 29. — С. 23–42. — (Bolyai Society Mathematical Studies)
  • Wayne Wei-Ming Dai, Masao Sato. IEEE International Symposium on Circuits and Systems. — 1990. — Т. 4. — С. 2677–2681. — DOI:10.1109/ISCAS.1990.112560.
  • Erik Demaine, André Schulz. Proc. ACM-SIAM Symposium on Discrete Algorithms. — 2011. — С. 1177–1187.
  • Vida Dujmović, Gašper Fijavž, Gwenaël Joret, David R. Wood. The maximum number of cliques in a graph embedded in a surface. — 2009. — arXiv:0906.4142.
  • Ehab S. El-Mallah, Charles J. Colbourn. On two dual classes of planar graphs // . — 1990. — Т. 80, вип. 1. — С. 21–40. — DOI:10.1016/0012-365X(90)90293-Q.
  • E. W. Elcock, I. Gargantini, T. R. Walsh. Triangular decomposition // Image and Vision Computing. — 1987. — Т. 5, вип. 3. — С. 225–231. — DOI:10.1016/0262-8856(87)90053-9.
  • Stefan Felsner, Florian Zickfeld. On the number of planar orientations with prescribed degrees // Electronic Journal of Combinatorics. — 2008. — Т. 15, вип. 1. — С. R77. — arXiv:math/0701771.
  • Alan M. Frieze, Charalampos E. Tsourakakis. High Degree Vertices, Eigenvalues and Diameter of Random Apollonian Networks. — 2011.
  • Thomas Fowler. Unique Coloring of Planar Graphs. — Georgia Institute of Technology Mathematics Department, 1998. — (Ph.D. thesis)
  • Jim Geelen, Anjie Guo, David McKinnon. Straight line embeddings of cubic planar graphs with integer edge lengths // Journal of Graph Theory. — 2008. — Т. 58, вип. 3. — С. 270–274. — DOI:10.1002/jgt.20304.
  • T. Gerlach. Toughness and Hamiltonicity of a class of planar graphs // . — 2004. — Т. 286, вип. 1—2. — С. 61–65. — DOI:10.1016/j.disc.2003.11.046.
  • A. Goldner, F. Harary. Note on a smallest nonhamiltonian maximal planar graph // Bull. Malaysian Math. Soc.. — 1975. — Т. 6, вип. 1. — С. 41–42.. См. также журналы 6(2):33 (1975) и 8:104-106 (1977). Посилання взято зі статті Список публікацій Харарі.
  • Branko Grünbaum. Unambiguous polyhedral graphs // Israel Journal of Mathematics. — 1963. — Т. 1, вип. 4. — С. 235–238. — DOI:10.1007/BF02759726.
  • Branko Grünbaum. Convex Polytopes. — Wiley Interscience, 1967.
  • S. L. Hakimi, E. F. Schmeichel. On the number of cycles of length k in a maximal planar graph // Journal of Graph Theory. — 1979. — Т. 3, вип. 1. — С. 69–86. — DOI:10.1002/jgt.3190030108.
  • Andrea Jiménez, Marcos Kiwi. Counting perfect matchings of cubic graphs in the geometric dual. — 2010. — arXiv:1010.5918.
  • P. Sreenivasa Kumar, C. E. Veni Madhavan. Foundations of Software Technology and Theoretical Computer Science, Ninth Conference, Bangalore, India December 19–21, 1989, Proceedings. — Springer-Verlag, 1989. — Т. 405. — С. 30–43. — (Lecture Notes in Computer Science) — DOI:10.1007/3-540-52048-1_30.
  • L. Markenzon, C. M. Justel, N. Paciornik. Subclasses of k-trees: Characterization and recognition // Discrete Applied Mathematics. — 2006. — Т. 154, вип. 5. — С. 818–825. — DOI:10.1016/j.dam.2005.05.021.
  • Debajyoti Mondal, Rahnuma Islam Nishat, Md. Saidur Rahman, Muhammad Jawaherul Alam. Canadian Conference on Computational Geometry. — 2010.
  • J. W. Moon, L. Moser. Simple paths on polyhedra // Pacific Journal of Mathematics. — 1963. — Т. 13. — С. 629–631. — DOI:10.2140/pjm.1963.13.629.
  • Rahnuma Islam Nishat, Debajyoti Mondal, Md. Saidur Rahman. Graph Drawing, 18th International Symposium, GD 2010, Konstanz, Germany, September 21–24, 2010, Revised Selected Papers. — Springer-Verlag, 2011. — Т. 6502. — С. 317–328. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-18469-7_29.
  • Takao Nishizeki. A 1-tough non-Hamiltonian maximal planar graph // . — 1980. — Т. 30, вип. 3. — С. 305–307. — DOI:10.1016/0012-365X(80)90240-X.
  • H. P. Patil. On the structure of k-trees // Journal of Combinatorics, Information and System Sciences. — 1986. — Т. 11, вип. 2—4. — С. 57–64.
  • Julius Petersen. Die Theorie der regulären graphs // . — 1891. — Т. 15. — С. 193–220. — DOI:10.1007/BF02392606.
  • Michael D. Plummer. Extending matchings in planar graphs IV // . — 1992. — Т. 109, вип. 1–3. — С. 207–219. — DOI:10.1016/0012-365X(92)90292-N.
  • T. Politof. A characterization and efficient reliability computation of Δ-Y reducible networks. — University of California, Berkeley, 1983. — (Ph.D. thesis). Как процитировано в статье Эль-Маллаха и Колбоурна El-Mallah, Colbourn, (1990).
  • Neil Robertson, P. D. Seymour. Graph minors. III. Planar tree-width // . — 1984. — Т. 36, вип. 1. — С. 49–64. — (Series B). — DOI:10.1016/0095-8956(84)90013-3.
  • Fujio Takeo. On triangulated graphs. I // Bull. Fukuoka Gakugei Univ. III. — 1960. — Т. 10. — С. 9–21.. На помилку щодо гамільтоновості в вказав Вільям Татт.
  • William Thurston. The geometry and topology of 3-manifolds. — Princeton lecture notes, 1978–1981.
  • Charalampos E. Tsourakakis. The Degree Sequence of Random Apollonian Networks. — Department of Mathematical Sciences, Carnegie Mellon University, 2011. — arXiv:1106.1940v1.
  • David R. Wood. On the maximum number of cliques in a graph // . — 2007. — Т. 23, вип. 3. — С. 337–352. — arXiv:math/0602191. — DOI:10.1007/s00373-007-0738-8.
  • Zhongzhi Zhang, Lichao Chen, Shuigeng Zhou, Lujun Fang, Jihong Guan, Tao Zou. Analytical solution of average path length for Apollonian networks // Physical Review E. — 2008. — Т. 77. — С. 017102. — arXiv:0706.3491. — DOI:10.1103/PhysRevE.77.017102.
  • Tao Zhou, Gang Yan, Bing-Hong Wang. Maximal planar networks with large clustering coefficient and power-law degree distribution // Physical Review E. — 2005. — Т. 71, вип. 4. — С. 046141. — arXiv:cond-mat/0412448. — DOI:10.1103/PhysRevE.71.046141.
  • Tao Zhou, Gang Yan, Pei-Ling Zhou, Zhong-Qian Fu, Bing-Hong Wang. Random Apollonian networks. — University of Science and Technology of China, Hefei Anhui, 2004. — arXiv:cond-mat/0409414v2.
  • Florian Zickfeld, Günter M. Ziegler. Workshop on Geometric and Topological Combinatorics. — Alcal ́a de Henares, Madrid, 2006.

Посилання

  • Weisstein, Eric W. Сітка Аполлонія(англ.) на сайті Wolfram MathWorld.
  • Matlab Simulation Code

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Ne plutati z Sitka Apolloniya Graf Apolloniya neoriyentovanij graf utvorenij rekursivnim procesom podilu trikutnika na tri menshi trikutniki Grafi Apolloniya mozhna ekvivalentno viznachiti yak planarni 3 dereva yak maksimalni planarni hordalni grafi yak odnoznachno 4 farbovani planarni grafi abo yak grafi blokovih mnogogrannikiv Grafi nazvano im yam Apolloniya Perzkogo yakij vivchav pov yazani pobudovi pakuvannya kil Graf ApolloniyaGraf Goldnera Harari negamiltoniv graf ApolloniyaViznachennyaGraf Apolloniya mozhna otrimati z trikutnogo grafa vkladenogo v evklidovu ploshinu shlyahom neodnorazovogo viboru trikutnoyi grani vkladennya dodannya novoyi vershini v cyu trikutnu gran i z yednannya novoyi vershini z kozhnoyu vershinoyu grani V rezultati gran dilitsya na tri menshi trikutniki yaki u svoyu chergu mozhna podiliti v takij samij sposib PrikladiPovni grafi z troma ta chotirma vershinami K3 ta K4 ye grafami Apolloniya K3 utvoryuyetsya z pochatkovogo trikutnika bez podalshih operacij podilu granej todi yak K4 utvoryuyetsya odniyeyu operaciyeyu podilu Graf Goldnera Harari ye grafom Apolloniya a takozh najmenshim maksimalnim negamiltonovim planarnim grafom Inshij skladnishij graf Apolloniya vikoristav Nishizeki yak priklad 1 zhorstkogo negamiltonovogo maksimalnogo planarnogo grafa Teoretichni vlastivostiOskilki grafi Apolloniya viznachayutsya rekursivnim podilom trikutnikiv voni mayut inshi matematichni opisi Grafi ye hordalnimi maksimalnimi planarnimi grafami hordalnimi mnogogrannimi grafami ta planarnimi 3 derevami Grafi ye odnoznachno 4 rozfarbovuvanimi planarnimi grafami ta planarnimi grafami z unikalnoyu dekompoziciyeyu v lis Shnajdera sho skladayetsya z troh derev Grafi ye maksimalnimi planarnimi grafami z derevnoyu shirinoyu 3 klasom grafiv yaki mozhna opisati yihnimi zaboronenimi grafami abo zvedennyam shlyahom Y D peretvoren Grafi ye maksimalnimi planarnimi grafami iz virodzhenistyu 3 Grafi ye takozh planarnimi grafami z danim chislom vershin yaki mayut najbilshu mozhlivu kilkist trikutnikiv najbilshu mozhlivu kilkist tetraedrichnih pidgrafiv najbilshu mozhlivu kilkist klik i najbilshu mozhlivu kilkist chastin pislya rozkladannya na okremi trikutniki Hordalnist Grafi Apolloniya ye prikladami maksimalnih planarnih grafiv u yaki ne mozhna dodati rebro bez porushennya planarnosti abo ekvivalentno grafami yaki mozhna namalyuvati na ploshini tak sho bud yaka gran zokrema j zovnishnya ye trikutnikom Grafi ye takozh hordalnimi grafami v yakih kozhen cikl iz chotiroh abo bilshe vershin maye diagonalne rebro sho z yednuye dvi vershini ciklu yaki ne ye poslidovnimi v cikli a poryadok u yakomu vershini dodayutsya v procesi pobudovi grafa Apolloniya ye poryadkom viklyuchennya v hordalnomu grafi Cya vlastivist daye alternativnij opis grafiv Apolloniya ce tochno hordalni maksimalni planarni grafi abo ekvivalentno hordalni mnogogranni grafi U grafi Apolloniya bud yaka maksimalna klika ce povnij graf iz chotirma vershinami utvorenij viborom bud yakoyi vershini ta troh najblizhchih susidiv Bud yakij minimalnij klikovij separator klika vidalennya yakoyi rozbivaye graf na dva nezv yazni grafi ce odin iz rozdilenih trikutnikiv Hordalnij graf u yakomu vsi maksimalni kliki i vsi minimalni klikovi separatori mayut odnakovij rozmir ye k derevom a grafi Apolloniya ye prikladami 3 derev Ne vsi 3 dereva planarni ale planarni 3 dereva ce tochno grafi Apolloniya Yedinist rozfarbuvannya Bud yakij graf Apolloniya maye yedine 4 kolirne rozfarbuvannya Oskilki graf planarnij z teoremi pro chotiri farbi viplivaye sho graf maye rozfarbuvannya chotirma kolorami ale oskilki kolori pochatkovogo trikutnika fiksovani ye yedina mozhlivist viboru koloru dlya novoyi vershini tomu z tochnistyu do perestanovki koloriv rozfarbuvannya grafa bude yedinim Skladnishe pokazati ale ce takozh istinne sho bud yakij planarnij graf iz yedinim rozfarbuvannyam ye grafom Apolloniya Takim chinom graf Apolloniya mozhna oharakterizuvati yak planarnij graf z yedinim 4 kolirnim rozfarbuvannyam Grafi Apolloniya dayut prikladi planarnih grafiv sho mayut najmenshe chislo k rozfarbuvan dlya k gt 4 Takozh grafi Apolloniya ce tochno maksimalni planarni grafi yaki yaksho fiksuvati zovnishnyu gran mayut yedinij lis Shnajdera rozbittya reber grafa na tri dereva z korenyami u vershinah zovnishnoyi grani Derevna shirina Dokladnishe Derevna shirina teoriya grafiv Grafi Apolloniya ne utvoryuyut simejstva grafiv zamknenogo shodo operaciyi vzyattya minoriv grafa oskilki pri vidalenni reber ale ne vershin otrimayemo graf yakij ne ye grafom Apolloniya Prote simejstvo planarnih chastkovih 3 derev pidgrafiv grafiv Apolloniya ye minorno zamknutim simejstvom Takim chinom zgidno z teoremoyu Robertsona Sejmura yih mozhna oharakterizuvati skinchennim chislom zaboronenih minoriv Minimalni zaboroneni minori dlya planarnih chastkovih 3 derev ce chotiri minimalni grafi dlya planarnih grafiv i chastkovih 3 derev povnij graf K5 povnij dvochastkovij graf K3 3 graf oktaedra ta graf p yatikutnoyi prizmi Grafi Apolloniya ye maksimalnimi grafami yaki ne mistyat cih chotiroh grafiv yak minoriv Peretvorennya Y D zaminyuye vershinu stepenya 3 na trikutnik sho z yednuye susidiv dostatno razom z operaciyeyu vidalennya kratnih reber dlya zvedennya grafa Apolloniya do yedinogo trikutnika Planarni grafi yaki mozhna zvesti do yedinogo rebra za dopomogoyu peretvorennya Y D vidalennya kratnih reber vidalennya vershin stepenya 1 i zaminoyu vershini stepenya 2 razom z rebrami na odne rebro ce tochno planarni chastkovi 3 dereva Dvoyisti grafi planarnih chastkovih 3 derev utvoryuyut inshe zamknute shodo vzyattya minoriv simejstvo grafiv yake ye tochno timi grafami yaki mozhna zvesti do yedinogo rebra za dopomogoyu peretvorennya D Y vidalennya kratnih reber vidalennya vershin stepenya 1 i zvilnennya vid vershin stepenya 2 Virodzhenist U bud yakomu pidgrafi grafa Apolloniya ostannya dodana vershina maye stepin 3 tomu grafi Apolloniya mayut virodzhenist 3 Takim chinom poryadok u yakomu vershini dodayutsya pri stvorenni grafa ye poryadkom virodzhennya i grafi Apolloniya zbigayutsya z 3 virodzhenimi maksimalnimi planarnimi grafami Ekstremalnist Insha vlastivist sho harakterizuye grafi Apolloniya stosuyetsya zv yaznosti Bud yakij maksimalnij planarnij graf mozhna rozklasti na 4 vershinno zv yazni maksimalni planarni pidgrafi podilom uzdovzh trikutnikiv yaki ne ye granyami grafa yaksho ye trikutnik sho ne ye grannyu mozhna utvoriti dva menshih maksimalnih planarnih grafi odin z chastini sho mistitsya v trikutniku inshij iz zovnishnoyi vidnosno nogo chastini Maksimalni planarni grafi bez rozdilyuvalnih trikutnikiv utvoreni bagatorazovim rozbittyam takogo rodu inodi nazivayut blokami hocha tak nazivayut i komponenti dvozv yaznosti grafa yakij sam po sobi dvozv yaznim ne ye Graf Apolloniya ce maksimalnij planarnij graf u yakomu vsi bloki izomorfni povnomu grafu K4 V ekstremalnij teoriyi grafiv grafi Apolloniya ce tochno planarni grafi z n vershinami v yakih chislo blokiv dosyagaye maksimalnogo znachennya n 3 ta planarni grafi v yakih chislo trikutnikiv maksimalne i dorivnyuye 3n 8 Oskilki kozhen pidgraf K4 planarnogo grafa maye buti blokom na cih grafah dosyagayetsya maksimum chisla pidgrafiv K4 ce chislo dorivnyuye n 3 Na cih zhe grafah dosyagayetsya najbilsha kilkist klik bud yakogo tipu chislo klik dorivnyuye 8n 16 Geometrichni realizaciyiPobudova z upakovanih kil Priklad sitki ApolloniyaPobudova grafa Apolloniya z upakovanih kil Grafi nazvano im yam Apolloniya Perzkogo yakij vivchav zadachu pobudovi kil sho dotikayutsya do troh inshih kil Odin iz metodiv pobudovi grafiv Apolloniya pochati z troh vzayemno dotichnih kil i bagatorazovo vpisuvati inshe kolo v promizhok utvorenij troma kolami pobudovanimi ranishe Fraktal utvorenij u takij sposib nazivayut sitkoyu Apolloniya Yaksho proces pobudovi sitki Apolloniya zupiniti namalyuvavshi lishe skinchenne chislo kil to graf yakij maye vershinu dlya kozhnogo kola i rebro dlya bud yakih dvoh dotichnih kil i ye grafom Apolloniya Isnuvannya snozhini dotichnih kil dotiki yakih podayut graf Apolloniya viznachaye yaka stverdzhuye sho bud yakij planarnij graf mozhna podati dotichnimi kolami Mnogogranniki Triakistetraedr realizaciya grafa Apolloniya z 8 vershinami u viglyadi mnogogrannika Grafi Apolloniya ce planarni 3 vershinno zv yazni grafi i tomu za teoremoyu Shtajnica mozhut buti zavzhdi podani yak grafi opuklih mnogogrannikiv Opuklij mnogogrannik sho podaye graf Apolloniya ce trivimirnij blokovij mnogogrannik Taki mnogogranniki mozhna otrimati z tetraedra bagatorazovim prikleyuvannyam dodatkovih tetraedriv po odnomu do trikutnih granej mnogogrannika Takim chinom grafi Apolloniya mozhna viznachiti yak grafi blokovih trivimirnih mnogogrannikiv Mozhna znajti podannya bud yakogo grafa Apolloniya yak opuklogo trivimirnogo mnogogrannika v yakomu vsi koordinati ye cilimi chislami polinomialnoyi velichini sho krashe nizh dlya inshih planarnih grafiv Trikutni sitki Rekursivnij podil trikutnikiv na tri menshi trikutniki doslidzhuvali Elkok Gargantini i Volsh yak tehniku segmentaciyi zobrazhennya v komp yuternomu zori U comu konteksti voni nazivayut takij podil potrijnim nerivnostoronnim rozkladannyam na trikutniki Voni pomitili sho pri dodavanni kozhnoyi novoyi vershini v centroyid trikutnika trikutniki triangulyaciyi matimut odnakovi ploshi hocha voni j riznu formu Zagalnishe grafi Apolloniya mozhna namalyuvati na ploshini z bud yakoyu zazdalegid zadanoyu plosheyu kozhnoyi grani Yaksho ploshi zadano yak racionalni chisla takimi budut i koordinati vershin Mozhna provesti proces podilu trikutnikiv pri pobudovi grafa Apolloniya tak sho na kozhnomu kroci dovzhini reber budut racionalnimi chislami Nevidomo chi bud yakij planarnij graf mozhna namalyuvati iz takimi samimi vlastivostyami Za polinomialnij chas mozhna znajti malyunok planarnogo 3 dereva z cilimi koordinatami z minimalnoyu plosheyu obmezhuvalnogo pryamokutnika i pereviriti chi mozhna namalyuvati zadane planarne 3 derevo z vershinami na zadanij mnozhini tochok Vlastivosti ta zastosuvannyaGrafi bez doskonalogo paruvannya Plammer vikoristav grafi Apolloniya dlya pobudovi neskinchennogo simejstva maksimalnih planarnih grafiv iz parnim chislom vershin sho ne mayut doskonalogo paruvannya Grafi Plammera buduyutsya v dva etapi Na pershomu etapi pochinayuchi z trikutnika abc bagato raziv povtoryuyetsya podil trikutnoyi grani sho mistit rebro bc Otrimanij graf mistit shlyah z a do kincevoyi vershini podilu ta kozhna vershina cogo shlyahu z yednana rebrami z vershinami b i c Na drugomu etapi kozhna trikutna gran otrimanogo planarnogo grafa she raz rozbivayetsya Yaksho shlyah z a do kincevoyi vershini rozbittya pershogo etapu maye parnu dovzhinu zagalna kilkist vershin grafa tezh parna Odnak priblizno 2 3 vershin vstavlenih na drugomu etapi utvoryuyut nezalezhnu mnozhinu i ne mozhut utvoryuvati paruvan mizh soboyu a reshti vershin dlya utvorennya doskonalogo paruvannya nedostatno Hocha sami grafi Apolloniya ne mozhut mati doskonalih paruvan dvoyisti grafam Apolloniya grafi ye 3 regulyarnymi grafami bez rozrizalnih reber otzhe za teoremoyu Petersena voni obov yazkovo mayut prinajmni odne doskonale paruvannya Dlya grafiv Apolloniya vidomo navit bilshe dvoyisti grafam Apolloniya grafi mayut eksponencijno veliku kilkist doskonalih paruvaan Laslo Lovas i Majkl D Plammer vislovili gipotezu sho analogichna eksponencijna nizhnya mezha maye isnuvati dlya vsih 3 regulyarnih grafiv bez rozrizalnih reber sho j bulo piznishe pidtverdzheno Stepenevij zakon grafiv Zh Andrade G Gerrmann R Andrade i L de Silva vivchali stepenevi zakoni poslidovnostej stepeniv osoblivih vidiv grafiv cogo vidu utvorenih podilom usih trikutnikiv odnakove chislo raziv Voni vikoristovuvali ci grafi dlya modelyuvannya zapovnennya prostoru chastinami riznogo rozmiru Gruntuyuchis na yihnij praci inshi avtori zaproponuvali vipadkovi grafi Apolloniya oderzhuvani vipadkovim viborom grani dlya podilu i pokazali sho dlya cih grafiv vikonuyetsya stepenevij zakon u rozpodili stepeniv vershin a takozh pokazali sho ci grafi mayut mali vidstani Friz i Tsourakakis analizuvali najbilshi stepeni vershin i vlasni znachennya vipadkovih grafiv Apolloniya Zh Andrade G Gerrmann R Andrade i L de Silva pomitili takozh sho yihni grafi zadovolnyayut efektu svit tisnij teoriya shesti rukostiskan tobto vsi vershini roztashovani blizko odna vid odnoyi Gruntuyuchis na chiselnih eksperimentah voni ocinili serednyu vidstan mizh vipadkovo vibranimi parami vershin u grafi z n vershinami yak proporcijnu log n 3 4 ale podalshi doslidzhennya pokazali sho serednya vidstan naspravdi proporcijna log n Rozpodil kutiv Batler i Grem pomitili sho yaksho kozhnu novu vershinu pomishati v tochku peretinu bisektris trikutnika to mnozhina trijok kutiv trikutnikiv u podili yaksho yih interpretuvati yak baricentrichni koordinati tochok u pravilnomu trikutniku pri zrostanni rivnya podilu v granici utvoryuye trikutnik Serpinskogo Gamiltonovist Takeo pomilkovo stverdzhuvav sho vsi grafi Apolloniya mayut gamiltonovi cikli prote graf Goldnera Harari ye kontrprikladom Yaksho graf Apolloniya maye zhorstkist bilshu vid 1 sho oznachaye sho pri vidalenni bud yakogo chisla vershin iz grafa v nomu zalishayetsya zv yaznih komponentiv menshe nizh chislo vidalenih vershin vin obov yazkovo gamiltoniv ale isnuyut negamiltonovi grafi Apolloniya zhorstkist yakih dorivnyuye odinici Perelik Kombinatornu zadachu pidrahunku apolloniyevih triangulyacij vivchav Takeo Vin pokazav sho dlya chisla triangulyacij isnuye prosta tvirna funkciya f x 1 x f x 3 U cij tvirnij funkciyi chlen stepenya n mistit chislo grafiv Apolloniya iz zovnishnim trikutnikom i n 3 vershinami Chislo grafiv Apolloniya iz zovnishnim trikutnikom i 3 4 5 vershinami 1 1 3 12 55 273 1428 7752 43263 246675 poslidovnist A001764 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS Cya zh poslidovnist zadaye kilkist trijkovih derev i kilkist rozbittiv opuklogo mnogokutnika na mnogokutniki z neparnim chislom storin Napriklad isnuye 12 grafiv Apolloniya z 6 vershinami tri utvoryuyutsya rozbittyam zovnishnogo trikutnika z podalshim rozbittyam dvoh z otrimanih trikutnikiv i she dev yat utvoryuyutsya rozbittyam zovnishnogo trikutnika i rozbittyam odnogo z otrimanih trikutnikiv iz podalshim rozbittyam odnogo z malih trikutnikiv IstoriyaBirkgof ye rannya stattya v yakij vikoristano dvoyistu formu grafiv Apolloniya planarni karti utvoreni bagatorazovim pomishennyam novih dilyanok u vershinah prostishih kart yak priklad klasu planarnih grafiv z malim chislom koloriv Geometrichni strukturi blizki do grafiv Apolloniya vivchalisya v kombinatorici mnogogrannikiv vid pochatku 1960 h rokiv koli Gryunbaum vikoristav yih dlya opisu grafiv yaki mozhna realizuvati u mnogogrannikah u yedinij sposib za rozmirnistyu i z tochki zoru kombinatoriki Yih vikoristali takozh Mun ta Mozer dlya poshuku simplicijnih mnogogrannikiv bez dovgih shlyahiv U teoriyi grafiv tisnij zv yazok mizh planarnistyu i derevnoyu shirinoyu prostezhuyetsya do statti Robertsona i Sejmura 1984 roku yaki pokazali sho zamknene vidnosno vzyattya minoriv simejstvo grafiv abo maye obmezhenu derevnu shirinu abo mistit usi planarni grafi Planarni 3 dereva yak klas grafiv rozglyadali Hakimi i Shmajhel Alon i Karo Patil ta bagato inshih avtoriv Nazvu graf Apolloniya zaproponovano v statti Zh Andrade G Gerrmanna R Andrade ta L de Silvi dlya grafiv u yakih riven podilu trikutnikiv odnoridnij Geometrichno ci grafi vidpovidayut blokovim mnogogrannikam mnogogrannikam Kli Inshi avtori vikoristovuvali termin dlya shirshogo klasu grafiv planarnih 3 derev z metoyu uzagalnennya modeli na vipadkovi grafi Apolloniya Triangulyaciyu otrimanu v takij sposib takozh nazvali blokovoyu triangulyaciyeyu Div takozh inshij metod podilu trikutnika na menshi trikutniki en she odin metod podilu trikutnika na menshi trikutnikiPrimitkiCej graf nazvano imenami avtoriv statti Goldner Harary 1975 Odnak vin i ranishe z yavlyavsya v literaturi napriklad u Gryunbauma Grunbaum 1967 stor 357 Nishizeki 1980 Ekvivalentnist planarnih 3 derev i hordalnih maksimalnih planarnih grafiv pripustiv bez dovedennya Patil Patil 1986 Dovedennya div u statii Markenzona Dzhustela i Pakiornika Markenzon Justel Paciornik 2006 Zagalnishij opis hordalnih planarnih grafiv ta efektivnogo algoritmu yih rozpiznavannya div u statti Kumara j Madgavana Kumar Madhavan 1989 Sho bud yakij hordalnij poliedrichnij graf ye maksimalnim planarnim zauvazhiv Gerlah Gerlach 2004 Fowler 1998 Fakt sho grafi Apolloniya minimizuyut chislo rozfarbuvan iz chislom koloriv bilshim vid 4 pokazav Birkgof u dvoyistij formi rozfarbuvannya kart Birkhoff 1930 Felsner Zickfeld 2008 Bernardi Bonichon 2009 Dva zaboroneni minori dlya planarnih grafiv daye teorema Vagnera Pro zaboroneni minori chastkovih 3 derev yaki vklyuchayut takozh neplanarnij graf Vagnera div statti Arnborga Proskurovski Korniela Arnborg Proskurowski Corniel 1986 i Bodlaendera Bodlaender 1998 Pryame dovedennya togo sho graf oktaedra ta p yatikutnoyi prizmi ye yedinimi dvoma planarnimi zaboronenimi minorami div u stattyah Dayi Sato Dai Sato 1990 i El Mallaha Kolbourna El Mallah Colbourn 1990 Politof Politof 1983 uviv zvidni D Y planarni grafi j opisav yih u terminah zaboronenih gomeomorfnih pidgrafiv Dvoyistist mizh D Y i Y D zvidnimi grafami opis oboh klasiv zaboronenimi minorami i zv yazok iz planarnimi chastkovimi 3 derevami vzyato zi statti El Mallaha i Kolbourna El Mallah Colbourn 1990 Opis uterminah najbilshogo chisla trikutnikiv u planarnomu grafi divitsya stattyu Hakimi ta Shmejhelya Hakimi Schmeichel 1979 Alon i Saro cituyut cej rezultat i nadayut opis u terminah izomorfizmu klasiv blokiv ta chisla blokiv Alon Caro 1984 Mezha zagalnogo chisla klik dosit prosto vihodit z mezhi chisla pidgrafiv i pidgrafiv K4 yiyi naviv u yavnomu viglyadi Vud Wood 2007 yakij na prikladi grafiv Apolloniya pokazav strogist mezhi Uzagalnennya cih mezh dlya neplanarnih poverhon divitsya v statti Dujmovicha Fiyavzha Zhore i Vuda Dujmovic Fijavz Joret Wood 2009 Andrade Herrmann Andrade da Silva 2005 Thurston 1978 1981 Div napriklad stattyu Byelova De Loera j Rihter Geberta Below De Loera Richter Gebert 2000 Demaine Schulz 2011 Elcock Gargantini Walsh 1987 Biedl Ruiz Velazquez 2010 Dlya podilu trikutnika z racionalnimi dovzhinami storin tak shob otrimani trikutniki tezh mali racionalni storoni div stattyu Almeringa Almering 1963 Shodo zagalnoyi problemi poshuku planarnogo grafa z racionalnimi dovzhinami storin div stattyu Gilena Guo ta Makkinnona Geelen Guo McKinnon 2008 Shodo malyuvannya z cilimi koordinatami div stattyu Mondala Nishata Rahmana j Alama Mondal Nishat Rahman Alam 2010 Shodo malyuvannya na zadanij mnozhini vershin div stattyu Nishata Mondala j Rahmana Nishat Mondal Rahman 2011 Plummer 1992 Petersen 1891 Jimenez Kiwi 2010 Tsourakakis 2011 Zhou Yan Zhou Fu Wang 2004 Zhou Yan Wang 2005 Frieze Tsourakakis 2011 Albenque Marckert 2008 Zhang Chen Zhou Fang 2008 Butler Graham 2010 Takeo 1960 Div stattyu Nishizeki Nishizeki 1980 z prikladom negamiltonovogo grafa yakij maye zhorstkist 1 i stattyu Beme Garanta j Tkacha Bohme Harant Tkac 1999 z dovedennyam sho grafi Apolloniya z bilshoyu zhorstkistyu ye gamiltonovimi Div stattyu Gerlaha Gerlach 2004 z uzagalnennyam cogo rezultatu na shirshij klas planarnih grafiv Birkhoff 1930 Grunbaum 1963 Moon Moser 1963 Robertson Seymour 1984 Hakimi Schmeichel 1979 Alon Caro 1984 Patil 1986 Grunbaum 1967 Zickfeld Ziegler 2006 Badent Binucci Di Giacomo Didimo 2007 LiteraturaMarie Albenque Jean Francois Marckert Some families of increasing planar maps Electronic Journal of Probability 2008 T 13 S 1624 1671 arXiv 0712 0593 DOI 10 1214 ejp v13 563 Almering Rational quadrilaterals 1963 T 25 S 192 199 N Alon Y Caro Convexity and Graph Theory proceedings of the Conference on Convexity and Graph Theory Israel March 1981 M Rosenfeld J Zaks Elsevier 1984 S 25 36 Annals of Discrete Mathematics 20 North Holland Mathematical Studies 87 ISBN 978 0 444 86571 7 Jose S Andrade Jr Hans J Herrmann Roberto F S Andrade Luciano R da Silva Apollonian Networks Simultaneously Scale Free Small World Euclidean Space Filling and with Matching Graphs Physical Review Letters 2005 T 94 S 018702 arXiv cond mat 0406295 DOI 10 1103 physrevlett 94 018702 S Arnborg A Proskurowski D Corniel Forbidden Minors Characterization of Partial 3 trees Dept of Computer and Information Science University of Oregon 1986 Technical Report CIS TR 86 07 Kak procitirovano v state El Mallaha i Kolbourna El Mallah Colbourn 1990 Melanie Badent Carla Binucci Emilio Di Giacomo Walter Didimo Stefan Felsner Francesco Giordano Jan Kratochvil Pietro Palladino Maurizio Patrignani Francesco Trotta Canadian Conference on Computational Geometry 2007 Alexander Below Jesus A De Loera Jurgen Richter Gebert The Complexity of Finding Small Triangulations of Convex 3 Polytopes 2000 Olivier Bernardi Nicolas Bonichon Intervals in Catalan lattices and realizers of triangulations 2009 T 116 vip 1 S 55 75 Series A DOI 10 1016 j jcta 2008 05 005 Therese Biedl Lesvia Elena Ruiz Velazquez Graph Drawing 17th International Symposium GD 2009 Chicago IL USA September 22 25 2009 Revised Papers Springer Verlag 2010 T 5849 S 316 322 Lecture Notes in Computer Science DOI 10 1007 978 3 642 11805 0 30 George D Birkhoff On the number of ways of colouring a map Proceedings of the Edinburgh Mathematical Society 1930 T 2 S 83 91 2 DOI 10 1017 S0013091500007598 Hans L Bodlaender A partial k arboretum of graphs with bounded treewidth Theoretical Computer Science 1998 T 209 vip 1 2 S 1 45 DOI 10 1016 S0304 3975 97 00228 4 Thomas Bohme Jochen Harant Michal Tkac More than one tough chordal planar graphs are Hamiltonian Journal of Graph Theory 1999 T 32 vip 4 S 405 410 DOI 10 1002 SICI 1097 0118 199912 32 4 lt 405 AID JGT8 gt 3 3 CO 2 Q S Butler Ron Graham Fete of Combinatorics and Computer Science G Katona A Schrijver T Szonyi Heidelberg Springer Verlag 2010 T 29 S 23 42 Bolyai Society Mathematical Studies Wayne Wei Ming Dai Masao Sato IEEE International Symposium on Circuits and Systems 1990 T 4 S 2677 2681 DOI 10 1109 ISCAS 1990 112560 Erik Demaine Andre Schulz Proc ACM SIAM Symposium on Discrete Algorithms 2011 S 1177 1187 Vida Dujmovic Gasper Fijavz Gwenael Joret David R Wood The maximum number of cliques in a graph embedded in a surface 2009 arXiv 0906 4142 Ehab S El Mallah Charles J Colbourn On two dual classes of planar graphs 1990 T 80 vip 1 S 21 40 DOI 10 1016 0012 365X 90 90293 Q E W Elcock I Gargantini T R Walsh Triangular decomposition Image and Vision Computing 1987 T 5 vip 3 S 225 231 DOI 10 1016 0262 8856 87 90053 9 Stefan Felsner Florian Zickfeld On the number of planar orientations with prescribed degrees Electronic Journal of Combinatorics 2008 T 15 vip 1 S R77 arXiv math 0701771 Alan M Frieze Charalampos E Tsourakakis High Degree Vertices Eigenvalues and Diameter of Random Apollonian Networks 2011 Thomas Fowler Unique Coloring of Planar Graphs Georgia Institute of Technology Mathematics Department 1998 Ph D thesis Jim Geelen Anjie Guo David McKinnon Straight line embeddings of cubic planar graphs with integer edge lengths Journal of Graph Theory 2008 T 58 vip 3 S 270 274 DOI 10 1002 jgt 20304 T Gerlach Toughness and Hamiltonicity of a class of planar graphs 2004 T 286 vip 1 2 S 61 65 DOI 10 1016 j disc 2003 11 046 A Goldner F Harary Note on a smallest nonhamiltonian maximal planar graph Bull Malaysian Math Soc 1975 T 6 vip 1 S 41 42 Sm takzhe zhurnaly 6 2 33 1975 i 8 104 106 1977 Posilannya vzyato zi statti Spisok publikacij Harari Branko Grunbaum Unambiguous polyhedral graphs Israel Journal of Mathematics 1963 T 1 vip 4 S 235 238 DOI 10 1007 BF02759726 Branko Grunbaum Convex Polytopes Wiley Interscience 1967 S L Hakimi E F Schmeichel On the number of cycles of length k in a maximal planar graph Journal of Graph Theory 1979 T 3 vip 1 S 69 86 DOI 10 1002 jgt 3190030108 Andrea Jimenez Marcos Kiwi Counting perfect matchings of cubic graphs in the geometric dual 2010 arXiv 1010 5918 P Sreenivasa Kumar C E Veni Madhavan Foundations of Software Technology and Theoretical Computer Science Ninth Conference Bangalore India December 19 21 1989 Proceedings Springer Verlag 1989 T 405 S 30 43 Lecture Notes in Computer Science DOI 10 1007 3 540 52048 1 30 L Markenzon C M Justel N Paciornik Subclasses of k trees Characterization and recognition Discrete Applied Mathematics 2006 T 154 vip 5 S 818 825 DOI 10 1016 j dam 2005 05 021 Debajyoti Mondal Rahnuma Islam Nishat Md Saidur Rahman Muhammad Jawaherul Alam Canadian Conference on Computational Geometry 2010 J W Moon L Moser Simple paths on polyhedra Pacific Journal of Mathematics 1963 T 13 S 629 631 DOI 10 2140 pjm 1963 13 629 Rahnuma Islam Nishat Debajyoti Mondal Md Saidur Rahman Graph Drawing 18th International Symposium GD 2010 Konstanz Germany September 21 24 2010 Revised Selected Papers Springer Verlag 2011 T 6502 S 317 328 Lecture Notes in Computer Science DOI 10 1007 978 3 642 18469 7 29 Takao Nishizeki A 1 tough non Hamiltonian maximal planar graph 1980 T 30 vip 3 S 305 307 DOI 10 1016 0012 365X 80 90240 X H P Patil On the structure of k trees Journal of Combinatorics Information and System Sciences 1986 T 11 vip 2 4 S 57 64 Julius Petersen Die Theorie der regularen graphs 1891 T 15 S 193 220 DOI 10 1007 BF02392606 Michael D Plummer Extending matchings in planar graphs IV 1992 T 109 vip 1 3 S 207 219 DOI 10 1016 0012 365X 92 90292 N T Politof A characterization and efficient reliability computation of D Y reducible networks University of California Berkeley 1983 Ph D thesis Kak procitirovano v state El Mallaha i Kolbourna El Mallah Colbourn 1990 Neil Robertson P D Seymour Graph minors III Planar tree width 1984 T 36 vip 1 S 49 64 Series B DOI 10 1016 0095 8956 84 90013 3 Fujio Takeo On triangulated graphs I Bull Fukuoka Gakugei Univ III 1960 T 10 S 9 21 Na pomilku shodo gamiltonovosti v vkazav Vilyam Tatt William Thurston The geometry and topology of 3 manifolds Princeton lecture notes 1978 1981 Charalampos E Tsourakakis The Degree Sequence of Random Apollonian Networks Department of Mathematical Sciences Carnegie Mellon University 2011 arXiv 1106 1940v1 David R Wood On the maximum number of cliques in a graph 2007 T 23 vip 3 S 337 352 arXiv math 0602191 DOI 10 1007 s00373 007 0738 8 Zhongzhi Zhang Lichao Chen Shuigeng Zhou Lujun Fang Jihong Guan Tao Zou Analytical solution of average path length for Apollonian networks Physical Review E 2008 T 77 S 017102 arXiv 0706 3491 DOI 10 1103 PhysRevE 77 017102 Tao Zhou Gang Yan Bing Hong Wang Maximal planar networks with large clustering coefficient and power law degree distribution Physical Review E 2005 T 71 vip 4 S 046141 arXiv cond mat 0412448 DOI 10 1103 PhysRevE 71 046141 Tao Zhou Gang Yan Pei Ling Zhou Zhong Qian Fu Bing Hong Wang Random Apollonian networks University of Science and Technology of China Hefei Anhui 2004 arXiv cond mat 0409414v2 Florian Zickfeld Gunter M Ziegler Workshop on Geometric and Topological Combinatorics Alcal a de Henares Madrid 2006 PosilannyaWeisstein Eric W Sitka Apolloniya angl na sajti Wolfram MathWorld Matlab Simulation Code

Дата публікації:
Топ