Коловий граф
У теорії графів коловий граф — це граф перетинів множини хорд кола. Тобто це неорієнтований граф, вершини якого можна ототожнити з хордами кола, і ці вершини суміжні тоді й тільки тоді, коли відповідні хорди перетинаються.
Алгоритмічна складність
СпінрадШаблон:Sfn представив алгоритм, який працює за час O(n2), який перевіряє, чи є заданий неорієнтований граф з n вершинами коловим, і якщо він коловий, будує множину хорд, які дають коловий граф.
Багато інших задач, які NP-повні на графах загального вигляду, мають алгоритми поліноміального часу, якщо обмежитися коловими графами. Наприклад, КлоксШаблон:Sfn показав, що деревну ширину колового графа можна визначити, а оптимальне дерево декомпозиції побудувати за час O(n3). Крім того, найменше заміщення (тобто хордальний граф з якомога меншим числом ребер, що містить даний коловий граф як підграф) можна знайти за час O(n3)Шаблон:Sfn. ТіскінШаблон:Sfn показав, що найбільшу кліку колового графа можна знайти за час O(n log2 n), а Неш і ГреггШаблон:Sfn показали, що найбільшу незалежну множину незваженого колового графа можна знайти за час O(n min{d, α}), де d — параметр графа, відомий як щільність, а α — число незалежності колового графа.
Все ж є задачі, які залишаються NP-повними, навіть якщо обмежитися коловими графами. До цих задач належать пошуки домінівної множини, найменшої зв'язної домінівної множини і найменшої тотальної домінівної множиниШаблон:Sfn.
Хроматичне число
Хроматичне число колового графа дорівнює найменшому числу кольорів, які можна використати для розфарбовування хорд, так, щоб ніякі дві перетинні хорди не мали однакового кольору. Оскільки можна утворити коловий граф, у якому довільна велика множина хорд перетинають одна одну, хроматичне число колового графа може бути довільно великим, а визначення хроматичного числа колового графа є NP-повною задачеюШаблон:Sfn. NP-повною задачею є й перевірка, чи можна розфарбувати коловий граф чотирма кольорамиШаблон:Sfn. УнгерШаблон:Sfn стверджував, що пошук розфарбування трьома кольорами можна здійснити за поліноміальний час, але в описі його результатів відсутні багато подробицьШаблон:Sfn.
Деякі автори досліджували задачу розфарбовування обмежених підкласів колових графів малим числом кольорів. Зокрема, колові графи, в яких немає множин з k і більше хорд, в яких всі хорди перетинають одна одну, можна розфарбувати, не перевищуючи кольорів[1]. Зокрема, при k = 3 (тобто для колових графів без трикутників) хроматичне число не перевищує п'яти, і ця межа точна — всі колові графи без трикутників можна розфарбувати в п'ять кольорів і існують колові графи без трикутників, що вимагають п'яти кольорів для розфарбовування[2]. Якщо коловий граф має обхват щонайменше п'ять (тобто в ньому немає трикутників і циклів з чотирма вершинами), його можна розфарбувати, обмежившись трьома кольорамиШаблон:Sfn. Задача розфарбовування рамкових графів без трикутників еквівалентна задачі подання рамкових графів у вигляді графа, ізометричного прямому добутку дерев. У цій відповідності задач число кольорів у розфарбуванні відповідає числу дерев у добуткуШаблон:Sfn.
Застосування
Колові графи з'являються під час проєктування НВІС як абстракція окремого випадку трасування друкованих плат, відомого як «двополюсне трасування перетинів каналів». У цьому випадку ділянка трасування є прямокутником, усі мережі є двополюсниками, а виводи розташовуються по периметру прямокутника. Легко бачити, що граф перетинів цієї мережі є коловим графомШаблон:Sfn. Одна з цілей трасування — забезпечення відсутності електричного контакту між різними мережами та розташування можливих перетинних частин на різних шарах. Таким чином, колові графи охоплюють частину задач трасування.
Розфарбування колових графів можна використовувати також для пошуку книжкового вкладення довільних графів — якщо вершини заданого графа G розташовані на колі, а ребра графа G утворюють хорди кола, то граф перетинів цих хорд є коловим графом, а розфарбування цього колового графа еквівалентне книжковому вкладенню, що зберігає колове розташування. У цій еквівалентності число кольорів відповідає числу сторінок у книжковому вкладенніШаблон:Sfn.
Пов'язані класи графів
Граф перетинів множини інтервалів на прямій називається інтервальним графом.
Граф є коловим тоді і тільки тоді, коли він є правильним інтервальним графом. Це графи, вершини яких відповідають (відкритим) відрізкам на прямий і дві вершини з'єднані ребром, якщо два інтервали мають непорожній перетин. При цьому ніякий інтервал не міститься повністю в іншому інтервалі.
Струнні графи, графи перетинів кривих на площині, включають колові графи як окремий випадок.
Будь-який дистанційно-успадковуваний граф є коловим графом, як і будь-який граф перестановки або індиферентний граф. Будь-який зовніпланарний граф також є коловимШаблон:SfnШаблон:Sfn.
Примітки
Література
- Шаблон:Стаття
- Шаблон:Стаття
- Шаблон:Стаття
- Шаблон:Стаття
- Шаблон:Стаття
- Шаблон:Стаття. Як процитовано в Агеєва Шаблон:Harvard citation
- Шаблон:Стаття. Як процитовано в Агеєва Шаблон:Harvard citation
- Шаблон:Книга
- Шаблон:Стаття
- Шаблон:Стаття
- Шаблон:Стаття
- Шаблон:Книга
- Шаблон:Стаття
- Шаблон:Стаття
- Шаблон:Стаття
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга. Як процитовано в Шаблон:Harvnb.
- Шаблон:Книга
Посилання
- ↑ Шаблон:Harvnb. Для более ранних границ см. Шаблон:Harvnb, Шаблон:Harvnb и Шаблон:Harvnb.
- ↑ См. Шаблон:Harvnb для верхней границы и Шаблон:Harvnb графов, достигающих нижнюю границу. Карапетян Шаблон:Harvard citation и Шаблон:Harvard citation указали ранее более слабые границы для той же задачи.