Graficul de permutare

În teoria grafurilor, un graf de permutare este un graf ale cărui vârfuri corespund elementelor permutării și ale cărui muchii reprezintă perechi de elemente care sunt inversate după permutare. Graficele de permutare pot fi definite geometric ca grafice de intersecție ale segmentelor ale căror capete se află pe două linii paralele. Permutări diferite pot da același grafic de permutare. Un graf dat are o reprezentare unică (până la simetrie) dacă este simplu în termeni de descompunere modulară [1] .

Definiție și descriere

Fie σ = (σ 1 ,σ 2 , ..., σ n ) o permutare a numerelor de la 1 la n . Pentru σ, graficul de permutare are n vârfuri v 1 , v 2 , ..., v n și în acest grafic există o muchie v i v j pentru oricare doi indici i și j pentru care i  <  j și σ i  > σ j . Astfel, pentru doi indici i și j , o muchie dintr-un grafic este definită exact în același mod în care este definită o transpunere într-o permutare.

Având în vedere o permutare σ, se poate defini un set de segmente s i cu puncte finale ( i ,0) și (σ i ,1). Capatele acestor segmente sunt situate pe două drepte paralele y  = 0 și y  = 1, iar două segmente au o intersecție nevidă dacă și numai dacă corespund inversării în permutare. Astfel, graficul de permutare pentru σ coincide cu graficul de intersecție a segmentelor . Pentru orice două linii paralele și orice set finit de segmente de linii cu capete pe aceste drepte, graficul de intersecție al segmentelor de linii este un grafic de permutare. Dacă toate punctele de capăt ale segmentelor sunt diferite, permutarea corespunzătoare graficului de permutare poate fi obținută prin numerotarea segmentelor pe una dintre linii (secvențial, de exemplu, de la stânga la dreapta), atunci numerele de pe cealaltă linie vor da permutarea dorită.

Graficele de permutare pot fi descrise în alte moduri echivalente:

Algoritmi eficienți

Este posibil să se verifice dacă un grafic este un grafic de permutare și să se construiască permutarea corespunzătoare în timp liniar [5] .

Ca o subclasă de grafice perfecte , multe probleme care sunt NP-complete pentru graficele arbitrare pot fi rezolvate eficient pentru graficele de permutare. De exemplu:

Relația cu alte clase de grafice

Graficele de permutare sunt un caz special de grafice circulare, grafice de comparabilitate , complemente ale graficelor de comparabilitate și grafice trapezoidale .

Subclasele de grafice de permutare sunt grafice de permutare bipartite și cografe .

Note

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

Literatură

Link -uri