Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Дугова діаграма це спосіб подання графа в якому вершини розташовуються вздовж прямої на евклідовій площині а ребра малюю

Дугова діаграма

Дугова діаграма

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

image
Дугова діаграма графа Голднера — Харарі. Червоний пунктирний відрізок показує, де можна розбити граф, щоб зробити його гамільтоновим.

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

Хір, Босток і Огіветскі написали, що дугові діаграми «не можуть виражати повної структури графа так само ефективно, як це робить двовимірне подання», але дає змогу простіше уявити багатовимірні дані, пов'язані з вершинами графів.

Планарні графи

image
Діаграма Фарея

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

Якщо граф намальовано без перетинів дуг у вигляді дугової діаграми, в якій кожне ребро подано одним півколом, малюнок є двосторінковим книжковим вкладенням, що можливо тільки для підгамільтонових графів, підмножини планарних графів. Наприклад, максимальний планарний граф має таке вкладення тоді й лише тоді, коли він містить гамільтонів цикл. Таким чином, негамільтонів максимальний планарний граф, такий як граф Голднера — Харарі, не може мати планарного вкладення з одним півколом на ребро. Перевірка, чи граф має дугову діаграму без перетинів цього типу (або, еквівалентно, книжкова товщина графа дорівнює двом), є NP-повною задачею.

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

Мінімізація перетинів

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

Кіміковський, Шоуп, Хе, Сікора та Врто обговорювали евристичні алгоритми пошуку дугових діаграм із кількома перетинами.

Орієнтація за годинниковою стрілкою

Для подання орієнтованих графів загальноприйнятим є напрямок дуг за годинниковою стрілкою, так що дуги, спрямовані зліва направо, малюються над прямою, а спрямовані справа наліво — під прямою. Цю домовленість про орієнтацію за годинниковою стрілкою розробила, як частину іншого способу подання графа, Фекет, Ванг, Данг і Аріс, а до дугових діаграм її застосували Преторіус і ван Вейк.

Інше використання

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

Примітки

  1. Wattenberg, 2002.
  2. Saaty, 1964.
  3. Nicholson, 1968.
  4. Masuda, Nakajima, Kashiwabara, Fujisawa, 1990.
  5. Heer, Bostock, Ogievetsky, 2010.
  6. Півкола для малювання ребер у книжковому вкладенні застосували вже Бернхарт і Кайнен 1979 року (Bernhart, Kainen, 1979), але явний зв'язок дугових діаграм із двосторінковими вкладеннями, очевидно, належить Масуді, Накаджимі, Кашивабарі і Фуджисаві (Masuda, Nakajima, Kashiwabara, Fujisawa, 1990).
  7. Chung, Leighton, Rosenberg, 1987.
  8. Giordano, Liotta, Mchedlidze, Symvonis, 2007.
  9. Bekos, Kaufmann, Kobourov, Symvonis, 2013.
  10. Efrat, Erten, Kobourov, 2007.
  11. Cimikowski, Mumey, 2007.
  12. Cimikowski, Shope, 1996.
  13. Cimikowski, 2002.
  14. He, Sýkora, Vrt'o, 2005.
  15. Fekete, Wang, Dang, Aris, 2003.
  16. Pretorius, van Wijk, 2007.
  17. Brandes, 1999.
  18. Djidjev, Vrt'o, 2002.

