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

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

Цілком упорядковуваний граф

Цілком упорядковуваний граф

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

Визначення

Алгоритм жадібного розфарбовування, коли він застосовується до заданого упорядкування вершин графу G, розглядає послідовно вершини графу (згідно з порядком) і призначає кожній вершині перший доступний колір. Різні упорядкування вершин можуть приводити до різного числа необхідних кольорів. Завжди існує впорядкування, яке веде до оптимального розфарбування — це істинне, наприклад, при упорядкуванні вершин за кольорами оптимального розфарбування, але таке впорядкування, іноді, складно знайти. Цілком упорядковувані графи, за визначенням, це графи, для яких існує впорядкування, оптимальне для алгоритму жадібного розфарбовування не тільки для самого графу, але й для всіх його породжених підграфів.

Формальніше, кажуть, що граф G цілком упорядковуваний, якщо існує впорядкування π вершин графу G, таке, що будь-який породжений підграф графу G оптимально розфарбовується алгоритмом жадібного розфарбовування за використання підпослідовності упорядкування π, породженої вершинами підграфу. Впорядкування π має цю властивість точно тоді, коли не існує чотирьох вершин a, b, c і d, для яких abcd є породженим підграфом, у якому a стоїть перед b (в упорядкуванні), а c стоїть після d.

Обчислювальна складність

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

Пов'язані класи графів

Будь-який цілком упорядковуваний граф є досконалим.

Хордальні графи є цілком упорядковуваними. Досконалий порядок хордальних графів можна знайти обернення упорядкування досконалого виключення для графу. Таким чином, застосування алгоритму жадібного розфарбовування до досконалого упорядкування забезпечує ефективний алгоритм розфарбовування хордальних графів. Графи порівнянності також є цілком упорядковуваними, де досконале впорядкування визначається топологічним порядком транзитивної орієнтації графу.

Ще один клас цілком упорядковуваних графів складається з графів G, таких, що в будь-якій підмножині з п'яти вершин з графу G щонайменше одна з п'яти вершин має замкнутий окіл, який є підмножиною (або дорівнює) замкнутим околам інших вершин з п'ятірки. Еквівалентно, це графи, в яких частковий порядок замкнутих околів, який визначається включенням множин, має ширину, яка не перевищує 4. Граф-цикл із 5 вершинами має ширину часткового порядку околів, рівну п'яти, так що число чотири є максимальною шириною, що забезпечує досконале впорядкування. Як і в разі хордальних графів (але, в загальному випадку, не для цілком упорядковуваних графів узагалі) графи з шириною чотири розпізнаються за поліноміальний час.

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

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

Відомі деякі інші класи цілком упорядковуваних графів.

Примітки

  1. Chvátal, 1984.
  2. Maffray, 2003.
  3. Middendorf, Pfeiffer, 1990.
  4. Payan, 1983.
  5. Felsner, Raghavan, Spinrad, 2003.
  6. Hoàng, Reed, 1989.
  7. Brandstädt, Le, Spinrad, 1999, с. 70, 82.
  8. Brandstädt, Le, Spinrad, 1999, с. 71, Theorem 5.2.4.
  9. Christen, Selkow, 1979.
  10. Chvátal, Hoàng, Mahadev, De Werra, 1987.
  11. Hoàng, Maffray, Olariu, Preissmann, 1992.
  12. Brandstädt, Le, Spinrad, 1999, с. 81–86.

Література

  • Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Graph Classes: A Survey. — SIAM Monographs on Discrete Mathematics and Applications, 1999. — .
  • Claude A. Christen, Stanley M. Selkow. Some perfect coloring properties of graphs // . — 1979. — Т. 27, вип. 1. — С. 49–59. — (Series B). — DOI:10.1016/0095-8956(79)90067-4.
  • Václav Chvátal. Topics in Perfect Graphs / Claude Berge, Václav Chvátal. — Amsterdam : North-Holland, 1984. — Т. 21. — С. 63–68. — (Annals of Discrete Mathematics). Як процитовано в Маффрея (Maffray, (2003)).
  • Václav Chvátal, Chính T. Hoàng, N. V. R. Mahadev, D. De Werra. Four classes of perfectly orderable graphs // Journal of Graph Theory. — 1987. — Т. 11, вип. 4. — С. 481–495. — DOI:10.1002/jgt.3190110405..
  • F. F. Dragan, F. Nicolai. LexBFS-orderings of distance-hereditary graphs. — (Schriftenreihe des Fachbereichs Mathematik der Univ. Duisburg SM-DU-303). Як процитовано в Бранштедта (Brandstädt, Le та Spinrad, (1999)).
  • Stefan Felsner, Vijay Raghavan, Jeremy Spinrad. Recognition algorithms for orders of small width and graphs of small Dilworth number // . — 2003. — Т. 20, вип. 4. — С. 351–364 (2004). — DOI:10.1023/B:ORDE.0000034609.99940.fb..
  • Chính T. Hoàng, Frédéric Maffray, Stephan Olariu, Myriam Preissmann. A charming class of perfectly orderable graphs // . — 1992. — Т. 102, вип. 1. — С. 67–74. — DOI:10.1016/0012-365X(92)90348-J..
  • Chính T. Hoàng, Bruce A. Reed. Some classes of perfectly orderable graphs // Journal of Graph Theory. — 1989. — Т. 13, вип. 4. — С. 445–463. — DOI:10.1002/jgt.3190130407..
  • Frédéric Maffray. Recent Advances in Algorithms and Combinatorics / Bruce A. Reed, Cláudia L. Sales. — Springer-Verlag, 2003. — Т. 11. — С. 65–84. — (CMS Books in Mathematics) — . — DOI:10.1007/0-387-22444-0_3..
  • Matthias Middendorf, Frank Pfeiffer. On the complexity of recognizing perfectly orderable graphs // . — 1990. — Т. 80, вип. 3. — С. 327–333. — DOI:10.1016/0012-365X(90)90251-C..
  • Charles Payan. Perfectness and Dilworth number // . — 1983. — Т. 44, вип. 2. — С. 229–230. — DOI:10.1016/0012-365X(83)90064-X..

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

