Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Graphe scindé
Résumé
vignette|240x240px| Un graphe scindé, partitionné en une clique et un ensemble stable.
En théorie des graphes, un graphe scindé ou graphe séparé (en anglais : split graph) est un graphe dont les sommets peuvent être partitionnés deux parties : une clique et un ensemble stable. Les graphes scindés ont été étudiés pour la première fois par Földes et Marteau en 1977, et introduit indépendamment par Tyshkevich et Tchernyak en 1979 .
Un graphe scindé peut avoir plus d'une partition en une clique et un ensemble stable ; par exemple, le chemin a – b – c est un graphe scindé, dont les sommets peuvent être partitionnés de trois manières différentes :
la clique et l'ensemble stable ;
la clique et l'ensemble stable ;
la clique et l'ensemble stable .
Les graphes scindés peuvent être caractérisés par leurs sous-graphes induits interdits : un graphe est scindé si et seulement si aucun sous-graphe induit n'est un cycle sur quatre ou cinq sommets, ou n'est une paire d'arêtes disjointes (le complément d'un 4-cycle.
De par leur définition, les graphes scindé sont clairement fermés par complémentation . Une autre caractérisation des graphes scindés fait intervenir la complémentation : ce sont des graphes cordaux dont les compléments sont également cordaux. Tout comme les graphes cordaux sont les graphes d'intersection de sous-arbres d'arbres, les graphes scindés sont les graphes d'intersection de sous-étoiles distinctes de graphes en étoile. Presque tous les graphes cordaux sont des graphes scindés, au sens où la fraction des graphes cordaux scindés parmi les graphes cordaux à n sommets qui sont scindé tend vers 1 lorsque n tend vers l'infini.
Comme les graphes cordaux sont parfaits, les graphes scindés le sont aussi. Les graphes à double scission, une famille de graphes dérivés de graphes scindés en doublant chaque sommet (la clique induit alors un anti-couplage et l'ensemble stable induit un couplage), figure, dans la preuve de du théorème des graphes parfaits fort, comme l'une des cinq classes de base de graphes parfaits à partir desquels tous les autres peuvent être formés.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.