Література

  • Michael A. Bekos, Michael Kaufmann, Stephen G. Kobourov, Antonios Symvonis. Graph Drawing: 20th International Symposium, GD 2012, Redmond, WA, USA, September 19–21, 2012, Revised Selected Papers. — Springer, 2013. — Т. 7704. — С. 150–161. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-36763-2_14.
  • Frank R. Bernhart, Paul C. Kainen. The book thickness of a graph // . — 1979. — Т. 27, вип. 3. — С. 320–331. — (Series B). — DOI:10.1016/0095-8956(79)90021-2.
  • Ulrik Brandes. Graph Drawing: 7th International Symposium, GD’99, Štiřín Castle, Czech Republic September 15–19, 1999, Proceedings. — Springer, 1999. — Т. 1731. — С. 410–415. — (Lecture Notes in Computer Science) — DOI:10.1007/3-540-46648-7_42.
  • Fan R. K. Chung, Frank T. Leighton, Arnold L. Rosenberg. Embedding graphs in books: A layout problem with applications to VLSI design // SIAM Journal on Algebraic and Discrete Methods. — 1987. — Т. 8. — С. 33–58. — DOI:10.1137/0608002. з джерела 14 жовтня 2021. Процитовано 25 квітня 2022..
  • Robert Cimikowski. Algorithms for the fixed linear crossing number problem // Discrete Applied Mathematics. — 2002. — Т. 122. — С. 93–115. — DOI:10.1016/S0166-218X(01)00314-6.
  • Robert Cimikowski, Brendan Mumey. Approximating the fixed linear crossing number // Discrete Applied Mathematics. — 2007. — Т. 155. — С. 2202–2210. — DOI:10.1016/j.dam.2007.05.009.
  • Robert Cimikowski, Paul Shope. A neural-network algorithm for a graph layout problem // IEEE Transactions on Neural Networks. — 1996. — Т. 7. — С. 341–345. — DOI:10.1109/72.485670.
  • Hristo Djidjev, Imrich Vrt'o. Graph Drawing: 9th International Symposium, GD 2001, Vienna, Austria, September 23–26, 2001, Revised Papers. — Springer, 2002. — Т. 2265. — С. 96–101. — (Lecture Notes in Computer Science) — DOI:10.1007/3-540-45848-4_8..
  • Alon Efrat, Cesim Erten, Stephen G. Kobourov. Fixed-location circular arc drawing of planar graphs // . — 2007. — Т. 11. — С. 145–164. — DOI:10.7155/jgaa.00140.
  • Jean-Daniel Fekete, David Wang, Niem Dang, Aleks Aris, Catherine Plaisant. IEEE Symp. on Information Visualization, Poster Compendium. — 2003. — С. 82–83.
  • Francesco Giordano, Giuseppe Liotta, Tamara Mchedlidze, Antonios Symvonis. Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007, Proceedings. — Springer, 2007. — Т. 4835. — С. 172–183. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-540-77120-3_17.
  • Hongmei He, Ondrej Sýkora, Imrich Vrt'o. Crossing Minimisation Heuristics for 2-page Drawings // Electronic Notes in Discrete Mathematics. — 2005. — Т. 22. — С. 527–534. — DOI:10.1016/j.endm.2005.06.088.
  • Jeffrey Heer, Michael Bostock, Vadim Ogievetsky. A tour through the visualization zoo // Communications of the ACM. — 2010. — Т. 53. — С. 59–67. — DOI:10.1145/1743546.1743567.
  • Sumio Masuda, Kazuo Nakajima, Toshinobu Kashiwabara, Toshio Fujisawa. Crossing minimization in linear embeddings of graphs // . — 1990. — Т. 39. — С. 124–127. — DOI:10.1109/12.46286.
  • T. A. J. Nicholson. Permutation procedure for minimising the number of crossings in a network // Proceedings of the Institution of Electrical Engineers. — 1968. — Т. 115. — С. 21–26. — DOI:10.1049/piee.1968.0004.
  • A. J. Pretorius, J. J. van Wijk. Bridging the semantic gap: Visualizing transition graphs with user-defined diagrams // IEEE Computer Graphics and Applications. — 2007. — Т. 27. — С. 58–66. — DOI:10.1109/MCG.2007.121.
  • Thomas L. Saaty. The minimum number of intersections in complete graphs // Proceedings of the National Academy of Sciences of the United States of America. — 1964. — Т. 52. — С. 688–690. — DOI:10.1073/pnas.52.3.688.
  • M. Wattenberg. Proc. IEEE Symposium o nInformation Visualization (INFOVIS 2002). — 2002. — С. 110–116. — DOI:10.1109/INFVIS.2002.1173155.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Dugova diagrama ce sposib podannya grafa v yakomu vershini roztashovuyutsya vzdovzh pryamoyi na evklidovij ploshini a rebra malyuyutsya u viglyadi pivkil na odnij z dvoh pivploshin abo u viglyadi gladkih krivih utvorenih pivkolami U deyakih vipadkah yaksho rebra z yednuyut susidni vershini na pryamij yih zobrazhayut vidrizkami pryamoyi Dugova diagrama grafa Goldnera Harari Chervonij punktirnij vidrizok pokazuye de mozhna rozbiti graf shob zrobiti jogo gamiltonovim Nazva dugova diagrama dlya takogo podannya grafiv pohodit vid vikoristannya podibnogo tipu diagram Vattenberga yaki vin vikoristovuvav dlya vizualizaciyi povtoryuvanih fragmentiv ryadkiv z yednuyuchi pari odnakovih pidryadkiv Prote sam stil podannya grafa znachno starshij za nazvu i datuyetsya robotami Saati i Nikolsona yaki vikoristovuvali dugovi diagrami dlya vivchennya chisla shreshen grafiv Starisha ale ridshe vikoristovuvana nazva dugovih diagram linijne vkladennya Hir Bostok i Ogivetski napisali sho dugovi diagrami ne mozhut virazhati povnoyi strukturi grafa tak samo efektivno yak ce robit dvovimirne podannya ale daye zmogu prostishe uyaviti bagatovimirni dani pov yazani z vershinami grafiv Planarni grafiDiagrama Fareya Yak zauvazhiv Nikolson bud yake vkladennya grafa v ploshinu mozhna peretvoriti na dugovu diagramu ne zminivshi chisla peretiniv Zokrema bud yakij planarnij graf maye planarnu dugovu diagramu Odnak take vkladennya mozhe vimagati vikoristannya bilsh nizh odnogo pivkola dlya malyuvannya deyakih reber grafa Yaksho graf namalovano bez peretiniv dug u viglyadi dugovoyi diagrami v yakij kozhne rebro podano odnim pivkolom malyunok ye dvostorinkovim knizhkovim vkladennyam sho mozhlivo tilki dlya pidgamiltonovih grafiv pidmnozhini planarnih grafiv Napriklad maksimalnij planarnij graf maye take vkladennya todi j lishe todi koli vin mistit gamiltoniv cikl Takim chinom negamiltoniv maksimalnij planarnij graf takij yak graf Goldnera Harari ne mozhe mati planarnogo vkladennya z odnim pivkolom na rebro Perevirka chi graf maye dugovu diagramu bez peretiniv cogo tipu abo ekvivalentno knizhkova tovshina grafa dorivnyuye dvom ye NP povnoyu zadacheyu Odnak bud yakij planarnij graf maye dugovu diagramu v yakij kozhne rebro podano u viglyadi bidugi sho skladayetsya ne bilshe nizh z dvoh pivkil Strogishe bud yakij st planarnij oriyentovanij graf planarnij spryamovanij aciklichnij graf z odnim vitokom i odnim stokom obidva na zovnishnij grani maye dugovu diagramu v yakij bud yake rebro utvoryuye monotonnu krivu vsi krivi rebra napravleni v odin bik Dlya neoriyentovanih planarnih grafiv odnim zi sposobiv pobudovi dugovoyi diagrami maksimum z dvoma pivkolami na rebro ye podil grafa ta dodannya dodatkovih reber z metoyu otrimati gamiltoniv cikl pri comu rebra dilyatsya maksimum na dvi chastini potim vikoristovuyetsya poryadok uzdovzh gamiltonovogo ciklu yak poryadok prohodzhennya vershin na pryamij Minimizaciya peretinivOskilki perevirka chi maye danij graf dugovu diagramu bez peretiniv z odnim pivkolom na rebro ye NP povnoyu zadacheyu takozh NP skladnoyu zadacheyu ye poshuk dugovoyi diagrami sho minimizuye chislo peretiniv Zavdannya minimizaciyi chisla peretiniv zalishayetsya NP skladnoyu dlya neplanarnih grafiv navit yaksho poryadok vershin uzdovzh pryamoyi vzhe zadano Odnak u razi zadanogo poryadku vershin vkladennya bez peretiniv yaksho take isnuye mozhna znajti za polinomialnij chas perevivshi zadachu v zadachu en v yakij zminni podayut roztashuvannya kozhnoyi dugi a obmezhennya zapobigayut roztashuvannyu dvoh reber sho peretinayutsya po odin bik vid pryamoyi z vershinami Krim togo u razi fiksovanogo roztashuvannya vershin vkladennya z minimizaciyeyu chisla peretiniv mozhna aproksimuvati rozv yazavshi zadachu v dopomizhnomu grafi yakij podaye pivkola ta yih potencijni peretini Kimikovskij Shoup He Sikora ta Vrto obgovoryuvali evristichni algoritmi poshuku dugovih diagram iz kilkoma peretinami Oriyentaciya za godinnikovoyu strilkoyuDlya podannya oriyentovanih grafiv zagalnoprijnyatim ye napryamok dug za godinnikovoyu strilkoyu tak sho dugi spryamovani zliva napravo malyuyutsya nad pryamoyu a spryamovani sprava nalivo pid pryamoyu Cyu domovlenist pro oriyentaciyu za godinnikovoyu strilkoyu rozrobila yak chastinu inshogo sposobu podannya grafa Feket Vang Dang i Aris a do dugovih diagram yiyi zastosuvali Pretorius i van Vejk Inshe vikoristannyaBrandes vikoristovuvav dugovi diagrami dlya vizualizaciyi diagram staniv zsuvovogo registra a Dzhidzhev i Vrto dlya dovedennya sho chislo peretiniv bud yakogo grafa prinajmni dorivnyuye kvadratu jogo shirini rozrizu PrimitkiWattenberg 2002 Saaty 1964 Nicholson 1968 Masuda Nakajima Kashiwabara Fujisawa 1990 Heer Bostock Ogievetsky 2010 Pivkola dlya malyuvannya reber u knizhkovomu vkladenni zastosuvali vzhe Bernhart i Kajnen 1979 roku Bernhart Kainen 1979 ale yavnij zv yazok dugovih diagram iz dvostorinkovimi vkladennyami ochevidno nalezhit Masudi Nakadzhimi Kashivabari i Fudzhisavi Masuda Nakajima Kashiwabara Fujisawa 1990 Chung Leighton Rosenberg 1987 Giordano Liotta Mchedlidze Symvonis 2007 Bekos Kaufmann Kobourov Symvonis 2013 Efrat Erten Kobourov 2007 Cimikowski Mumey 2007 Cimikowski Shope 1996 Cimikowski 2002 He Sykora Vrt o 2005 Fekete Wang Dang Aris 2003 Pretorius van Wijk 2007 Brandes 1999 Djidjev Vrt o 2002 LiteraturaMichael A Bekos Michael Kaufmann Stephen G Kobourov Antonios Symvonis Graph Drawing 20th International Symposium GD 2012 Redmond WA USA September 19 21 2012 Revised Selected Papers Springer 2013 T 7704 S 150 161 Lecture Notes in Computer Science DOI 10 1007 978 3 642 36763 2 14 Frank R Bernhart Paul C Kainen The book thickness of a graph 1979 T 27 vip 3 S 320 331 Series B DOI 10 1016 0095 8956 79 90021 2 Ulrik Brandes Graph Drawing 7th International Symposium GD 99 Stirin Castle Czech Republic September 15 19 1999 Proceedings Springer 1999 T 1731 S 410 415 Lecture Notes in Computer Science DOI 10 1007 3 540 46648 7 42 Fan R K Chung Frank T Leighton Arnold L Rosenberg Embedding graphs in books A layout problem with applications to VLSI design SIAM Journal on Algebraic and Discrete Methods 1987 T 8 S 33 58 DOI 10 1137 0608002 z dzherela 14 zhovtnya 2021 Procitovano 25 kvitnya 2022 Robert Cimikowski Algorithms for the fixed linear crossing number problem Discrete Applied Mathematics 2002 T 122 S 93 115 DOI 10 1016 S0166 218X 01 00314 6 Robert Cimikowski Brendan Mumey Approximating the fixed linear crossing number Discrete Applied Mathematics 2007 T 155 S 2202 2210 DOI 10 1016 j dam 2007 05 009 Robert Cimikowski Paul Shope A neural network algorithm for a graph layout problem IEEE Transactions on Neural Networks 1996 T 7 S 341 345 DOI 10 1109 72 485670 Hristo Djidjev Imrich Vrt o Graph Drawing 9th International Symposium GD 2001 Vienna Austria September 23 26 2001 Revised Papers Springer 2002 T 2265 S 96 101 Lecture Notes in Computer Science DOI 10 1007 3 540 45848 4 8 Alon Efrat Cesim Erten Stephen G Kobourov Fixed location circular arc drawing of planar graphs 2007 T 11 S 145 164 DOI 10 7155 jgaa 00140 Jean Daniel Fekete David Wang Niem Dang Aleks Aris Catherine Plaisant IEEE Symp on Information Visualization Poster Compendium 2003 S 82 83 Francesco Giordano Giuseppe Liotta Tamara Mchedlidze Antonios Symvonis Algorithms and Computation 18th International Symposium ISAAC 2007 Sendai Japan December 17 19 2007 Proceedings Springer 2007 T 4835 S 172 183 Lecture Notes in Computer Science DOI 10 1007 978 3 540 77120 3 17 Hongmei He Ondrej Sykora Imrich Vrt o Crossing Minimisation Heuristics for 2 page Drawings Electronic Notes in Discrete Mathematics 2005 T 22 S 527 534 DOI 10 1016 j endm 2005 06 088 Jeffrey Heer Michael Bostock Vadim Ogievetsky A tour through the visualization zoo Communications of the ACM 2010 T 53 S 59 67 DOI 10 1145 1743546 1743567 Sumio Masuda Kazuo Nakajima Toshinobu Kashiwabara Toshio Fujisawa Crossing minimization in linear embeddings of graphs 1990 T 39 S 124 127 DOI 10 1109 12 46286 T A J Nicholson Permutation procedure for minimising the number of crossings in a network Proceedings of the Institution of Electrical Engineers 1968 T 115 S 21 26 DOI 10 1049 piee 1968 0004 A J Pretorius J J van Wijk Bridging the semantic gap Visualizing transition graphs with user defined diagrams IEEE Computer Graphics and Applications 2007 T 27 S 58 66 DOI 10 1109 MCG 2007 121 Thomas L Saaty The minimum number of intersections in complete graphs Proceedings of the National Academy of Sciences of the United States of America 1964 T 52 S 688 690 DOI 10 1073 pnas 52 3 688 M Wattenberg Proc IEEE Symposium o nInformation Visualization INFOVIS 2002 2002 S 110 116 DOI 10 1109 INFVIS 2002 1173155

Дата публікації:
Топ