Sammenlignelighed graf - Comparability graph

I grafteori er en sammenlignelighedsgraf en uorienteret graf, der forbinder par af elementer, der kan sammenlignes med hinanden i en delvis rækkefølge . Sammenlignelighedsgrafer er også blevet kaldt transitivt orienterbare grafer , delvist ordnede grafer , indeslutningsgrafer og delingsgrafer . En uforlignelighed graf er en ikke -styret graf, der forbinder par af elementer, der ikke kan sammenlignes med hinanden i en delvis rækkefølge .

Definitioner og karakterisering

Image
Hasse -diagram over en poset (venstre) og dens sammenlignelighedsgraf (højre)
Image
En af de forbudte inducerede subgrafer af en sammenlignelighedsgraf. Den generaliserede cyklus a - b - d - f - d - c - e - c - b - a i denne graf har ulige længder (ni), men har ingen trekantede akkorder.

For ethvert strengt delvist ordnet sæt ( S , <) er sammenlignelighedsgrafen for ( S , <) grafen ( S , ⊥), hvis hjørner er elementerne i S, og kanterne er disse par { u , v } af elementer sådan at u < v . Det vil sige, for et delvist ordnet sæt, tag den rettede acykliske graf , anvend transitiv lukning og fjern orientering.

Tilsvarende er en sammenlignelighedsgraf en graf, der har en transitiv orientering , en tildeling af retninger til grafens kanter (dvs. en orientering af grafen), således at adjacensforholdet for den resulterende dirigerede graf er transitiv : når der er rettet kanter ( x , y ) og ( y , z ), skal der eksistere en kant ( x , z ).

Man kan repræsentere enhver endelig delorden som en gruppe af sæt, således at x < y i delordenen, når det sæt, der svarer til x, er et undersæt af sættet, der svarer til y . På denne måde kan sammenligningsgrafer påvises at svare til indeslutningsgrafer for sætfamilier; det vil sige en graf med et toppunkt for hvert sæt i familien og en kant mellem to sæt, når det ene er et delsæt af det andet. Alternativt kan man repræsentere den delvise rækkefølge ved en familie af heltal , således at x < y når hele tallet svarende til x er en divisor af heltalet svarende til y . På grund af denne konstruktion er sammenlignelighedsgrafer også blevet kaldt delingsgrafer.

Sammenlignelighedsgrafer kan karakteriseres som graferne således, at man for hver generaliseret cyklus af ulige længder kan finde en kant ( x , y ), der forbinder to hjørner, der er på afstand to i cyklussen. En sådan kant kaldes en trekantet akkord . I denne sammenhæng er en generaliseret cyklus defineret til at være en lukket gang, der bruger hver kant af grafen højst én gang i hver retning. Sammenlignelighedsgrafer kan også karakteriseres ved en liste over forbudte inducerede subgrafer .

Forholdet til andre graffamilier

Hver komplet graf er en sammenlignelighedsgraf, sammenlignelighedsgrafen for en samlet ordre . Alle acykliske orienteringer af en komplet graf er transitive. Hver topartsgraf er også en sammenlignelighedsgraf. Orientering af kanterne på en todelt graf fra den ene side af todelen til den anden resulterer i en transitiv orientering, svarende til en delvis rækkefølge af højde to. Som Seymour (2006) bemærker, har hver sammenligningsgraf, der hverken er komplet eller topartet, en skæv partition .

Den komplementet af ethvert interval graf er en sammenlignelighed graf. Sammenlignelighedsforholdet kaldes en intervalordre . Intervalgrafer er nøjagtigt de grafer, der er akkordale, og som har sammenlignelige grafkompletter.

En permutationsgraf er en indeslutningsgraf med et sæt intervaller. Derfor er permutationsgrafer en anden underklasse af sammenlignelighedsgrafer.

De trivielt perfekte grafer er sammenlignelighedsgrafer for rodfæstede træer . Cographs kan karakteriseres som sammenlignelighedsgrafer for serie-parallelle delordner ; cographs er således også sammenlignelighedsgrafer.

Tærskelgrafer er en anden særlig form for sammenlignelighedsgraf.

Hver sammenligningsgraf er perfekt . Perfektionen af ​​sammenlignelighedsgrafer er Mirskys sætning , og perfektionen af ​​deres komplementer er Dilworths sætning ; disse fakta sammen med den perfekte grafteorem kan bruges til at bevise Dilworths sætning ud fra Mirskys sætning eller omvendt. Nærmere betegnet er sammenlignelighedsgrafer fuldstændig ordenlige grafer , en underklasse af perfekte grafer: en grådig farvelgoritme til en topologisk rækkefølge af en transitiv orientering af grafen vil farve dem optimalt.

