Graphe de permutation
From Wikipedia, the free encyclopedia
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[1].
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é[2].
Relations avec d'autres classes
La classe des graphes de permutation est incluse dans les graphes de comparabilité, dans les circle graphs, et dans les graphes trapézoïdaux (en).
Les cographes sont des graphes de permutation.
