Permutační graf

V teorii grafů je graf permutace graf , jehož vrcholy odpovídají prvkům permutace a jehož hrany představují dvojice prvků, které jsou po permutaci obráceny. Permutační grafy lze definovat geometricky jako průsečíkové grafy segmentů, jejichž konce leží na dvou rovnoběžných úsecích. Různé permutace mohou poskytnout stejný permutační graf. Daný graf má jednoznačné zobrazení (až do symetrie), pokud je jednoduchý z hlediska modulárního rozkladu [1] .

Definice a popis

Nechť σ = (σ 1 ,σ 2 , ..., σ n ) je nějaká permutace čísel od 1 do n . Pro σ má permutační graf n vrcholů v 1 , v 2 , ..., v n a v tomto grafu existuje hrana v i v j pro libovolné dva indexy i a j , pro které i  <  j a σ i  > σ j . Pro dva indexy i a j je tedy hrana v grafu definována přesně stejným způsobem, jako je definována transpozice v permutaci.

Vzhledem k permutaci σ lze definovat množinu segmentů s i s koncovými body ( i ,0) a (σ i ,1). Koncové body těchto segmentů jsou umístěny na dvou rovnoběžných přímkách y  = 0 a y  = 1 a dva segmenty mají neprázdný průsečík právě tehdy, pokud odpovídají inverzi v permutaci. Permutační graf pro σ se tedy shoduje s grafem průniku segmentů . Pro jakékoli dvě rovnoběžné úsečky a jakoukoli konečnou množinu úseček s konci na těchto úsecích je graf průsečíku úseček grafem permutace. Pokud jsou všechny koncové body segmentů různé, lze permutaci odpovídající permutačnímu grafu získat očíslováním segmentů na jedné z čar (postupně, například zleva doprava), čísla na druhé linii pak požadovanou permutaci.

Permutační grafy lze popsat některými jinými ekvivalentními způsoby:

Efektivní algoritmy

Je možné zkontrolovat, zda je graf permutačním grafem a sestrojit odpovídající permutaci v lineárním čase [5] .

Jako podtřída dokonalých grafů lze pro permutační grafy efektivně vyřešit mnoho problémů, které jsou NP-úplné pro libovolné grafy. Například:

Vztah k jiným třídám grafů

Permutační grafy jsou speciálním případem kruhových grafů , grafů srovnatelnosti , doplňků grafů srovnatelnosti a lichoběžníkových grafů .

Podtřídy permutačních grafů jsou bipartitní permutační grafy a kografy .

Poznámky

  1. ↑ Brandstädt, Le, Spinrad, 1999 , s.191.
  2. ↑ Brandstädt, Le, Spinrad, 1999 , Tvrzení 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 .

Literatura

Odkazy