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
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 L'algorithme de Karger pour la coupe minNotes du cours de Sanjeev Arora (Université de Princeton)., et l'algorithme de Borůvka pour l'arbre couvrant de poids minimum.. utilisent la contraction d'arêtes.
frame|center|Un déroulement de l'algorithme de Karger sur un graphe. Pour cet algorithme, on conserve les multiarêtes.
Notes et références
Voir aussi Mineur (théorie des graphes) Théorème de Robertson-Seymour
Catégorie:Opération sur les graphes