U teoriyi grafiv cilkom uporyadkovuvanij graf ce graf vershini yakogo mozhna vporyadkuvati tak sho algoritm zhadibnogo rozfarbovuvannya z cim uporyadkuvannyam optimalno rozfarbovuye bud yakij porodzhenij pidgraf danogo grafu Vidpovidne vporyadkuvannya nazivayetsya doskonalim Cilkom uporyadkovuvani grafi utvoryuyut pidklas doskonalih grafiv i v cej pidklas vhodyat hordalni grafi grafi porivnyannosti i distancijno uspadkovuvani grafi Odnak perevirka chi ye graf cilkom uporyadkovuvanim ye NP povnoyu zadacheyu ViznachennyaAlgoritm zhadibnogo rozfarbovuvannya koli vin zastosovuyetsya do zadanogo uporyadkuvannya vershin grafu G rozglyadaye poslidovno vershini grafu zgidno z poryadkom i priznachaye kozhnij vershini pershij dostupnij kolir Rizni uporyadkuvannya vershin mozhut privoditi do riznogo chisla neobhidnih koloriv Zavzhdi isnuye vporyadkuvannya yake vede do optimalnogo rozfarbuvannya ce istinne napriklad pri uporyadkuvanni vershin za kolorami optimalnogo rozfarbuvannya ale take vporyadkuvannya inodi skladno znajti Cilkom uporyadkovuvani grafi za viznachennyam ce grafi dlya yakih isnuye vporyadkuvannya optimalne dlya algoritmu zhadibnogo rozfarbovuvannya ne tilki dlya samogo grafu ale j dlya vsih jogo porodzhenih pidgrafiv Formalnishe kazhut sho graf G cilkom uporyadkovuvanij yaksho isnuye vporyadkuvannya p vershin grafu G take sho bud yakij porodzhenij pidgraf grafu G optimalno rozfarbovuyetsya algoritmom zhadibnogo rozfarbovuvannya za vikoristannya pidposlidovnosti uporyadkuvannya p porodzhenoyi vershinami pidgrafu Vporyadkuvannya p maye cyu vlastivist tochno todi koli ne isnuye chotiroh vershin a b c i d dlya yakih abcd ye porodzhenim pidgrafom u yakomu a stoyit pered b v uporyadkuvanni a c stoyit pislya d Obchislyuvalna skladnistRozpiznavannya cilkom uporyadkovuvanih grafiv ye NP povnoyu zadacheyu Odnak legko pereviriti chi ye konkretne uporyadkuvannya doskonalim tobto chi zadovolnyaye vimogam cilkom uporyadkovuvanosti grafu Otzhe ye NP skladnoyu zadacheyu poshuk doskonalogo uporyadkuvannya grafu navit yaksho zazdalegid vidomo sho graf cilkom uporyadkovuvanij Pov yazani klasi grafivBud yakij cilkom uporyadkovuvanij graf ye doskonalim Hordalni grafi ye cilkom uporyadkovuvanimi Doskonalij poryadok hordalnih grafiv mozhna znajti obernennya uporyadkuvannya doskonalogo viklyuchennya dlya grafu Takim chinom zastosuvannya algoritmu zhadibnogo rozfarbovuvannya do doskonalogo uporyadkuvannya zabezpechuye efektivnij algoritm rozfarbovuvannya hordalnih grafiv Grafi porivnyannosti takozh ye cilkom uporyadkovuvanimi de doskonale vporyadkuvannya viznachayetsya topologichnim poryadkom tranzitivnoyi oriyentaciyi grafu She odin klas cilkom uporyadkovuvanih grafiv skladayetsya z grafiv G takih sho v bud yakij pidmnozhini z p yati vershin z grafu G shonajmenshe odna z p yati vershin maye zamknutij okil yakij ye pidmnozhinoyu abo dorivnyuye zamknutim okolam inshih vershin z p yatirki Ekvivalentno ce grafi v yakih chastkovij poryadok zamknutih okoliv yakij viznachayetsya vklyuchennyam mnozhin maye shirinu yaka ne perevishuye 4 Graf cikl iz 5 vershinami maye shirinu chastkovogo poryadku okoliv rivnu p yati tak sho chislo chotiri ye maksimalnoyu shirinoyu sho zabezpechuye doskonale vporyadkuvannya Yak i v razi hordalnih grafiv ale v zagalnomu vipadku ne dlya cilkom uporyadkovuvanih grafiv uzagali grafi z shirinoyu chotiri rozpiznayutsya za polinomialnij chas Koncepciya mizh poryadkom doskonalogo viklyuchennya dlya hordalnih grafiv i doskonalim uporyadkuvannyam ponyattya poryadku napivdoskonalogo viklyuchennya U doskonalomu viklyuchenni nemaye porodzhenogo shlyahu z troh vershin u yakomu serednya vershina viklyuchayetsya pershoyu a v poryadku napivdoskonalogo viklyuchennya nemaye porodzhenih shlyahiv z chotiroh vershin u yakih odna z serednih vershin vidalyayetsya ranishe vid inshih z chetvirki Otzhe obernennya takogo uporyadkuvannya zadovolnyaye vimogam doskonalogo uporyadkuvannya tak sho grafi z poryadkom napivdoskonalogo viklyuchennya ye cilkom uporyadkovuvanimi Zokrema algoritm leksikografichnogo poshuku v shirinu vikoristovuvanij dlya poshuku poryadku doskonalogo viklyuchennya dlya hordalnih grafiv mozhna vikoristati dlya poshuku poryadku napivdoskonalogo viklyuchennya distancijno uspadkovuvanih grafiv yaki takim chinom takozh ye cilkom uporyadkovuvanimi Grafi dlya yakih bud yake vporyadkuvannya vershin ye doskonalim ce kografi odnochasno i hordalni i distancijno uspadkovuvani grafi Oskilki kografi ne mistyat porodzhenih shlyahiv iz chotiroh vershin voni ne mozhut porushiti vimogi vporyadkuvannya shlyahiv u doskonalomu poryadku Vidomi deyaki inshi klasi cilkom uporyadkovuvanih grafiv PrimitkiChvatal 1984 Maffray 2003 Middendorf Pfeiffer 1990 Payan 1983 Felsner Raghavan Spinrad 2003 Hoang Reed 1989 Brandstadt Le Spinrad 1999 s 70 82 Brandstadt Le Spinrad 1999 s 71 Theorem 5 2 4 Christen Selkow 1979 Chvatal Hoang Mahadev De Werra 1987 Hoang Maffray Olariu Preissmann 1992 Brandstadt Le Spinrad 1999 s 81 86 LiteraturaAndreas Brandstadt Van Bang Le Jeremy Spinrad Graph Classes A Survey SIAM Monographs on Discrete Mathematics and Applications 1999 ISBN 0 89871 432 X Claude A Christen Stanley M Selkow Some perfect coloring properties of graphs 1979 T 27 vip 1 S 49 59 Series B DOI 10 1016 0095 8956 79 90067 4 Vaclav Chvatal Topics in Perfect Graphs Claude Berge Vaclav Chvatal Amsterdam North Holland 1984 T 21 S 63 68 Annals of Discrete Mathematics Yak procitovano v Maffreya Maffray 2003 Vaclav Chvatal Chinh T Hoang N V R Mahadev D De Werra Four classes of perfectly orderable graphs Journal of Graph Theory 1987 T 11 vip 4 S 481 495 DOI 10 1002 jgt 3190110405 F F Dragan F Nicolai LexBFS orderings of distance hereditary graphs Schriftenreihe des Fachbereichs Mathematik der Univ Duisburg SM DU 303 Yak procitovano v Branshtedta Brandstadt Le ta Spinrad 1999 Stefan Felsner Vijay Raghavan Jeremy Spinrad Recognition algorithms for orders of small width and graphs of small Dilworth number 2003 T 20 vip 4 S 351 364 2004 DOI 10 1023 B ORDE 0000034609 99940 fb Chinh T Hoang Frederic Maffray Stephan Olariu Myriam Preissmann A charming class of perfectly orderable graphs 1992 T 102 vip 1 S 67 74 DOI 10 1016 0012 365X 92 90348 J Chinh T Hoang Bruce A Reed Some classes of perfectly orderable graphs Journal of Graph Theory 1989 T 13 vip 4 S 445 463 DOI 10 1002 jgt 3190130407 Frederic Maffray Recent Advances in Algorithms and Combinatorics Bruce A Reed Claudia L Sales Springer Verlag 2003 T 11 S 65 84 CMS Books in Mathematics ISBN 0 387 95434 1 DOI 10 1007 0 387 22444 0 3 Matthias Middendorf Frank Pfeiffer On the complexity of recognizing perfectly orderable graphs 1990 T 80 vip 3 S 327 333 DOI 10 1016 0012 365X 90 90251 C Charles Payan Perfectness and Dilworth number 1983 T 44 vip 2 S 229 230 DOI 10 1016 0012 365X 83 90064 X

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