Permutationsgraf

I grafteori er en permutationsgraf en graf, hvis toppunkter svarer til elementerne i permutationen , og hvis kanter repræsenterer par af elementer, der er vendt om efter permutationen. Permutationsgrafer kan defineres geometrisk som skæringsgrafer af segmenter, hvis ender ligger på to parallelle linjer. Forskellige permutationer kan give den samme permutationsgraf. En given graf har en unik repræsentation (op til symmetri), hvis den er enkel med hensyn til modulær dekomponering [1] .

Definition og beskrivelse

Lad σ = (σ 1 ,σ 2 , ..., σ n ) være en eller anden permutation af tal fra 1 til n . For σ har permutationsgrafen n toppunkter v 1 , v 2 , ..., v n og i denne graf eksisterer en kant v i v j for alle to indekser i og j for hvilke i < j og σ i > σ j . For to indeks i og j defineres således en kant i en graf på nøjagtig samme måde, som en transposition i en permutation er defineret.

Givet en permutation σ kan man definere et sæt af segmenter si med endepunkter ( i ,0) og (σ i , 1 ). Disse segmenters endepunkter er placeret på to parallelle linjer y = 0 og y = 1, og to segmenter har et ikke-tomt skæringspunkt, hvis og kun hvis de svarer til inversionen i permutationen. Således falder permutationsgrafen for σ sammen med segmentskæringsgrafen . For alle to parallelle linjer og ethvert begrænset sæt af linjestykker med ender på disse linjer, er linjestykkernes skæringsgraf en permutationsgraf. Hvis alle segmenternes endepunkter er forskellige, kan permutationen svarende til permutationsgrafen fås ved at nummerere segmenterne på en af linjerne (sekventielt f.eks. fra venstre mod højre), så vil tallene på den anden linje give den nødvendige permutation.

Permutationsgrafer kan beskrives på nogle andre tilsvarende måder:

Grafen G er en permutationsgraf, hvis og kun hvis G er en cirkulær graf , hvor det er muligt at konstruere en ækvator , altså en ekstra akkord, der vil skære alle andre akkorder [2] .
En graf G er en permutationsgraf, hvis og kun hvis både G og dens komplement er sammenlignelighedsgrafer [3] . $\overline{G}$
En graf G er en permutationsgraf, hvis og kun hvis det er en sammenlignelighedsgraf for en poset , hvis dimension ikke overstiger to [4] .
Hvis grafen G er en permutationsgraf, så er komplementet det også. Permutationen svarende til komplementet af grafen G kan opnås som den omvendte permutation af den, der svarer til grafen G .

Effektive algoritmer

Det er muligt at kontrollere om en graf er en permutationsgraf og konstruere den tilsvarende permutation i lineær tid [5] .

Som en underklasse af perfekte grafer kan mange problemer, der er NP-komplette for vilkårlige grafer, løses effektivt for permutationsgrafer. For eksempel:

Den maksimale klike i en permutationsgraf svarer til den største faldende undersekvens i den permutation, der definerer grafen, så klikproblemet for permutationsgrafer kan løses i polynomisk tid ved hjælp af den største faldende sekvensalgoritme [6] .

På samme måde svarer en stigende sekvens i en permutation til et uafhængigt sæt af samme størrelse i permutationsgrafen.

Træbredden og stibredden af permutationsgrafer kan beregnes i polynomiel tid. Algoritmer til beregning af disse værdier bruger det faktum, at antallet af beregninger af minimumspunktseparatorerne i en permutationsgraf afhænger polynomielt af størrelsen af grafen [7] .

Relation til andre klasser af grafer

Permutationsgrafer er et særligt tilfælde af cirkelgrafer , sammenlignelighedsgrafer , komplementer til sammenlignelighedsgrafer og trapezformede grafer .

Underklasser af permutationsgrafer er todelte permutationsgrafer og kografer .

Noter

↑ Brandstädt, Le, Spinrad, 1999 , s.191.
↑ Brandstädt, Le, Spinrad, 1999 , Proposition 4.7.1, s.57.
↑ Dushnik, Miller, 1941 .
↑ Baker, Fishburn, Roberts, 1971 .
↑ McConnell, Spinrad, 1999 .
↑ Golumbic, 1980 .
↑ Bodlaender, Kloks, Kratsch, 1995 .

Litteratur