Résumé
thumb|Un cycle, en noir, avec deux cordes, en vert. Si l'on s'en tient à cette partie, le graphe est cordal. Supprimer l'une des arêtes vertes rendrait le graphe non cordal. En effet, l'autre arête verte formerait, avec les trois arêtes noires, un cycle de longueur 4 sans corde. En théorie des graphes, on dit qu'un graphe est cordal si chacun de ses cycles de quatre sommets ou plus possède une corde, c'est-à-dire une arête reliant deux sommets non adjacents du cycle. Une définition équivalente est que tout cycle sans corde possède au plus trois sommets. Les graphes cordaux, aussi appelés graphes triangulés, sont un sous-ensemble des graphes parfaits. On parle aussi de graphe triangulé. Un graphe est cordal s'il ne contient pas de cycle induit de longueur 4 ou plus. Un cycle induit de longueur quatre ou plus est appelé un trou. Le terme «graphe triangulé» est aussi utilisé car chaque cycle doit être un triangle. Un ordonnancement d'élimination parfaite d'un graphe est un ordonnancement des sommets du graphe tel que, pour tout sommet , l'ensemble formé par et ses voisins qui se trouvent après lui forment une clique. Un graphe est cordal si et seulement s'il possède un ordonnancement d'élimination parfaite . thumb|Un graphe cordal à huit sommets, représenté comme le graphe d'intersection de huit sous-arbres d'un arbre à six nœuds Une autre caractérisation des graphes cordaux faite par , utilise les arbres et leurs sous-arbres. À partir d'une collection de sous-arbres d'un arbre , il est possible de définir un graphe sous-arbre qui est un graphe d'intersection avec un sommet par sous-arbre. Les arêtes relient les sous-arbres qui ont au moins un nœud en commun dans l'arbre . Comme Gavril l'a montré, les graphes sous-arbre sont exactement les graphes cordaux. Cette représentation forme une décomposition arborescente du graphe, où la hauteur du graphe vaut la taille de la plus grande clique du graphe moins un; la décomposition arborescente de n'importe quel graphe peut être vue de cette manière comme une représentation de comme un sous-graphe d'un graphe cordal.
À 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.