AccueilđŸ‡«đŸ‡·Chercher

Graphe cordal

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.

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.

On parle aussi de graphe triangulé.

DĂ©finition

Un graphe est cordal s'il ne contient pas de cycle induit de longueur 4 ou plus[1] - [2]. 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[2].

Caractérisations

Élimination parfaite

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 (Fulkerson et Gross 1965).

Graphes d'intersection de sous-arbres

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 Gavril 1974, 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.

SĂ©parateurs

Les graphes dont tous les séparateurs minimaux sont des cliques sont les graphes cordaux[3].

Relations avec d'autres classes

Sous-classes

Les graphes d'intervalles sont les graphes d'intersection de sous-arbres de graphes chemin ; ainsi, ils sont une sous-famille des graphes cordaux.

Les graphes scindés (ou « séparés », split graphs en anglais) sont exactement les graphes à la fois cordaux et complémentaires de graphes cordaux. Bender, Richmond et Wormald 1985 ont montré, en notant le nombre de graphes scindés à sommets et le nombre de graphes cordaux à sommets, que tendait vers 1 lorsque tendait vers l'infini.

Les graphes trivialement parfaits sont exactement les graphes qui sont Ă  la fois des graphes cordaux et des cographes.

Sur-classes

Les graphes cordaux sont une sous-classe des graphes sans trou pair et des graphes sans trou impair, puisque les graphes cordaux sont par définition les graphes sans trou (un trou étant un cycle de longueur au moins 4).

Aspects algorithmiques

Reconnaissance des graphes cordaux

Rose, Lueker et Tarjan 1976 (voir aussi Habib et al. 2000) montrent qu'un ordonnancement d'Ă©limination parfaite d'un graphe cordal peut ĂȘtre trouvĂ© de maniĂšre efficace en utilisant un algorithme appelĂ©e parcours en largeur lexicographique[4]. Cet algorithme maintient une partition des sommets du graphe sous forme d'une sĂ©quence d'ensembles. Au dĂ©but, cette sĂ©quence est un seul ensemble avec tous les sommets. L'algorithme va ensuite choisir de maniĂšre rĂ©pĂ©tĂ©e un sommet de l'ensemble le plus jeune dans la sĂ©quence qui contient les sommets pas encore choisis, et sĂ©pare chaque ensemble de la sĂ©quence en deux sous-ensembles, l'un contenant les voisins de dans et l'autre les sommets non-voisins. Quand cette sĂ©paration a Ă©tĂ© faite pour tous les sommets, la sĂ©quence est composĂ©e d'ensembles ne contenant qu'un seul sommet. Ces sommets se retrouvent dans l'ordre inverse de l'ordonnancement d'Ă©limination parfaite.

Comme la recherche lexicographique en largeur d'abord et le fait de tester si un ordonnancement est un ordonnancement d'Ă©limination parfaite peuvent ĂȘtre effectuĂ©s en temps linĂ©aire, il est possible de savoir si un graphe est cordal en temps linĂ©aire.

L'ensemble de tous les ordonnancements d'Ă©limination parfaite d'un graphe cordal peut ĂȘtre modĂ©lisĂ© comme les mots de base d'un antimatroĂŻde (en) ; Chandran et al. 2003 ont utilisĂ© cette connexion avec les antimatroĂŻdes dans un algorithme listant efficacement tous les ordonnancements d'Ă©limination parfaite d'un graphe cordal donnĂ©.

Cliques maximales et coloration de graphes

Une application de l'ordonnancement d'Ă©limination parfaite est la recherche d'une clique maximum d'un graphe cordal en temps polynomial. Le problĂšme similaire, mais pour un graphe quelconque, est NP-complet[5]. De maniĂšre gĂ©nĂ©rale, le nombre de cliques maximales dans un graphe cordal croĂźt linĂ©airement, tandis que cette croissance peut ĂȘtre exponentielle dans des graphes non cordaux. Pour lister toutes les cliques maximales d'un graphe cordal, il suffit de trouver un ordonnancement d'Ă©limination parfaite, de crĂ©er une clique pour chaque sommet avec les voisins de venant aprĂšs dans l'ordonnancement d'Ă©limination parfaite, et de tester pour chacune des cliques ainsi formĂ©es si est maximale.

La plus grande clique maximale est une clique maximum et, comme les graphes cordaux sont des graphes parfaits, la taille de la clique est le nombre chromatique du graphe cordal. Un graphe cordal est parfaitement ordonnable : une coloration optimale peut ĂȘtre obtenue par application d'un algorithme de coloration gloutonne aux sommets dans l'ordre inverse de celui de l'ordonnancement d'Ă©limination parfaite (Maffray 2003).

Bibliographie

  • (en) E. A. Bender, L. B. Richmond et N. C. Wormald, « Almost all chordal graphs split », J. Austral. Math. Soc., Series A, vol. 38, no 2,‎ , p. 214–221, lien Math Reviews
  • (en) L. S. Chandran, L. Ibarra, F. Ruskey et J. Sawada, « Enumerating and characterizing the perfect elimination orderings of a chordal graph », Theoretical Computer Science, vol. 307,‎ , p. 303–317 (DOI 10.1016/S0304-3975(03)00221-4, lire en ligne).
  • (en) D. R. Fulkerson et O. A. Gross, « Incidence matrices and interval graphs », Pacific J. Math, vol. 15,‎ , p. 835–855 (lire en ligne)
  • (en) Fănică Gavril, « The intersection graphs of subtrees in trees are exactly the chordal graphs », Journal of Combinatorial Theory, Series B, vol. 16,‎ , p. 47–56 (DOI 10.1016/0095-8956(74)90094-X)
  • (en) Michel Habib, Ross McConnell, Christophe Paul et Laurent Viennot, « Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing », Theoretical Computer Science, vol. 234,‎ , p. 59–84 (DOI 10.1016/S0304-3975(97)00241-7, lire en ligne).
  • (en) Richard M. Karp, « Reducibility Among Combinatorial Problems », dans Raymond E. Miller et James W. Thatcher, Complexity of Computer Computations, Plenum, (ISBN 978-1-4684-2003-6, DOI 10.1007/978-1-4684-2001-2_9, lire en ligne), p. 85-103
  • (en) FrĂ©dĂ©ric Maffray, « On the coloration of perfect graphs », dans Bruce A. Reed et ClĂĄudia L. Sales, Recent Advances in Algorithms and Combinatorics, Springer-Verlag, coll. « CMS Books in Mathematics, vol. 11 », (DOI 10.1007/0-387-22444-0_3), p. 65–84.
  • (en) D. Rose, George Lueker et Robert E. Tarjan, « Algorithmic aspects of vertex elimination on graphs », SIAM Journal on Computing, vol. 5,‎ , p. 266–283 (DOI 10.1137/0205021).

Notes et références

Voir aussi

Liens externes

  • (en) H.N. de Ridder et al. 2001-2012, ISGCI (Information System on Graph Classes and their Inclusions), Graphclass: chordal.
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent s’appliquer aux fichiers multimĂ©dias.