Arbres couvrants


Problème de recherche d'un arbre couvrant :

Soit un graphe non orienté. Peut-on trouver un sous ensemble du graphe, défini en conservant tous les sommets mais en ne gardant que certaines arêtes, qui satisfasse les propriétés d'un "arbre" (connexe et sans cycle) ?

Nous ne voyons en fait pas d'algorithme spécifique pour répondre à cette question. Pour ce faire, il suffit de donner une valeur identique à toutes les arêtes du graphe, et de répondre au problème suivant :


Recherche d'arbre couvrant de poids minimal :

Soit un graphe non orienté et valué (valeur numérique associée à chaque arête). Trouver un arbre couvrant ayant le poids de valeur minimale.


La "poids" d'un graphe non orienté est la somme des valeurs de toutes ses arêtes.


Nous abordons ici les algorithmes classiques :

- Kruskall, version "constructive" et version "destructive" ;

- Prim.