Колова схема
Колова́ схе́ма — стиль візуалізації графів, у якому вершини графа розташовуються на колі, здебільшого рівномірно, отже утворюють вершини правильного многокутника.
Застосування
Колова схема добре підходить для мережевих топологій зв'язку, таких як зірка або кільцеШаблон:Sfn, а також циклічних частин метаболічних мережШаблон:Sfn. Для графів із відомим гамільтоновим циклом колова схема дозволяє зобразити цикл у вигляді кола; таке колова схема утворює базис для LCF-коду гамільтонових кубічних графівШаблон:Sfn.
Колова схема можна використати для візуалізації повного графа, а також фрагментів, таких як кластери вершин графа, двозв'язні компонентиШаблон:SfnШаблон:Sfn, кластери генів у графі взаємодії генівШаблон:Sfn або природні підгрупи в соціальній мережіШаблон:Sfn. Використовуючи кілька кіл з вершинами графів, можна застосовувати й інші методи розташування кластерів, такі як силові алгоритми візуалізаціїШаблон:Sfn.
Перевага колової схеми в таких галузях, як біоінформатика або візуалізація соціальних мереж, полягає в його візуальній нейтральностіШаблон:Sfn: за розташування всіх вершин на рівній відстані одна від одної й від центру малюнка жоден з вузлів не займає центрального привілейованого становища. Це важливо, оскільки є психологічна тенденція сприймати близькі до центру вузли як найважливішіШаблон:Sfn.
Стиль ребер
Ребра на зображенні графа можуть бути хордами колаШаблон:Sfn, дугами кілШаблон:Sfn (можливо перпендикулярні до кола в точці, так що ребра моделі розташовуються як прямі в моделі Пуанкаре гіперболічної геометрії) або кривими інших типівШаблон:Sfn.
Візуальну відмінність між внутрішньою та зовнішньою частинами кола в коловій схемі можна використати для розділення двох типів зображення ребер. Наприклад, алгоритм колового малювання Ганснера та КоренаШаблон:Sfn використовує групування ребер усередині кола разом з деякими незгрупованими ребрами поза коломШаблон:Sfn.
Для колової схеми регулярних графів із ребрами, намальованими всередині і поза колом як дуги, кути падіння (кут із дотичною в точці) з обох боків дуги однакові, що спрощує оптимізацію кутової роздільності малюнкаШаблон:Sfn.
Число схрещень
Деякі автори вивчають задачу пошуку перестановки вершин колової схеми, яка мінімізує число схрещень, коли всі ребра малюються всередині кола. Це число схрещень дорівнює нулю лише для зовніпланарних графівШаблон:SfnШаблон:Sfn. Для інших графів його можна оптимізувати або скоротити окремо для кожної двозв'язної компоненти графа перед формуванням розв'язку, оскільки такі компоненти можна намалювати без взаємодії між нимиШаблон:Sfn.
У загальному випадку мінімізація числа схрещень є NP-повною задачеюШаблон:Sfn, але її можна апроксимувати з коефіцієнтом , де — число вершинШаблон:Sfn. Розроблено також евристичні методи скорочення складності, наприклад, засновані на продуманому порядку вставляння вершин та на локальній оптимізаціїШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn.
Колову схему можна використати для максимізації числа схрещень. Зокрема, вибір випадкової перестановки вершин приводить до того, що схрещування відбувається з імовірністю 1/3, так що очікуване число схрещень становить близько третини від найбільшої кількості схрещень серед усіх можливих розташувань вершин. Дерандомізація цього методу дає детермінований апроксимаційний алгоритм із коефіцієнтом апроксимації, рівним трьомШаблон:Sfn.
Інші критерії оптимальності
Також із коловою схемою пов'язані задачі оптимізації довжини ребер колової схеми, кутової роздільності схрещень або ширини розрізу (найбільшої кількості ребер, які з'єднують протилежні дуги кола)Шаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn, проте, багато з цих задач NP-повніШаблон:Sfn.
Див. також
- Хордова діаграма — концепція візуалізації інформації, тісно пов'язана з коловим розташуванням.
- Шаблон:Не перекладено — комп'ютерна гра, в якій гравець має пересувати вершини випадково згенерованого планарного графа з коловим розташуванням, щоб розплутати малюнок.