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

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

Багато інших задач, які NP-повні на графах загального вигляду, мають алгоритми поліноміального часу, якщо обмежитися коловими графами. Наприклад, Клокс показав, що деревну ширину колового графа можна визначити, а оптимальне дерево декомпозиції побудувати за час O(n3). Крім того, найменше заміщення (тобто хордальний граф з якомога меншим числом ребер, що містить даний коловий граф як підграф) можна знайти за час O(n3). Тіскін показав, що найбільшу кліку колового графа можна знайти за час O(n log2 n), а Неш і Грегг показали, що найбільшу незалежну множину незваженого колового графа можна знайти за час O(n min{d, α}), де d — параметр графа, відомий як щільність, а α — число незалежності колового графа.

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

Хроматичне число

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

Деякі автори досліджували задачу розфарбовування обмежених підкласів колових графів малим числом кольорів. Зокрема, колові графи, в яких немає множин з k і більше хорд, в яких всі хорди перетинають одна одну, можна розфарбувати, не перевищуючи кольорів. Для более ранних границ см. , и .. Зокрема, при k = 3 (тобто для колових графів без трикутників) хроматичне число не перевищує п'яти, і ця межа точна — всі колові графи без трикутників можна розфарбувати в п'ять кольорів і існують колові графи без трикутників, що вимагають п'яти кольорів для розфарбовуванняСм. для верхней границы и графов, достигающих нижнюю границу. Карапетян и указали ранее более слабые границы для той же задачи.. Якщо коловий граф має обхват щонайменше п'ять (тобто в ньому немає трикутників і циклів з чотирма вершинами), його можна розфарбувати, обмежившись трьома кольорами. Задача розфарбовування рамкових графів без трикутників еквівалентна задачі подання рамкових графів у вигляді графа, ізометричного прямому добутку дерев. У цій відповідності задач число кольорів у розфарбуванні відповідає числу дерев у добутку.

Застосування Колові графи з'являються під час проєктування НВІС як абстракція окремого випадку трасування друкованих плат, відомого як «двополюсне трасування перетинів каналів». У цьому випадку ділянка трасування є прямокутником, усі мережі є двополюсниками, а виводи розташовуються по периметру прямокутника. Легко бачити, що граф перетинів цієї мережі є коловим графом. Одна з цілей трасування — забезпечення відсутності електричного контакту між різними мережами та розташування можливих перетинних частин на різних шарах. Таким чином, колові графи охоплюють частину задач трасування.

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

Пов'язані класи графів Граф перетинів множини інтервалів на прямій називається інтервальним графом.

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

Струнні графи, графи перетинів кривих на площині, включають колові графи як окремий випадок.

Будь-який дистанційно-успадковуваний граф є коловим графом, як і будь-який граф перестановки або індиферентний граф. Будь-який зовніпланарний граф також є коловим.

Примітки

Література

. Як процитовано в Агеєва . Як процитовано в Агеєва

. Як процитовано в .

Посилання