Колова схема

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

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

Застосування[ред. | ред. код]

Колова схема добре підходить для мережевих топологій зв'язку, таких як зірка або кільце[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