Den supplement af hver sammenlignelighed graf er en streng graf .

Algoritmer

En transitiv orientering af en graf, hvis den findes, kan findes i lineær tid. Imidlertid vil algoritmen til at gøre det tildele orienteringer til kanterne på en hvilken som helst graf, så for at fuldføre opgaven med at teste, om en graf er en sammenlignelighedsgraf, skal man teste, om den resulterende orientering er transitiv, et problem, der sandsynligvis svarer i kompleksitet til matrix multiplikation .

Fordi sammenlignelighedsgrafer er perfekte, kan mange problemer, der er hårde for mere generelle klasser af grafer, herunder graffarvning og det uafhængige sætproblem , løses i polynomtid for sammenlignelighedsgrafer.

Noter

Referencer

  • Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey , SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
  • Chartrand, Gary ; Muntean, Raluca; Saenpholphat, Varaporn; Zhang, Ping (2001), "Hvilke grafer er delingsgrafer?", Proceedings of the Thirty-second Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 2001), Congressus Numerantium , 151 : 189-200, MR  1887439
  • Dushnik, Ben; Miller, EW (1941), "Delvist bestilt sæt", American Journal of Mathematics , The Johns Hopkins University Press, 63 (3): 600-610, doi : 10,2307 / 2.371.374 , HDL : 10338.dmlcz / 100.377 , JSTOR  2.371.374 , MR  0004862.
  • Fox, Jacob; Pach, Jànos (2012), "String -grafer og uforlignelige grafer" (PDF) , Advances in Mathematics , 230 (3): 1381–1401, doi : 10.1016/j.aim.2012.03.011.
  • Gallai, Tibor (1967), "Transitiv orientierbare Graphen", Acta Math. Acad. Sci. Hung. , 18 (1–2): 25–66, doi : 10.1007/BF02020961 , MR  0221974 , S2CID  119485995.
  • Ghouila-Houri, Alain (1962), "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", Les Comptes rendus de l'Académie des sciences , 254 : 1370– 1371, MR  0172275.
  • Gilmore, PC; Hoffman, AJ (1964), "En karakterisering af sammenlignelighedsgrafer og af intervalgrafer", Canadian Journal of Mathematics , 16 : 539–548, doi : 10.4153/CJM-1964-055-5 , MR  0175811.
  • Golumbic, Martin Charles (1980), Algoritmisk grafteori og perfekte grafer , Academic Press, ISBN 0-12-289260-7.
  • Golumbic, M .; Rotem, D .; Urrutia, J. (1983), "Sammenlignelighedsgrafer og skæringsgrafer", Diskret matematik , 43 (1): 37–46, doi : 10.1016/0012-365X (83) 90019-5.
  • Jung, HA (1978), "On a class of posets and the corresponding comparability graphs", Journal of Combinatorial Theory, Series B , 24 (2): 125–133, doi : 10.1016/0095-8956 (78) 90013-8 , MR  0491356.
  • Lovász, L. (1983), "Perfekte grafer", udvalgte emner i grafteori , 2 , London: Academic Press, s. 55–87.
  • Maffray, Frédéric (2003), "Om farvning af perfekte grafer", i Reed, Bruce A .; Sales, Cláudia L. (red.), Recent Advances in Algorithms and Combinatorics , CMS Books in Mathematics, 11 , Springer-Verlag, s. 65–84, doi : 10.1007/0-387-22444-0_3.
  • McConnell, RM; Spinrad, J. (1997), "Linear-time transitive orientation", 8. ACM-SIAM Symposium on Discrete Algorithms , s. 19–25.
  • Seymour, Paul (2006), "Hvordan beviset for den stærke perfekte grafformodning blev fundet" (PDF) , Gazette des Mathématiciens (109): 69–83, MR  2245898.
  • Trotter, William T. (1992), Combinatorics and Partially Ordered Sets - Dimension Theory , Johns Hopkins University Press.
  • Urrutia, Jorge (1989), "Partial orders and Euclidean geometry", i Rival, I. (red.), Algorithms and Order , Kluwer Academic Publishers, s. 327–436, doi : 10.1007/978-94-009-2639 -4.