Cographe

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Un exemple de cographe : le graphe de Turán T(13,4)

En théorie des graphes, un cographe est un graphe qui peut être généré par complémentation et union disjointe à partir du graphe à un nœud.

La plupart des problèmes algorithmiques peuvent être résolus sur cette classe en temps polynomial, et même linaire, du fait de ses propriétés structurelles.

Définitions et caractérisations[modifier | modifier le code]

Cette famille de graphe a été introduite par plusieurs auteurs indépendamment dans les années 70 sous divers noms, notamment D*-graphes, hereditary Dacey graphs et 2-parity graphs[1].

Définition[modifier | modifier le code]

Un cographe est un graphe simple qui peut-être construit de manière recursive selon les règles suivantes:

  • le graphe à un sommet est un cographe,
  • le complémetaire d'un cographe est un cographe,
  • l'union de deux cographe est un cographe.

Définition utilisant l'opération join[modifier | modifier le code]

Le "join" de deux graphes disjoints G_1=(V_1,E_1) et G_2=(V_2,E_2), est l'opération qui consiste a créer un nouveau graphe G=(V,E), où V=V_1 \cup V_2 et E = E_1 \cup E_2 \cup \{(i,j)|i\in V_1,j \in V_2\}. Cette opération est en fait le complémentaire de l'union des complémentaires.

Un cographe est alors un graphe qui peut être formé à partir des graphes à un sommets, par "join" et par union.

Caractérisations[modifier | modifier le code]

Il existe de nombreuses caractérisations des cographes, notamment :

  • les cographes sont les graphes P_4-free, c'est-à-dire ceux qui n'ont pas le chemin sur quatre sommets comme sous-graphe induit[2];
  • les cographes sont graphes pour lesquels tous les sous-graphes induits non-triviaux possèdent deux sommets ayant le même voisinage.

Coarbre[modifier | modifier le code]

Un couple coarbre/cographe.

Un coarbre décrit un cographe, grâce aux opérations qui sont nécessaires pour les construire.

Les feuilles représentent les noeuds du cographe, et les nœuds internes représentent des opérations. Les nœuds étiquetés par un 0 représentent l'union des cographes représentés par les sous-arbres et ceux étiquetés par un 1 représentent le "join" de ces cographes.

Cette représentation est unique. C'est une manière compacte de représenter les cographes.

De plus en échangeant les 1 et les 0, on obtient le coarbre du graphe complémentaire.

Propriétés mathématiques[modifier | modifier le code]

  • La famille des cographes est stable par sous-graphes induits[3];
  • Les cographes sont des graphes parfaits.

Propriétés algorithmiques[modifier | modifier le code]

Les cographes peuvent être reconnus en temps linéaire[4]. La plupart des problèmes classiques peuvent être résolus en temps linéaire sur cette classe, par exemple les problèmes liés aux cliques et aux cycles hamiltoniens[5]. Le problème de la coupe maximum est polynomial sur cette classe[6].

Dans un contexte de calcul distribué synchrone, la caractérisation par 4-chemin exclus permet de reconnaitre les cographes en un nombre constant de tours[7].

Notes et références[modifier | modifier le code]

  1. voir notamment (Jung 1978), (Sumner 1974) et (Burlet et Uhry 1984)
  2. Voir (Corneil, Lerchs et Burlingham 1981) et (Seinsche 1974).
  3. Cela découle directement de la caractérisation P4-free.
  4. (Corneil, Perl et Stewart 1985)
  5. Voir la page associé sur Information System on Graph Classes and their Inclusions
  6. Voir (Bodlaender et Jansen 2000)
  7. (Fraigniaud, Halldorsson et Korman 2012)

Bibliographie[modifier | modifier le code]

  • H. A. Jung, « On a class of posets and the corresponding comparability graphs », Journal of Combinatorial Theory, Series B, vol. 24, no 2,‎ 1978, p. 125–133 (DOI 10.1016/0095-8956(78)90013-8).
  • M. Burlet et J. P. Uhry, « Topics on Perfect Graphs (Parity Graphs) », Annals of Discrete Mathematics, vol. 21,‎ 1984, p. 253–277.
  • D. G. Corneil, H. Lerchs et L. Stewart Burlingham, « Complement reducible graphs », Discrete Applied Mathematics, vol. 3, no 3,‎ 1981, p. 163–174 (DOI 10.1016/0166-218X(81)90013-5).
  • D. G. Corneil, Y. Perl et L. K. Stewart, « A linear recognition algorithm for cographs », SIAM Journal on Computing, vol. 14, no 4,‎ 1985, p. 926–934 (DOI 10.1137/0214065).
  • Hans L. Bodlaender et Klaus Jansen, « On the Complexity of the Maximum Cut Problem », Nord. J. Comput., vol. 7, no 1,‎ 2000, p. 14-31.
  • Pierre Fraigniaud, Magnus M Halldorsson et Amos Korman, « On the impact of identifiers on local decision », dans Principles of Distributed Systems,‎ 2012, p. 224 -238

Voir aussi[modifier | modifier le code]

Lien externe[modifier | modifier le code]