Théorie des graphes et algorithmes

Le théorème est évidemment vrai lorsque G est vide.

Supposons maintenant que G soit non vide et contienne moins de n-1 arêtes. On suppose qu'aucune des arêtes de coût minimal qui ne sont pas déjà dans G tout en ne créant pas de cycles avec G ne soit retenue.

Considérons un arbre de coût minimal F qui contient G et pas les arêtes refusées précédemment.

Soit b une des arêtes refusées précédemment.

Si on l'ajoute à F, on crée un cycle.

Comme b ne créait pas de cycle en l'ajoutant à G.

Obligatoirement, une des arêtes de ce cycle, adjacente à b, n'est pas dans G et a donc un coût strictement supérieur à b qui était une des arêtes de coût minimal.

Soit c l'une des arêtes adjacente à b et ajoutée à G après avoir refusé b.

En ôtant c de F et en ajoutant b, on supprime le cycle et on garde la connexité, ce qui nous fournit un arbre de coût strictement inférieur à l'arbre supposé de coût minimal.

(preuve par l'absurde).

On commence avec un sous-ensemble d'arêtes imposé F vide et on applique le théorème. On sait alors que l'on peut retenir dans l'arbre en cours de construction (sous forme d'un graphe partiel pas encore connexe, mais sans cycle) l'une des arêtes a_o de coût minimal. On la met dans F.

Si le graphe comporte plus de deux points, alors on considère l'une des arêtes de coût minimal en excluant a_o qui est déjà dans F. Soit a₁ cette arête. On la met également dans F car deux arêtes ne sont pas suffisantes pour créer un cycle.

Si le graphe comporte plus de trois points, alors on considère l'une des arêtes de coût minimal qui n'est pas dans F. Soit a₂ cette arête. Comme avec trois arêtes on peut créer un cycle et qu'un arbre est sans cycle, il faut vérifier si cette arête ferme un cycle avec les arêtes qui sont dans F. Si c'est le cas, on rejette cette arête sinon on met cette arête dans F.

On recommence l'activité précédente, pour les graphes de plus de trois points, jusqu'à ce que F contienne n-1 arêtes où n est le nombre de points du graphe considéré.

Après avoir cliqué sur Anim pour lancer l'animation, vous pouvez tester l'algorithme sur plusieurs exemples en utilisant "précédent" ou "suivant".

Pour l'étape 1, le tri des arêtes peut être effectué par un algorithme en mlogm.

L'étape 5 comporte au plus m itérations.

Pour chaque itération, l'algorithme qui vérifie si l'arête que l'on souhaite ajouter ne comporte pas de cycle peut être réalisée par un algorithme de coût linéaire par rapport à n si on ne l'optimise pas, mais peut être de coût log(n) si on utilise une structure de données de type anti-arborescence. Comme cela sera expliqué ci-après pour les personnes intéressées.

La complexité de l'algorithme est ainsi celle d'un tri de m arêtes.

Le nombre m d'arêtes d'un graphe connexe peut varier de n-1 à . L'algorithme de Kruskal est d'autant plus rapide que le graphe connexe est pauvre en arêtes.

Dans l'algorithme de Kruskal, on utilise une structure de données qui représente les composantes connexes du graphe partiel en cours de construction.

Ces composantes connexes sont représentées par des anti-arborescences.

Une anti-arborescence est un arbre orienté où tout point possède au plus un successeur.

Un seul point ne possède pas de successeurs, il est appelé anti-racine ou plus simplement racine (puisque l'on sait que l'on est dans une anti-arborescence).

Tous les points qui sont dans la même composante connexe ont la même racine. On trouve la racine de tout point en parcourant l'unique chemin qui part du point et qui mène à la racine.

Pour que l'ajout d'une arête {x,y} dans le graphe partiel sans cycle ne crée pas de cycle, il faut que x et y soit dans deux composantes connexes différentes et donc que racine(x) soit différente de racine(y).

La structure de données utilisée pour représenter les composantes connexes du graphe partiel est tout simplement un tableau d'entiers.

Ce tableau d'entiers contient dans la case SUCC(i) la valeur - 1 si i a été choisi comme racine d'une composante connexe ou un entier j différent de i si le point i n'est pas une racine de l'anti-arborescence. j est alors successeur de i dans l'anti-arborescence ; il est dans la même composante connexe.

Au départ, on initialise le tableau SUCC à - 1. Le graphe partiel vide est alors composé de n composantes connexes. Chaque point constitue une composante connexe.

Lorsque l'on ajoute la première arête Eo={xo,yo}, on fusionne les composantes connexes de xo et de yo. Comme ce sont deux racines, il suffit de poser SUCC(xo)=yo ou de manière équivalente SUCC(yo)=xo selon que l'on retient yo ou xo comme racine de la nouvelle anti-arborescence, le deuxième point ayant comme successeur la racine retenue.

En cours d'algorithme, lorsque l'on ajoute l'arête E={x,y}. Pour vérifier si cette arête crée un cycle, on cherche racine(x). Pour obtenir racine(x), on considére ro=SUCC(x), puis r1=SUCC(ro), ... , on s'arrête lorsque rk vaut -1 et rk-1 est la racine de x. On calcule de la même façon racine(y).

Si racine(x) = racine(y) alors on rejette l'arête, sinon, il faut fusionner les composantes connexes de x et de y. Pour cela, il suffit de faire SUCC(racine(x))=racine(y) ou SUCC(racine(y))=racine(x). Pour optimiser l'algorithme, ce choix n'est pas arbitraire, il faut regarder la longueur des plus longs chemins dans les deux composantes connexes et choisir comme nouvelle racine celle de la composante connexe dont les chemins étaient les plus longs (de manière arbitraire en cas d'égalité).

On considère l'exemple suivant.

