I grafteori er en sammenlignelighedsgraf en urettet graf , hvor par af elementer er forbundet med en kant, hvis disse elementer er sammenlignelige i en eller anden delvis rækkefølge . Sammenlignelighedsgrafer kaldes også transitivt orienterede grafer , delvist ordnede grafer og indlejrede grafer [1] . En uforlignelig graf er en urettet graf , hvor par af elementer er forbundet med en kant, hvis elementerne er uforlignelige i en eller anden delvis rækkefølge .
For ethvert delvist strengt ordnet sæt ( S ,<), er sammenlignelighedsgrafen ( S , <) grafen ( S , ⊥), hvis hjørner er elementer af S , og hvis kanter er par { u , v } af elementer, således at u < v . For delvist ordnede sæt tager vi således en rettet acyklisk graf , bruger en transitiv lukning og fjerner orienteringen.
En sammenlignelighedsgraf er også en graf med en transitiv orientering [2] , der har en orientering af grafens kanter således, at naboforholdet for den resulterende rettede graf er transitivt - hvis der er buer ( x , y ) og ( y , z ) ), skal der være en bue ( x , z ).
Man kan repræsentere et delvist ordnet mængde som en familie af mængder sådan, at x < y i delvis rækkefølge, hvis mængden svarende til x er en delmængde af mængden svarende til y . Det kan således vises, at sammenlignelighedsgrafen er ækvivalent med indlejringsgrafen for en familie af mængder, det vil sige en graf, hvis hjørner er familiens sæt, og kanterne forbinder hjørnerne, hvis et af mængderne er indeholdt i den anden [3] .
Også [4] er en sammenlignelighedsgraf en graf, hvor man for enhver generaliseret cyklus af ulige længde kan finde en kant ( x , y ), der forbinder to hjørner, der er i en afstand af to i cyklussen. Sådanne kanter kaldes trianguleringsakkorder . I denne sammenhæng er generaliserede sløjfer lukkede gennemløb, der krydser hver kant af grafen højst én gang i hver retning.
Sammenlignelighedsgrafen kan også beskrives ved at indstille forbudte undergrafer [5] .
Enhver komplet graf er en sammenlignelighedsgraf, sammenlignelighedsgrafen for et lineært ordnet sæt . Alle acykliske orienteringer i en komplet graf er transitive. Enhver todelt graf er også en sammenlignelighedsgraf. Orienteringen af kanterne af en todelt graf fra den ene side til den anden fører til en transitiv orientering svarende til en delvis rækkefølge af højde to. Som Seymour ( 2006 ) bemærkede , har enhver sammenlignelighedsgraf, der hverken er komplet eller todelt, en skæv faktorisering .
Komplementet af enhver intervalgraf er en sammenlignelighedsgraf. Intervalgrafer er nøjagtigt akkordgrafer med sammenlignelighedsgrafer som komplementer [6] .
En permutationsgraf er en indlejringsgraf af et sæt intervaller [7] . Således er permutationsgrafer en anden klasse af sammenlignelighedsgrafer.
Trivielt perfekte grafer er sammenlignelighedsgrafer for rodfæstede træer [8] . Kografer kan karakteriseres som sammenlignelighedsgrafer af parallel-sekventielle partielle ordrer . Således er kografer også sammenlignelighedsgrafer [9] .
Enhver sammenlignelighedsgraf er perfekt . Perfektionen af sammenlignelighedsgrafer er Mirskys teorem , og perfektionen af deres komplementer er Dilworths teorem . Disse fakta, sammen med dualitetsegenskaben ved perfekte grafer, kan bruges til at bevise Dilworths sætning ud fra Mirskys sætning og omvendt [10] . Mere præcist er sammenlignelighedsgrafer velordnede grafer , hvor sidstnævnte er en underklasse af perfekte grafer - den grådige farvealgoritme til topologisk sortering af en transitiv orientering af en graf farver den optimalt [11] .
Komplementet af enhver sammenlignelighedsgraf er en strenggraf [12] .
Den transitive orientering af grafen, hvis den findes, kan findes i lineær tid [13] . Algoritmen, der gør dette, bestemmer dog orienteringen for enhver graf, så for at fuldføre opgaven med at kontrollere, om en graf er en sammenlignelighedsgraf, skal man kontrollere, om orienteringen er transitiv, hvilket i kompleksitet svarer til matrixmultiplikation .
Da sammenlignelighedsgrafer er perfekte, kan mange problemer, der er vanskelige for mere generelle klasser af grafer, herunder graffarvning og det uafhængige sætproblem løses for sammenlignelighedsgrafer i polynomisk tid.