Permutaatiokaavio

Graafiteoriassa permutaatiograafi on graafi, jonka kärjet vastaavat permutaation alkioita ja jonka reunat edustavat alkiopareja, jotka käännetään permutaation jälkeen. Permutaatiograafit voidaan määritellä geometrisesti osien leikkauskaavioina, joiden päät ovat kahdella yhdensuuntaisella suoralla. Erilaiset permutaatiot voivat antaa saman permutaatiograafin. Tietyllä graafilla on ainutlaatuinen esitys (symmetriaan asti), jos se on yksinkertainen modulaarisen hajotuksen kannalta [1] .

Määritelmä ja kuvaus

Olkoon σ = (σ 1 ,σ 2 , ..., σ n ) jokin lukujen permutaatio 1 - n . σ:lle permutaatiograafissa on n kärkeä v 1 , v 2 , ..., v n ja tässä graafissa on reuna v i v j kahdelle indeksille i ja j , joille i  <  j ja σ i  > σ j . Siten kahdelle indeksille i ja j graafin reuna määritellään täsmälleen samalla tavalla kuin transpositio permutaatiossa.

Kun permutaatio σ on annettu, voidaan määrittää joukko segmenttejä s i , joiden päätepisteet ( i ,0) ja (σ i ,1). Näiden segmenttien päätepisteet sijaitsevat kahdella yhdensuuntaisella suoralla y  = 0 ja y  = 1, ja kahdella segmentillä on ei-tyhjä leikkauspiste, jos ja vain jos ne vastaavat permutaatiossa olevaa inversiota. Siten σ:n permutaatiokaavio osuu segmenttien leikkauskuvaajan kanssa . Kaikille kahdelle yhdensuuntaiselle suoralle ja mille tahansa rajalliselle janajoukolle, jonka päät ovat näillä viivoilla, janaosien leikkauskäyrä on permutaatiokaavio. Jos osien kaikki päätepisteet ovat erilaisia, permutaatiokaaviota vastaava permutaatio saadaan numeroimalla segmentit jollakin viivistä (peräkkäin esimerkiksi vasemmalta oikealle), niin toisen rivin numerot antavat haluttu permutaatio.

Permutaatiokaavioita voidaan kuvata muilla vastaavilla tavoilla:

Tehokkaat algoritmit

On mahdollista tarkistaa, onko graafi permutaatiograafi ja rakentaa vastaava permutaatio lineaarisessa ajassa [5] .

Täydellisten graafien alaluokkana monet ongelmat, jotka ovat NP-täydellisiä mielivaltaisille kaavioille, voidaan ratkaista tehokkaasti permutaatiokaavioille. Esimerkiksi:

Suhde muihin graafiluokkiin

Permutaatiokaaviot ovat erikoistapaus ympyräkaavioista , vertailukelpoisuuskaavioista , vertailukaavioiden komplementeista ja puolisuunnikkaan muotoisista kaavioista .

Permutaatiograafien alaluokkia ovat kaksiosaiset permutaatiograafit ja kografit .

Muistiinpanot

  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 .

Kirjallisuus

Linkit