Permutationsgraf

Permutationsgrafen och matchningsdiagrammet för permutationen

(4,3,5,1,2)

Inom det matematiska området för grafteorin är en permutationsgraf en graf vars hörn representerar elementen i en permutation och vars kanter representerar par av element som vänds om av permutationen. Permutationsgrafer kan också definieras geometriskt , som skärningsdiagram för linjesegment vars ändpunkter ligger på två parallella linjer. Olika permutationer kan ge upphov till samma permutationsgraf; en given graf har en unik representation (upp till permutationssymmetri ) om den är primtal med avseende på den modulära nedbrytningen .

Definition och karaktärisering

Om $\rho =(\sigma _{1},\sigma _{2},...,\sigma _{n})$ är någon permutation av talen från $1$ till $n$ , då kan man definiera en permutationsgraf från $\sigma$ där det finns $n$ hörn $v_{1},v_{2},...,v_{n}$ och där det finns en kant $v_{i}v_{j}$ för två valfria index $i<j$ för vilka $j$ förekommer före $i$ i $\rho$ . Det vill säga två index $i$ och $j$ bestämmer en kant i permutationsgrafen exakt när de bestämmer en inversion i permutationen.

Givet en permutation $\sigma$ , kan man också bestämma en uppsättning linjesegment $s_{i}$ med ändpunkter $(i,0)$ och $(k,1)$ , så att $\sigma _{k}=i$ . Slutpunkterna för dessa segment ligger på de två parallella linjerna $y=0$ och $y=1$ , och två segment har en icke-tom skärningspunkt om och endast om de motsvarar en inversion i permutationen. Således sammanfaller permutationsgrafen för $\sigma$ med skärningsgrafen för segmenten. För varje två parallella linjer, och varje ändlig uppsättning linjesegment med ändpunkter på båda linjerna, är skärningsdiagrammet för segmenten en permutationsgraf; i det fall att segmentändpunkterna alla är distinkta, kan en permutation för vilken det är permutationsgrafen ges genom att segmenten numreras på en av de två linjerna i följd, och avläser dessa siffror i den ordning som segmentändpunkterna visas. på andra linjen.

Permutationsgrafer har flera andra likvärdiga karaktäriseringar:

En graf $G$ är en permutationsgraf om och endast om $G$ är en cirkelgraf som tillåter en ekvator , dvs ett extra ackord som skär varannan ackord.
En graf $G$ är en permutationsgraf om och endast om både $G$ och dess komplement ${\overline {G}}$ är jämförbarhetsgrafer .
En graf $G$ är en permutationsgraf om och endast om det är jämförbarhetsgrafen för en delvis ordnad uppsättning som har orderdimension som högst två.
Om en graf $G$ är en permutationsgraf, så är dess komplement det också. En permutation som representerar komplementet av $G$ kan erhållas genom att vända om permutationen som representerar $G$ .

Effektiva algoritmer

Det är möjligt att testa om en given graf är en permutationsgraf, och i så fall konstruera en permutation som representerar den, i linjär tid .

Som en underklass av de perfekta graferna kan många problem som är NP-kompletta för godtyckliga grafer lösas effektivt för permutationsgrafer. Till exempel:

den största klicken i en permutationsgraf motsvarar den längsta minskande undersekvensen i permutationen som definierar grafen, så klickproblemet kan lösas i polynomtid för permutationsgrafer genom att använda en längst minskande undersekvensalgoritm.
likaså motsvarar en ökande undersekvens i en permutation en oberoende uppsättning av samma storlek i motsvarande permutationsgraf.
trädbredden och vägbredden för permutationsgrafer kan beräknas i polynomtid ; dessa algoritmer utnyttjar det faktum att antalet inkluderande minimala vertexseparatorer i en permutationsgraf är polynom i storleken på grafen.

Relation till andra grafklasser

Permutationsgrafer är ett specialfall av cirkelgrafer , jämförbarhetsgrafer , komplementen till jämförbarhetsgrafer och trapetsformade grafer .

Underklasserna av permutationsgraferna inkluderar de tvådelade permutationsgraferna (karakteriserade av Spinrad, Brandstädt & Stewart 1987) och kograferna .

Anteckningar

Baker, Kirby A.; Fishburn, Peter C .; Roberts, Fred S. (1971), "Partial orders of dimension 2", Networks , 2 (1): 11–28, doi : 10.1002/net.3230020103 .
Bodlaender, Hans L. ; Kloks, Ton; Kratsch, Dieter (1995), "Treewidth and pathwidth of permutation graphs", Journal on Discrete Mathematics , 8 (4): 606–616, doi : 10.1137/S089548019223992X , hdl 4/16685 : 1685 SIAM
Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy P. (1999), Graph Classes: A Survey , SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X .
Dushnik, Ben; Miller, Edwin W. (1941), "Partially ordered sets", American Journal of Mathematics , 63 (3): 600–610, doi : 10.2307/2371374 , JSTOR 2371374 .
Golumbic, Martin C. (1980), Algorithmic Graph Theory and Perfect Graphs , Datavetenskap och tillämpad matematik, Academic Press, sid. 159 .
McConnell, Ross M.; Spinrad, Jeremy P. (1999), "Modular decomposition and transitive orientation", Discrete Mathematics , 201 (1–3): 189–241, doi : 10.1016/S0012-365X(98)00319-7 , MR 9687 .
Spinrad, Jeremy P.; Brandstädt, Andreas ; Stewart, Lorna K. (1987), "Bipartite permutation graphs", Discrete Applied Mathematics , 18 (3): 279–292, doi : 10.1016/s0166-218x(87)80003-3 .

externa länkar