Вікіпедія

Колова схема

зображення графа з вершинами на колі

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

Колова схема графа Хватала
Колова схема діаграми станів для протоколу граничного шлюзу
Послідовна побудова колової схеми моделі Барабаші — Альберт формування соціальної мережі

Застосування ред.

Колова схема добре підходить для мережевих топологій зв'язку, таких як зірка або кільце[1], а також циклічних частин метаболічних мереж[2]. Для графів із відомим гамільтоновим циклом колова схема дозволяє зобразити цикл у вигляді кола; таке колова схема утворює базис для LCF-коду гамільтонових кубічних графів[3].

Колова схема можна використати для візуалізації повного графа, а також фрагментів, таких як кластери вершин графа, двозв'язні компоненти[1][4], кластери генів у графі взаємодії генів[5] або природні підгрупи в соціальній мережі[6]. Використовуючи кілька кіл з вершинами графів, можна застосовувати й інші методи розташування кластерів, такі як силові алгоритми візуалізації[7].

Перевага колової схеми в таких галузях, як біоінформатика або візуалізація соціальних мереж, полягає в його візуальній нейтральності[8]: за розташування всіх вершин на рівній відстані одна від одної й від центру малюнка жоден з вузлів не займає центрального привілейованого становища. Це важливо, оскільки є психологічна тенденція сприймати близькі до центру вузли як найважливіші[9].

Стиль ребер ред.

Ребра на зображенні графа можуть бути хордами кола[10], дугами кіл[11] (можливо перпендикулярні до кола в точці, так що ребра моделі розташовуються як прямі в моделі Пуанкаре гіперболічної геометрії) або кривими інших типів[12].

Візуальну відмінність між внутрішньою та зовнішньою частинами кола в коловій схемі можна використати для розділення двох типів зображення ребер. Наприклад, алгоритм колового малювання Ганснера та Корена[12] використовує групування ребер усередині кола разом з деякими незгрупованими ребрами поза колом[12].

Для колової схеми регулярних графів із ребрами, намальованими всередині і поза колом як дуги, кути падіння (кут із дотичною в точці) з обох боків дуги однакові, що спрощує оптимізацію кутової роздільності малюнка[11].

Число схрещень ред.

Деякі автори вивчають задачу пошуку перестановки вершин колової схеми, яка мінімізує число схрещень, коли всі ребра малюються всередині кола. Це число схрещень дорівнює нулю лише для зовніпланарних графів[10][13]. Для інших графів його можна оптимізувати або скоротити окремо для кожної двозв'язної компоненти графа перед формуванням розв'язку, оскільки такі компоненти можна намалювати без взаємодії між ними[13].

У загальному випадку мінімізація числа схрещень є NP-повною задачею[14], але її можна апроксимувати з коефіцієнтом  , де   — число вершин[15]. Розроблено також евристичні методи скорочення складності, наприклад, засновані на продуманому порядку вставляння вершин та на локальній оптимізації[16][1][10][17][13].

Колову схему можна використати для максимізації числа схрещень. Зокрема, вибір випадкової перестановки вершин приводить до того, що схрещування відбувається з імовірністю 1/3, так що очікуване число схрещень становить близько третини від найбільшої кількості схрещень серед усіх можливих розташувань вершин. Дерандомізація цього методу дає детермінований апроксимаційний алгоритм із коефіцієнтом апроксимації, рівним трьом[18].

Інші критерії оптимальності ред.

Також із коловою схемою пов'язані задачі оптимізації довжини ребер колової схеми, кутової роздільності схрещень або ширини розрізу (найбільшої кількості ребер, які з'єднують протилежні дуги кола)[16][12][19][20], проте, багато з цих задач NP-повні[16].

Див. також ред.

  • Хордова діаграма — концепція візуалізації інформації, тісно пов'язана з коловим розташуванням.
  • Planarity[en] — комп'ютерна гра, в якій гравець має пересувати вершини випадково згенерованого планарного графа з коловим розташуванням, щоб розплутати малюнок.

Примітки ред.

  1. ↑ а б в Doğrusöz, Madden, Madden, 1997.
  2. ↑ Becker, Rojas, 2001.
  3. ↑ Pisanski, Servatius, 2013.
  4. ↑ Six, Tollis, 1999b.
  5. ↑ Symeonidis, Tollis, 2004.
  6. ↑ Krebs, 1996.
  7. ↑ Doğrusöz, Belviranli, Dilek, 2012.
  8. ↑ Iragne, Nikolski, Mathieu, Auber, Sherman, 2005.
  9. ↑ Huang, Hong, Eades, 2007.
  10. ↑ а б в Six, Tollis, 1999a.
  11. ↑ а б Duncan, Eppstein, Goodrich, Kobourov, Nöllenburg, 2012.
  12. ↑ а б в г Gansner, Koren, 2007.
  13. ↑ а б в Baur, Brandes, 2005.
  14. ↑ Masuda, Kashiwabara, Nakajima, Fujisawa, 1987.
  15. ↑ Shahrokhi, Sýkora, Székely, Vrt'o, 1995.
  16. ↑ а б в Mäkinen, 1988.
  17. ↑ He, Sýkora, 2004.
  18. ↑ Verbitsky, 2008.
  19. ↑ Nguyen, Eades, Hong, Huang, 2011.
  20. ↑ Dehkordi, Nguyen, Eades, Hong, 2013.

Література ред.

Отримано з https://uk.wikipedia.org/w/index.php?title=Колова_схема&oldid=39292569