4. Arbre de recouvrement minimal▲
4-1. Définition▲
Un arbre de recouvrement est un arbre qui permet de relier les points d'un graphe G de telle sorte que pour tout couples (A, B) de point du graphe G, il existe un chemin permettant de relier A à B.
Un arbre de recouvrement minimal est un arbre de recouvrement dont le poids total (la somme des poids de ses arcs) est minimal (il n'existe pas d'arbre de recouvrement de poids plus faible). Le terme "arbre de recouvrement minimal" est parfois abrégé MST, pour Minimum Spanning Tree.
L'intérêt d'un arbre de recouvrement minimal est le suivant: Imaginons que l'on souhaite relier plusieurs villes entre elles à un réseau quelconque (gaz, électricité, téléphone...). Un graphe représente les liaisons possibles entre chacune de ces villes avec le coût que représente la liaison entre ces villes. La recherche de l'arbre de recouvrement minimal servira à de déterminer le réseau qui permettra de relier toutes les villes entre elles avec un coût minimal.
Pour trouver l'arbre de recouvrement minimal, on dispose de 2 algorithmes: Jarnik et Kruskal.
4-2. Algorithme de Jarnik (ou Prim)▲
4-2-1. Principe de l'algorithme▲
L'algorithme connu sous le nom d' "algorithme de Prim" (bien qu'en fait découvert par Jarnik 27 ans avant Prim) ressemble beaucoup, dans son principe, à l'algorithme de Dijkstra, même si la finalité est différente (trouver l'arbre de recouvrement minimal, et non le chemin le plus court entre 2 points) :
- On construit un graphe G' uniquement composé d'un point de départ
- On fait la liste des arcs tels que
- le point de départ appartienne à G'
- le point d'arrivée appartienne à G (notre graphe de départ) mais pas à G'
- Si la liste est vide, on s'arrête (on a fini de construire l'arbre de recouvrement minimal)
- A partir de cette liste, on sélectionne l'arc de poids le plus faible (afin de minimiser le poids du graphe)
- On ajoute cet arc à G', ce qui ajoute également un point à l'arbre en construction
- Retour en 2.
4-2-2. Implémentation▲
Voici l'implémentation de cet algorithme :
prim(Depart, ARM) :-
prim1([Depart], [], ARM).
prim1(Visite, Temp, ARM) :-
% On recherche tous les arcs P1->P2 tels que :
% - P1 appartient à Visite
% - P2 n'appartient pas à Visite
findall(
Poids-(P1,P2)
,
( member(P1, Visite), arc(P1,P2,Poids), \+member(P2, Visite) )
,
Candidates
),
% On évalue les candidats
prim2(Candidates, Visite, Temp, ARM).
prim2([], _, Temp, ARM) :-
% Il n'y a plus de candidat -> on a fini, on retourne l'ARM
!,
reverse(Temp, ARM).
prim2(Candidates, Visite, Temp, ARM) :-
% Recherche du meilleur candidat P2
keysort(Candidates, [_-(P1,P2)|_]),
prim1([P2|Visite], [ P1-P2 | Temp], ARM).
4-3. Algorithme de Kruskal▲
4-3-1. Principe de l'algorithme▲
L'algorithme de Kruskal fonctionne de la façon suivante :
- On part d'un graphe vide G'
- On dresse la liste des arcs de G, triés par poids croissant
- On parcourt ensuite la liste triée :
- si la liste ne contient plus d'élément, on a terminé et l'algorithme s'arrête
- si les deux points de l'arc ont déjà été visités, on ignore l'arc et on examine les arcs suivants
- sinon, on ajoute l'arc à l'arbre en construction, on ajoute les points de l'arc à la liste des points visités et on on examine les arcs suivants
4-3-2. Implémentation▲
Voici l'implémentation de l'algorithme de Kruskal :
kruskal(ARM) :-
findall(
Poids-(P1,P2)
,
arc(P1,P2,Poids)
,
Arcs
),
keysort(Arcs, ArcsTries),
krusk(ArcsTries, [], ARM).
krusk([], _, []) :-
!.
krusk([_-(P1,P2)|Q], Visite, ARM) :-
memberchk(P1, Visite),
memberchk(P2, Visite),
!,
krusk(Q, Visite, ARM).
krusk([_-(P1,P2)|Q], Visite, [P1-P2|ARM]) :-
union([P1,P2], Visite, Visite2),
krusk(Q, Visite2, ARM).
4-4. Différences entre Jarnik et Kruskal▲
Voici quelques unes des différences entre les algorithmes de Jarnik et Kruskal :
- Jarnik construit l'arbre de recouvrement minimal (ARM) en commençant par un point quelconque du graphe, alors que Kruskal construit l'ARM à partir des arêtes
- Dans le cas d'un graphe disjoint, Jarnik retournera l'ARM dans lequel appartient le point de départ, alors que Kruskal renverra tous les arbres de recouvrement minimal (constituant ainsi une forêt d'arbres)
Le choix d'un de ces 2 algorithmes découle le plus souvent du choix de la représentation du graphe. La plupart des représentations permettent, pour un point donné, d'accéder à la liste des points voisins mais ne permettent pas de dresser rapidement la liste des arêtes du graphes (c'est le cas, par exemple, avec une liste d'adjacences), pourtant nécessaire à Kruskal. Dans ce cas, on privilégie donc Jarnik.
Dans ce tutoriel, nous avons utilisé une représentation nous permettant d'avoir directement accès aux arêtes du graphe. Nous privilégierons donc l'algorithme de Kruskal pour ses nombreux avantages (algorithme simple à comprendre, simple à mettre en place, code concis, plus rapide car effectuant moins de tris, algorithme applicable sans modification au cas d'un graphe disjoint).
Conclusion▲
Dans ce cours, nous avons donné une implémentation Prolog de quelques algorithmes courants de la théorie des graphes (Dijkstra, Kruskal...). Concernant l'implémentation, nous avons choisi d'être le plus neutre et le plus général possible.
Les applications de la théorie des graphes sont nombreuses et le prédicat arc/3 est une généralisation de toutes sortes de relations dans différents contextes. Aussi nous invitons nos lecteurs à bien comprendre les algorithmes et les implémentations présentés dans cet article afin de les adapter au mieux en fonction de leurs besoins.