Grafic de permutare

În teoria graficelor , un grafic de permutare este un grafic nedirecționat ale cărui vârfuri reprezintă elementele unei permutări și ale căror margini leagă perechile de vârfuri care sunt inversate în permutare. De asemenea, putem defini graficele permutării într-un mod geometric: sunt graficele intersecțiilor segmentelor ale căror capete sunt pe două linii paralele.

Definiții și caracterizări

Definim graficele permutării după cum urmează. Vârfurile reprezintă elementele unei permutații , iar marginile conectează perechi de vârfuri ale căror elemente sunt inversate în permutare.

Alte caracterizări:

• graficele de permutare sunt graficele de intersecție ale segmentelor ale căror capete sunt dispuse pe două linii paralele.
• graficele de permutare sunt grafice care sunt grafice de comparabilitate și al căror complement este, de asemenea, comparabilitate.

Relațiile cu alte clase

Clasa graficelor de permutare este inclusă în graficele de comparabilitate din graficele de cerc  (în) și graficele trapezoidale  (în) .

Cele cographs sunt grafice permutare.

Note și referințe

• (fr) Acest articol este preluat parțial sau în întregime din articolul Wikipedia din limba engleză intitulat „  Permutation graph  ” (a se vedea lista autorilor ) .

1. Alain Hertz, „  Unele clase de grafice  ” , pe Centrul de cercetare interuniversitar GERAD
2. Ben Dushnik și Edwin W. Miller, „  Seturi parțial ordonate  ”, American Journal of Mathematics , vol.  63, n o  3, 1941, p.  600–610 ( DOI  10.2307 / 2371374 , JSTOR  2371374 , citiți online ).

linkuri externe

• „  Grafic de permutare  ” , pe Sistemul de informații privind clasele de grafice și incluziunile acestora