title: Contraction d'arête
text: # Contraction d'arête
  
  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 $min^,,$ et l'algorithme de Borůvka pour l'arbre couvrant de poids $minimum^,$ utilisent la contraction d'arêtes.
  
  