Graphe de permutation
En théorie des graphes, un graphe de permutation est un graphe non orienté dont les sommets représentent les éléments d'une permutation, et dont les arêtes relient les paires de sommets qui sont inversés dans la permutation. On peut aussi définir les graphes de permutations de manière géométrique : ce sont les graphes d'intersections de segments dont les extrémités sont sur deux droites parallèles.

Définitions et caractérisations 

On définit les graphes de permutation de la manière suivante. Les sommets représentent les éléments d'une permutation, et les arêtes relient les paires de sommets dont les éléments sont inversés dans la permutation.

Autre caractérisations : 

 les graphes de permutation sont les graphes d'intersection de segments dont les extrémités sont disposés sur deux droites parallèles.
 les graphes de permutation sont les graphes qui sont des graphes de comparabilité et dont le complémentaire est aussi de comparabilité.

Relations avec d'autres classes 

La classe des graphes de permutation est incluse dans les graphes de comparabilité, dans les , et dans les .

Les cographes sont des graphes de permutation.

Notes et références

Liens externes 
 

Graphe géométrique
Famille de graphes