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

В теорії графів граф порівнянності це неорієнтований граф у якому пари елементів з єднано ребром якщо ці елементи en в д

Граф порівнянності

Граф порівнянності

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

Визначення й характеристики

image
Діаграма Гассе частково впорядкованої множини (зліва) і її граф порівнянності (праворуч)
image
Один із заборонених породжених підграфів графу порівнянності. Узагальнений цикл a-b-d-f-d-c-e-c-b-a в цьому графі має непарну довжину (дев'ять), але не має хорд тріангуляризації

Для будь-якої частково строго впорядкованої множини (S, <) граф порівнянності (S, <) — це граф (S, ⊥), вершини якого — елементи S, а ребра — це пари {u, v} елементів, таких що u < v. Таким чином, для частково впорядкованих множин беремо орієнтований ациклічний граф, використовуємо транзитивне замикання і видаляємо орієнтацію.

Також, граф порівнянності — це граф, який має транзитивну орієнтацію, тобто орієнтація його ребер така, що відношення суміжності є транзитивним — якщо існують дуги (x, y) і (y, z), повинна існувати дуга (x, z).

Можна подати частково впорядковану множину, як сімейство множин таких, що x < y у частковому порядку, якщо відповідна x множина є підмножиною множини, відповідної y. Таким чином, можна показати, що граф порівнянності еквівалентний графу вкладеності сімейства множин, тобто графу, вершинами якого є множини сімейства, а ребра з'єднують вершини, якщо одна з множин міститься в іншій.

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

Граф порівнянності можна описати також заданням заборонених підграфів.

Зв'язок з іншими сімействами графів

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

Доповнення будь-якого інтервального графу є графом порівнянності. Інтервальні графи — це точно хордальні графи, які мають доповненнями графи порівнянності.

Граф перестановки — це граф вкладеності множини інтервалів. Таким чином, графи перестановок — це ще один клас графів порівнянності.

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

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

Доповнення будь-якого графу порівнянності є струнним графом.

Алгоритми

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

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

Див. також

Примітки

  1. Golumbic, 1980, стор. 105; Brandstädt et al, 1999, стор. 94.
  2. Ghouila-Houri, 1962; див. Brandstädt et al, 1999, теорема 1.4.1, стор. 12. Хоча орієнтація, породжена частковим порядком не циклічна, немає потреби включати умову відсутності циклів
  3. Urrutia, 1989; Trotter, 1992; Brandstädt et al, 1999, секція 6.3, стор. 94—96.
  4. Ghouila-Houri, 1962 и Gilmore, Hoffman, 1964. См. также Brandstädt et al, 1999, теорема 6.1.1, стор. 91.
  5. Gallai, 1967; Trotter, 1992; Brandstädt et al, 1999, стор. 91 і 112.
  6. Транзитивну орієнтовність доповнень інтервальних графів довів Гойла-Гоурі (Ghouila-Houri, 1962); характеризацію інтервальних графів можна знайти в Гілмора і Гофмана (Gilmore, Hoffman, 1964). Див. також Голумбіка (Golumbic, 1980), речення 1.3, сторінки 15—16.
  7. Dushnik, Miller, 1941. Brandstädt et al, 1999, теорема 6.3.1, стор. 95.
  8. (Brandstädt et al, 1999), теорема 6.6.1, стор. 99.
  9. Brandstädt et al1999, наслідок 6.4.1, стор. 96; Jung, 1978.
  10. Golumbic, 1980, теореми 5.34 і 5.35, стор. 133.
  11. Maffray, 2003.
  12. Golumbic, Rotem, Urrutia, 1983 і Lovász, 1983. Див. також Fox, Pach, 2009.
  13. McConnell, Spinrad, 1997; див. Brandstädt et al, 1999, стор. 91.

Посилання

  • Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Graph Classes: A Survey. — SIAM Monographs on Discrete Mathematics and Applications, 1999. — 4 липня. — .
  • Ben Dushnik, E. W. Miller. Partially ordered sets // American Journal of Mathematics. — The Johns Hopkins University Press, 1941. — Т. 63, вип. 3 (4 липня). — С. 600—610. — DOI:10.2307/2371374.
  • J. Fox, J. Pach. String graphs and incomparability graphs. — 2009. — 4 липня.
  • Tibor Gallai. Transitiv orientierbare Graphen // Acta Math. Acad. Sci. Hung.. — 1967. — Т. 18 (4 липня). — С. 25—66. — DOI:10.1007/BF02020961.
  • Alain Ghouila-Houri. Caractérisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une relation d'ordre // . — 1962. — Т. 254 (4 липня). — С. 1370—1371.
  • A characterization of comparability graphs and of interval graphs // Canadian Journal of Mathematics. — 1964. — Т. 16 (4 липня). — С. 539—548. — DOI:10.4153/CJM-1964-055-5.
  • Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. — Academic Press, 1980. — 4 липня. — .
  • M. Golumbic, D. Rotem, J. Urrutia. Comparability graphs and intersection graphs // Discrete Mathematics. — 1983. — Т. 43, вип. 1 (4 липня). — С. 37—46. — DOI:10.1016/0012-365X(83)90019-5.
  • H. A. Jung. On a class of posets and the corresponding comparability graphs // Journal of Combinatorial Theory, Series B. — 1978. — Т. 24, вип. 2 (4 липня). — С. 125—133. — DOI:10.1016/0095-8956(78)90013-8.
  • L. Lovász. Selected Topics in Graph Theory. — London : Academic Press, 1983. — Т. 2. — С. 55—87.
  • 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.
  • R. M. McConnell, J. Spinrad. 8th ACM-SIAM Symposium on Discrete Algorithms. — 1997. — 4 липня. — С. 19—25.
  • Paul Seymour. How the proof of the strong perfect graph conjecture was found // Gazette des Mathématiciens. — 2006. — Вип. 109 (4 липня). — С. 69—83. з джерела 9 березня 2022. Процитовано 17 травня 2021.
  • William T. Trotter. Combinatorics and Partially Ordered Sets — Dimension Theory. — Johns Hopkins University Press, 1992. — 4 липня.
  • Jorge Urrutia. Algorithms and Order. — Kluwer Academic Publishers, 1989. — С. 327—436.

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

V teoriyi grafiv graf porivnyannosti ce neoriyentovanij graf u yakomu pari elementiv z yednano rebrom yaksho ci elementi en v deyakomu chastkovomu poryadku Grafi porivnyannosti takozh nazivayut tranzitivno oriyentovanimi grafami chastkovo vporyadkovuvanimi grafami i grafami vkladenosti Graf neporivnyannosti ce neoriyentovanij graf u yakomu pari elementiv z yednuyutsya rebrom yaksho elementi en v deyakomu chastkovomu poryadku Viznachennya j harakteristikiDiagrama Gasse chastkovo vporyadkovanoyi mnozhini zliva i yiyi graf porivnyannosti pravoruch Odin iz zaboronenih porodzhenih pidgrafiv grafu porivnyannosti Uzagalnenij cikl a b d f d c e c b a v comu grafi maye neparnu dovzhinu dev yat ale ne maye hord triangulyarizaciyi Dlya bud yakoyi chastkovo strogo vporyadkovanoyi mnozhini S lt graf porivnyannosti S lt ce graf S vershini yakogo elementi S a rebra ce pari u v elementiv takih sho u lt v Takim chinom dlya chastkovo vporyadkovanih mnozhin beremo oriyentovanij aciklichnij graf vikoristovuyemo tranzitivne zamikannya i vidalyayemo oriyentaciyu Takozh graf porivnyannosti ce graf yakij maye tranzitivnu oriyentaciyu tobto oriyentaciya jogo reber taka sho vidnoshennya sumizhnosti ye tranzitivnim yaksho isnuyut dugi x y i y z povinna isnuvati duga x z Mozhna podati chastkovo vporyadkovanu mnozhinu yak simejstvo mnozhin takih sho x lt y u chastkovomu poryadku yaksho vidpovidna x mnozhina ye pidmnozhinoyu mnozhini vidpovidnoyi y Takim chinom mozhna pokazati sho graf porivnyannosti ekvivalentnij grafu vkladenosti simejstva mnozhin tobto grafu vershinami yakogo ye mnozhini simejstva a rebra z yednuyut vershini yaksho odna z mnozhin mistitsya v inshij Takozh graf porivnyannosti ce graf u yakomu dlya bud yakogo uzagalnenogo ciklu neparnoyi dovzhini mozhna znajti rebro x y yake z yednuye dvi vershini roztashovani na vidstani dva v cikli Taki rebra nazivayut hordami triangulyaciyi U comu konteksti uzagalneni cikli ye zamknutim obhodom yakij prohodit kozhne rebro grafu ne bilshe odnogo razu v kozhnomu napryamku Graf porivnyannosti mozhna opisati takozh zadannyam zaboronenih pidgrafiv Zv yazok z inshimi simejstvami grafivBud yakij povnij graf ye grafom porivnyannostilinijno vporyadkovanoyi mnozhini Vsi aciklichni oriyentaciyi v povnomu grafi tranzitivni Bud yakij dvochastkovij graf takozh ye grafom porivnyannosti Oriyentaciya reber dvochatkovogo grafu z odnogo boku v inshij privodit do tranzitivnoyi oriyentaciyi sho vidpovidaye chastkovomu poryadku visotoyu dva Yak zauvazhiv Sejmur Seymour 2006 bud yakij graf porivnyannosti yakij ne ye ni povnim ni dvochastkovim maye kosij rozklad Dopovnennya bud yakogo intervalnogo grafu ye grafom porivnyannosti Intervalni grafi ce tochno hordalni grafi yaki mayut dopovnennyami grafi porivnyannosti Graf perestanovki ce graf vkladenosti mnozhini intervaliv Takim chinom grafi perestanovok ce she odin klas grafiv porivnyannosti Trivialno doskonali grafi ce grafi porivnyannosti korenevih derev Kografi mozhna sharakterizuvati yak grafi porivnyannosti paralelno poslidovnih chastkovih poryadkiv Otzhe kografi tezh ye grafami porivnyannosti Bud yakij graf porivnyannosti ye doskonalim Doskonalist grafiv porivnyannosti stverdzhuye en a doskonalist yih dopovnen teorema Diluorsa Ci fakti razom zi vlastivistyu podvijnosti doskonalih grafiv mozhna vikoristovuvati dlya dovedennya teoremi Diluorsa z teoremi Mirskogo i navpaki Tochnishe grafi porivnyannosti ye cilkom uporyadkovuvanimi grafami ostanni ye pidklasom doskonalih grafiv algoritm zhadibnogo rozfarbovuvannya dlya topologichnogo sortuvannya tranzitivnoyi oriyentaciyi grafu rozfarbovuye jogo optimalno Dopovnennya bud yakogo grafu porivnyannosti ye strunnim grafom AlgoritmiTranzitivnu oriyentaciyu grafu yaksho vona isnuye mozhna znajti za linijnij chas Odnak algoritm yakij ce robit viznachaye oriyentaciyu dlya bud yakogo grafu tak sho dlya zavershennya zadachi perevirki chi ye graf grafom porivnyannosti potribno pereviriti chi ye oriyentaciya tranzitivnoyu sho za skladnistyu ekvivalentne mnozhennyu matric Oskilki grafi porivnyannosti doskonali bagato zadach skladni dlya zagalnishih klasiv grafiv zokrema rozfarbovuvannya grafiv i zadacha pro nezalezhnu mnozhinu dlya grafiv porivnyannosti mozhna rozv yazati za polinomialnij chas Div takozhTrivialno doskonalij grafPrimitkiGolumbic 1980 stor 105 Brandstadt et al 1999 stor 94 Ghouila Houri 1962 div Brandstadt et al 1999 teorema 1 4 1 stor 12 Hocha oriyentaciya porodzhena chastkovim poryadkom ne ciklichna nemaye potrebi vklyuchati umovu vidsutnosti cikliv Urrutia 1989 Trotter 1992 Brandstadt et al 1999 sekciya 6 3 stor 94 96 Ghouila Houri 1962 i Gilmore Hoffman 1964 Sm takzhe Brandstadt et al 1999 teorema 6 1 1 stor 91 Gallai 1967 Trotter 1992 Brandstadt et al 1999 stor 91 i 112 Tranzitivnu oriyentovnist dopovnen intervalnih grafiv doviv Gojla Gouri Ghouila Houri 1962 harakterizaciyu intervalnih grafiv mozhna znajti v Gilmora i Gofmana Gilmore Hoffman 1964 Div takozh Golumbika Golumbic 1980 rechennya 1 3 storinki 15 16 Dushnik Miller 1941 Brandstadt et al 1999 teorema 6 3 1 stor 95 Brandstadt et al 1999 teorema 6 6 1 stor 99 Brandstadt et al1999 naslidok 6 4 1 stor 96 Jung 1978 Golumbic 1980 teoremi 5 34 i 5 35 stor 133 Maffray 2003 Golumbic Rotem Urrutia 1983 i Lovasz 1983 Div takozh Fox Pach 2009 McConnell Spinrad 1997 div Brandstadt et al 1999 stor 91 PosilannyaAndreas Brandstadt Van Bang Le Jeremy Spinrad Graph Classes A Survey SIAM Monographs on Discrete Mathematics and Applications 1999 4 lipnya ISBN 0 89871 432 X Ben Dushnik E W Miller Partially ordered sets American Journal of Mathematics The Johns Hopkins University Press 1941 T 63 vip 3 4 lipnya S 600 610 DOI 10 2307 2371374 J Fox J Pach String graphs and incomparability graphs 2009 4 lipnya Tibor Gallai Transitiv orientierbare Graphen Acta Math Acad Sci Hung 1967 T 18 4 lipnya S 25 66 DOI 10 1007 BF02020961 Alain Ghouila Houri Caracterisation des graphes non orientes dont on peut orienter les arretes de maniere a obtenir le graphe d une relation d ordre 1962 T 254 4 lipnya S 1370 1371 A characterization of comparability graphs and of interval graphs Canadian Journal of Mathematics 1964 T 16 4 lipnya S 539 548 DOI 10 4153 CJM 1964 055 5 Martin Charles Golumbic Algorithmic Graph Theory and Perfect Graphs Academic Press 1980 4 lipnya ISBN 0 12 289260 7 M Golumbic D Rotem J Urrutia Comparability graphs and intersection graphs Discrete Mathematics 1983 T 43 vip 1 4 lipnya S 37 46 DOI 10 1016 0012 365X 83 90019 5 H A Jung On a class of posets and the corresponding comparability graphs Journal of Combinatorial Theory Series B 1978 T 24 vip 2 4 lipnya S 125 133 DOI 10 1016 0095 8956 78 90013 8 L Lovasz Selected Topics in Graph Theory London Academic Press 1983 T 2 S 55 87 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 DOI 10 1007 0 387 22444 0 3 R M McConnell J Spinrad 8th ACM SIAM Symposium on Discrete Algorithms 1997 4 lipnya S 19 25 Paul Seymour How the proof of the strong perfect graph conjecture was found Gazette des Mathematiciens 2006 Vip 109 4 lipnya S 69 83 z dzherela 9 bereznya 2022 Procitovano 17 travnya 2021 William T Trotter Combinatorics and Partially Ordered Sets Dimension Theory Johns Hopkins University Press 1992 4 lipnya Jorge Urrutia Algorithms and Order Kluwer Academic Publishers 1989 S 327 436

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