Permutációs gráf

A gráfelméletben a permutációs gráf olyan gráf, amelynek csúcsai megfelelnek a permutáció elemeinek , és amelynek élei olyan elempárokat képviselnek, amelyek a permutáció után megfordulnak. A permutációs gráfok geometriailag definiálhatók olyan szakaszok metszésponti gráfjaiként, amelyek végei két párhuzamos egyenesen fekszenek. Különböző permutációk ugyanazt a permutációs gráfot adhatják. Egy adott gráf egyedi reprezentációval rendelkezik (a szimmetriáig), ha a moduláris felbontás szempontjából egyszerű [1] .

Meghatározás és leírás

Legyen σ = (σ 1 ,σ 2 , ..., σ n ) a számok valamilyen permutációja 1-től n -ig . σ esetén a permutációs gráfnak n v 1 , v 2 , ..., v n csúcsa van, és ebben a gráfban létezik egy v i v j él bármely két i és j indexre , amelyekre i  <  j és σ i  > σ j . Így két i és j index esetén egy gráf éle pontosan ugyanúgy van definiálva, mint egy permutációban a transzpozíció .

Adott egy σ permutáció, definiálhatunk s i szakaszok halmazát ( i ,0) és (σ i ,1) végpontokkal . Ezeknek a szakaszoknak a végpontjai két párhuzamos egyenesen helyezkednek el, y  = 0 és y  = 1, és két szakasznak akkor és csak akkor van nem üres metszéspontja, ha megfelelnek a permutációban lévő inverziónak. Így a σ permutációs gráfja egybeesik a szegmensmetszés gráfjával . Bármely két párhuzamos egyenes és véges szakaszok halmaza esetén, amelyeknek végei ezeken az egyeneseken vannak, a szakaszok metszéspontja egy permutációs gráf. Ha a szegmensek összes végpontja eltérő, akkor a permutációs gráfnak megfelelő permutációt úgy kaphatjuk meg, hogy az egyik vonalon sorszámozzuk a szegmenseket (soros pl. balról jobbra), akkor a másik sorban lévő számok adják meg a kívánt permutációt.

A permutációs gráfokat más ekvivalens módon is leírhatjuk:

Hatékony algoritmusok

Lehetőség van annak ellenőrzésére, hogy egy gráf permutációs gráf-e, és lineáris időben megszerkeszthető a megfelelő permutáció [5] .

A tökéletes gráfok alosztályaként számos olyan probléma, amely tetszőleges gráfokhoz NP-teljes , hatékonyan megoldható permutációs gráfok esetében. Például:

Más gráfosztályokhoz való viszony

A permutációs gráfok a körgrafikonok , az összehasonlíthatósági grafikonok , az összehasonlíthatósági grafikonok kiegészítői és a trapézgráfok speciális esetei .

A permutációs gráfok alosztályai a kétrészes permutációs gráfok és kográfok .

Jegyzetek

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

Irodalom

Linkek