On initialise les tableaux SUCC et H à -1 (chaque point est racine de sa composante connexe) et à 0 (la hauteur des anti-arborescences est nulles)

L'arête {7,4} de valeur 1 est la première arête trouvée par le tri des arêtes. On la place dans le graphe partiel et on regroupe les points 4 et 7 dans la même composante connexe en mettant, par exemple, la valeur 4 dans SUCC(7). La hauteur de la composante connexe qui a pour racine 4 est maintenant égale à 1.

Conseil

Pour bien comprendre l'algorithme et l'utilisation des anti-arborescences, vous pouvez prendre une feuille de papier et dessiner d'une part le graphe partiel avec les arcs que l'on ajoute à chaque étape et le graphe des anti-arborescences à chacune de ses modifications.

L'arête {8,10} de valeur 1 est la seconde arête trouvée par le tri des arêtes. 8 et 4 sont tous les deux des racines. On ne crée donc pas de cycle en ajoutant cette arête.

On la place dans le graphe partiel et on regroupe les points 8 et 10 dans la même composante connexe en mettant, par exemple, la valeur 8 dans SUCC(10). La hauteur de la composante connexe qui a pour racine 8 est maintenant égale à 1.

L'arête {9,10} de valeur 2 est l'arête suivante. 9 est une racine et 10 a pour racine 8 (différente de 9). On ne crée donc pas de cycle en ajoutant cette arête.

On la place dans le graphe partiel et on regroupe les points 9 et 10 dans la même composante connexe. L'anti-arborescence de racine 8 est de hauteur 1 alors que celle de 9 est de hauteur 0. Pour maintenir pour 8 la hauteur 1, on va accorder à SUCC(9) la valeur 8 (on lui donne la même racine que le point 10 qu'il vient rejoindre).

L'arête {3,6} de valeur 2 est l'arête suivante. 3 et 6 sont tous les deux des racines. On ne crée donc pas de cycle en ajoutant cette arête.

On la place dans le graphe partiel et on regroupe les points 3 et 6 dans la même composante connexe en mettant, par exemple, la valeur 6 dans SUCC(3). La hauteur de la composante connexe qui a pour racine 3 est maintenant égale à 1.

L'arête {2,3} de valeur 2 est l'arête suivante. 2 et 3 sont tous les deux des racines. On ne crée donc pas de cycle en ajoutant cette arête.

On la place dans le graphe partiel et on regroupe les points 2 et 3 dans la même composante connexe. L'anti-arborescence de racine 3 est de hauteur 1 alors que celle de 2 est de hauteur 0. Pour maintenir pour 3 la hauteur 1, on va accorder à SUCC(2) la valeur 3 (6 et 3 ont comme successeurs la racine 2 et la hauteur de l'anti-arborescence reste égale à 1).

L'arête {5,6} de valeur 2 est l'arête suivante. 5 est une racine alors que la racine de 6 est 3. On ne crée donc pas de cycle en ajoutant cette arête.

On la place dans le graphe partiel et on regroupe les points 5 et 6 dans la même composante connexe. L'anti-arborescence de racine 3 est de hauteur 1 alors que celle de 5 est de hauteur 0. Pour maintenir pour 3 la hauteur 1, on va accorder à SUCC(5) la valeur 3 (6 et 5 ont comme successeurs la racine 3 et la hauteur de l'anti-arborescence reste égale à 1).

L'arête {6,4} de valeur 3 est l'arête suivante. 4 est une racine alors que la racine de 6 est 3. On ne crée donc pas de cycle en ajoutant cette arête.

On la place dans le graphe partiel et on regroupe les points 4 et 6 dans la même composante connexe. L'anti-arborescence de racine 3 est de hauteur 1, il en est de même pour celle de 4. Dans ce cas, on passe à la hauteur 2 pour la composante, on pointe une des deux racines vers l'autre racine. Par exemple,, on va accorder à SUCC(4) la valeur 3.

L'arête {8,3} de valeur 3 est l'arête suivante. 8 et 3 sont des racines. On ne crée donc pas de cycle en ajoutant cette arête.

On la place dans le graphe partiel et on regroupe les points 8 et 3 dans la même composante connexe. L'anti-arborescence de racine 3 est de hauteur 2, alors que celle de 8 est seulement de 1. On reste à la hauteur 2 pour 3 à condition de poser SUCC(8) égal à 3.

Comme p = n-2, il ne manque plus qu'une dernière arête pour compléter l'arbre et le rendre connexe.

L'arête {9,5} de valeur 3 est l'arête suivante. 9 a pour successeur 8 qui a pour successeur 3 et 5 a pour successeur 3. 9 et 5 ont donc 3 pour racine. Il ne faut pas ajouter cette arête car elle créerait un cycle dans le graphe partiel. On passe donc à l'arête suivante.

L'arête {7,2} de valeur 4 est l'arête suivante. 7 a pour successeur 4 qui a pour successeur 3 et 2 a pour successeur 3. 7 et 2 ont donc 3 pour racine. Il ne faut pas ajouter cette arête car elle créerait un cycle dans le graphe partiel. On passe donc à l'arête suivante.

8 et 3 sont des racines. On ne crée donc pas de cycle en ajoutant cette arête.

L'arête {1,6} de valeur 4 est l'arête suivante. 1 est une racine alors que 6 a pour racine 3. Elle ne crée donc pas de cycle. On la place dans le graphe partiel et on regroupe les points 1 et 6 dans la même composante connexe. L'anti-arborescence de racine 3 est de hauteur 2, alors que celle de 1 est seulement de 0. On reste à la hauteur 2 pour 3 à condition de poser SUCC(1) égal à 3.

L'algorithme de Kruskal est terminé. Le résultat est donné dans la figure suivante.