Дугова діаграма Дугова діаграма — це спосіб подання графа, в якому вершини розташовуються вздовж прямої на евклідовій площині, а ребра малюються у вигляді півкіл на одній з двох півплощин, або у вигляді гладких кривих, утворених півколами. У деяких випадках, якщо ребра з'єднують сусідні вершини на прямій, їх зображають відрізками прямої. Назва «дугова діаграма» для такого подання графів походить від використання подібного типу діаграм Ваттенберга[1], які він використовував для візуалізації повторюваних фрагментів рядків, з'єднуючи пари однакових підрядків. Проте, сам стиль подання графа значно старший за назву і датується роботами Сааті[2] і Нікольсона[3], які використовували дугові діаграми для вивчення числа схрещень графів. Старіша, але рідше використовувана назва дугових діаграм — лінійне вкладення[4]. Хір, Босток і Огіветскі[5] написали, що дугові діаграми «не можуть виражати повної структури графа так само ефективно, як це робить двовимірне подання», але дає змогу простіше уявити багатовимірні дані, пов'язані з вершинами графів. Планарні графи Як зауважив Ніколсон[3], будь-яке вкладення графа в площину можна перетворити на дугову діаграму, не змінивши числа перетинів. Зокрема, будь-який планарний граф має планарну дугову діаграму. Однак таке вкладення може вимагати використання більш ніж одного півкола для малювання деяких ребер графа. Якщо граф намальовано без перетинів дуг у вигляді дугової діаграми, в якій кожне ребро подано одним півколом, малюнок є двосторінковим книжковим вкладенням, що можливо тільки для підгамільтонових графів, підмножини планарних графів[6]. Наприклад, максимальний планарний граф має таке вкладення тоді й лише тоді, коли він містить гамільтонів цикл. Таким чином, негамільтонів максимальний планарний граф, такий як граф Голднера — Харарі, не може мати планарного вкладення з одним півколом на ребро. Перевірка, чи граф має дугову діаграму без перетинів цього типу (або, еквівалентно, книжкова товщина графа дорівнює двом), є NP-повною задачею[7]. Однак будь-який планарний граф має дугову діаграму, в якій кожне ребро подано у вигляді бідуги, що складається не більше ніж з двох півкіл. Строгіше, будь-який st-планарний орієнтований граф (планарний спрямований ациклічний граф з одним витоком і одним стоком, обидва на зовнішній грані) має дугову діаграму, в якій будь-яке ребро утворює монотонну криву, всі криві (ребра) направлені в один бік[8]. Для неорієнтованих планарних графів одним зі способів побудови дугової діаграми максимум з двома півколами на ребро є поділ графа та додання додаткових ребер з метою отримати гамільтонів цикл (при цьому ребра діляться максимум на дві частини), потім використовується порядок уздовж гамільтонового циклу як порядок проходження вершин на прямій[9]. Мінімізація перетинівОскільки перевірка, чи має даний граф дугову діаграму без перетинів з одним півколом на ребро, є NP-повною задачею, також NP-складною задачею є пошук дугової діаграми, що мінімізує число перетинів. Завдання мінімізації числа перетинів залишається NP-складною для непланарних графів, навіть якщо порядок вершин уздовж прямої вже задано[4]. Однак, у разі заданого порядку вершин, вкладення без перетинів (якщо таке існує) можна знайти за поліноміальний час, перевівши задачу в задачу 2-виконанності[en], в якій змінні подають розташування кожної дуги, а обмеження запобігають розташуванню двох ребер, що перетинаються, по один бік від прямої з вершинами[10]. Крім того, у разі фіксованого розташування вершин, вкладення з мінімізацією числа перетинів можна апроксимувати, розв'язавши задачу максимального розрізу в допоміжному графі, який подає півкола та їх потенційні перетини[11]. Кіміковський, Шоуп[12][13], Хе, Сікора та Врто[14] обговорювали евристичні алгоритми пошуку дугових діаграм із кількома перетинами. Орієнтація за годинниковою стрілкоюДля подання орієнтованих графів загальноприйнятим є напрямок дуг за годинниковою стрілкою, так що дуги, спрямовані зліва направо, малюються над прямою, а спрямовані справа наліво — під прямою. Цю домовленість про орієнтацію за годинниковою стрілкою розробила, як частину іншого способу подання графа, Фекет, Ванг, Данг і Аріс[15], а до дугових діаграм її застосували Преторіус і ван Вейк[16]. Інше використанняБрандес[17] використовував дугові діаграми для візуалізації діаграм станів зсувового регістра, а Джиджев і Врто[18] — для доведення, що число перетинів будь-якого графа принаймні дорівнює квадрату його ширини розрізу. Примітки
Література
|
Portal di Ensiklopedia Dunia
