Ê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 trivialement parfait
Résumé
vignette|upright=2| Construction d'un graphe trivialement parfait à partir d'intervalles imbriqués et de la relation d'accessibilité dans un arbre.
En théorie des graphes, un graphe trivialement parfait est un graphe qui a la propriété que dans chacun de ses sous-graphes induits, la taille du stable maximal est égale au nombre de cliques maximales. Les graphes trivialement parfaits ont été étudiés pour la première fois par Elliot S. Wolk en 1962; ils ont été nommés ainsi par Golumbic ; Golumbic écrit que « le nom a été choisi car il est trivial de montrer qu'un tel graphique est parfait ». Les graphes trivialement parfaits sont également appelés graphes de comparabilité d'arbres, graphes de comparabilité arborescents, et graphes à quasi-seuil.
Les graphes trivialement parfaits ont plusieurs autres caractérisations équivalentes :
Ils sont les graphes des arbres de comparabilité des arbres de la théorie des ordres. Autrement dit, soit un ensemble partiellement ordonné tel que pour tout , l'ensemble est bien ordonné par la relation
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.