Contraction d'arête

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En théorie des graphes, une contraction d'arête est une opération sur un graphe. Elle consiste, de façon imagée, à contracter une arête d'un graphe, ce qui revient à fusionner ses deux extrémités.

Cette opération est fondamentale pour la théorie des mineurs de graphe et elle est utilisée dans certains algorithmes et certaines preuves.

Définition[modifier | modifier le code]

Contraction de l'arête (u,v).

Soit un graphe G=(V,E), contenant une arête (u,v), avec u différent de v. La contraction de (u,v) est l'opération qui consiste à transformer G en un graphe G'=(V',E'), où V' est égal à V mise à part que u et v sont remplacés par un unique sommet w, et E' est égal à E mis à part que les occurrences de u et v sont remplacés par w.

Selon le domaine d'application, on enlève ou non les boucles et les multi-arêtes créées par la contraction.

Utilisations[modifier | modifier le code]

L'algorithme de Karger pour la coupe min[1],[2], et l'algorithme de Borůvka pour l'arbre couvrant de poids minimum[3],[4] utilisent la contraction d'arêtes.

Un déroulement de l'algorithme de Karger sur un graphe. Pour cet algorithme, on conserve les multiarêtes.

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

  1. David Karger, « Global Min-cuts in RNC and Other Ramifications of a Simple Mincut Algorithm », dans Proc. 4th Annual ACM-SIAM Symposium on Discrete Algorithms, (lire en ligne)
  2. Notes du cours de Sanjeev Arora (Université de Princeton).
  3. (cs) Otakar Borůvka, « O jistém problému minimálním (About a certain minimal problem) », Práce mor. přírodověd. spol. v Brně III, vol. 3,‎ , p. 37–58.
  4. « Algorithme de Boruvka », sur COATI chez INRIA.

Voir aussi[modifier | modifier le code]