Permutationsgraf

I grafteorin är en permutationsgraf en graf vars hörn motsvarar elementen i permutationen och vars kanter representerar par av element som är omvända efter permutationen. Permutationsgrafer kan definieras geometriskt som skärningsdiagram för segment vars ändar ligger på två parallella linjer. Olika permutationer kan ge samma permutationsgraf. En given graf har en unik representation (upp till symmetri) om den är enkel när det gäller moduluppdelning [1] .

Definition och beskrivning

Låt σ = (σ 1 ,σ 2 , ..., σ n ) vara någon permutation av tal från 1 till n . För σ har permutationsgrafen n hörn v 1 , v 2 , ..., v n och i denna graf finns en kant v i v j för två godtyckliga index i och j för vilka i  <  j och σ i  > σ j . För två index i och j definieras således en kant i en graf på exakt samma sätt som en transposition i en permutation definieras.

Givet en permutation σ kan man definiera en uppsättning segment si med ändpunkter ( i ,0) och (σ i , 1). Slutpunkterna för dessa segment är belägna på två parallella linjer y  = 0 och y  = 1, och två segment har en icke-tom skärningspunkt om och endast om de motsvarar inversionen i permutationen. Således sammanfaller permutationsgrafen för σ med segmentskärningsgrafen . För alla två parallella linjer och varje ändlig uppsättning linjesegment med ändar på dessa linjer, är linjesegmentens skärningsdiagram en permutationsgraf. Om alla ändpunkter för segmenten är olika kan permutationen som motsvarar permutationsgrafen erhållas genom att numrera segmenten på en av linjerna (sekventiellt, till exempel från vänster till höger), då kommer siffrorna på den andra linjen att ge den önskade permutationen.

Permutationsgrafer kan beskrivas på några andra likvärdiga sätt:

Effektiva algoritmer

Det är möjligt att kontrollera om en graf är en permutationsgraf och konstruera motsvarande permutation i linjär tid [5] .

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

Relation till andra klasser av grafer

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

Underklasser av permutationsgrafer är tvådelade permutationsgrafer och kografer .

Anteckningar

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

Litteratur

Länkar