Exercice 1
Il y a 5 villes. Le coût de construction d’une route directement entre i et j est l’entrée a(i,j) dans la matrice ci-dessous. Une entrée indéfinie indique que la route ne peut pas être construite. Déterminez le moindre coût pour rendre toutes les villes accessibles les unes des autres.
Nous ordonnons les arêtes selon les poids : 12, 23, 13, 45, 25, 15, 24, 35, 14 (ligne-colonne). L’algorithme de Kruskal accepte les arêtes 12, 23, puis rejette 13, puis accepte 45, 25, puis s’arrête. Ainsi, le moindre coût pour construire le réseau routier est de 3 + 3 + 7 + 8 = 21.
Exercice 2
Le professeur Herr Guerard propose un nouvel algorithme diviser pour régner pour calculer les arbres couvrant minimum, qui se déroule comme suit.
Étant donné un graphe G = (V, E), partitionnez l’ensemble V de sommets en deux ensembles V1 et V2 tels que |V1| et |V2| diffèrent d’au plus 1. Soit E1 l’ensemble des arêtes qui ne sont incidentes qu’aux sommets de V1, et soit E2 l’ensemble des arêtes qui ne sont incidentes qu’aux sommets de V2. Résolvez récursivement un problème d’arbre couvrant minimum sur chacun des deux sous-graphes G1 = (V1, E1) et G2 = (V2, E2). Enfin, sélectionnez l’arête de poids minimum dans E qui traverse la coupe V1, V2 et utilisez cette arête pour unir les deux arbres couvrants minimum résultants en un seul arbre couvrant.
Il soutient que l’algorithme calcule correctement un arbre couvrant minimum de G, soit fournit un exemple pour lequel l’algorithme échoue. Trouvez un exemple où cela fonctionne et où cela ne fonctionne pas.
Nous affirmons que l’algorithme échouera. Un contre-exemple simple est présenté ci-dessous. Le graphe G = (V, E) a quatre sommets : {v1, v2, v3, v4} et est divisé en sous-ensembles G1 avec V1 = {v1, v2} et G2 avec V2 = {v3, v4}. Le MST de G1 a un poids de 4, et le MST de G2 a un poids de 5, et l’arête de poids minimum traversant la coupe (V1, V2) a un poids de 1, en somme l’arbre couvrant formé par l’algorithme proposé suit {v2, v1 , v4, v3} qui a un poids de 10. Au contraire, il est évident que le MST de G suit {v4, v1, v2, v3} avec un poids de 7. L’algorithme proposé échoue donc à obtenir un MST.
Exercice 3
Montrez que si G est un graphe pondéré et e est une arête dont le poids est inférieur à celui de toute autre arête, alors e doit appartenir à chaque arbre couvrant de poids minimum pour G.
Supposons que T est un arbre couvrant de poids minimum pour G qui ne contient pas l’arête e. Considérons alors le graphe T+e. Ce graphe doit contenir un cycle C qui contient l’arête e. Soit f une arête de C différente de e, et posons T*=T+e−f. Alors T* est aussi un arbre couvrant pour G, mais w(T*)=w(T+e−f)=w(T)+w(e)−w(f) < w(T), contrairement à T étant un arbre couvrant de poids minimum. Par conséquent, un tel arbre T (c’est-à-dire sans e) ne peut exister.
Exercice 4
Montrer que si tous les poids du graphe pondéré G sont distincts, alors il existe un unique arbre couvrant de poids minimum pour G.
La preuve imite quelque peu celle de la preuve de l’algorithme de Kruskal. Supposons que T soit un arbre généré par l’algorithme de Kruskal (en fait, un instant de réflexion montre qu’avec les conditions du problème, un seul arbre de ce type pourrait être généré).
Nous affirmons qu’il n’y a pas d’autres arbres couvrants de poids minimum pour G. Supposons (et nous montrerons que cela conduit à une contradiction) qu’il existe d’autres arbres couvrants de poids minimum, et choisissez-en un, T’. Supposons alors que e est la première arête de T qui n’appartient pas à T’. Autrement dit, supposons que les arêtes de T, dans l’ordre où elles ont été ajoutées pour former T, soient e1, e2 , …, ek , …en−1 et que e = ek et pour tout i<k, ei ∈T’ .
Soit C le cycle en T’+ e qui contient e. soit f une arête de C qui n’est pas dans T’. Nous notons que par la nature de l’algorithme de Kruskal, le poids de f doit être supérieur au poids de e. En effet, au moment où nous avons placé e dans T, f était également disponible et n’aurait pas produit de cycle (puisque toutes les arêtes de T jusqu’à ce point sont également dans T ‘). Donc si w(f)<w(e), nous aurions utilisé f à ce stade. Alors maintenant l’ensemble T*=T’+e−f est un arbre couvrant de poids inférieur à T’, une contradiction.
Exercice 5
Considérons un algorithme de Kruskal « inversé » pour calculer un MST. Initialisez T comme étant l’ensemble de toutes les arêtes du graphe. Maintenant, considérons les arêtes du plus grand au plus petit coût. Pour chaque arête, supprimez-la de T si cette arête appartient à un cycle dans T. En supposant que tous les coûts d’arête sont distincts, ce nouvel algorithme calcule-t-il correctement un MST ?
Oui. À l’étape k (démarrant a k = 1), l’algorithme considère le k-ième plus grand avantage de coût. Si cette arête appartient à un cycle dans le graphe restant T, alors toutes les arêtes de ce cycle (et en fait de T) doivent avoir un coût inférieur à celui de l’arête considérée. Ainsi, l’arête ne peut pas appartenir au MST (par la question précédente).
L’algorithme ne peut pas se terminer avec T ayant un cycle, car l’algorithme aurait considéré chaque arête dans un tel cycle et aurait supprimé l’arête du coût le plus élevé lorsqu’il a considéré cette arête. L’algorithme ne peut pas non plus se terminer avec T déconnecté, car les arêtes ne sont supprimées que lorsqu’elles appartiennent à un cycle, et la déconnexion d’une arête qui appartient à un cycle ne déconnecte pas le graphe. Ainsi, l’algorithme se termine avec T étant un arbre couvrant.
C’est le MST car toutes les arêtes qui ont été supprimées ont la propriété de ne pas appartenir au MST. Étant donné que les seules arêtes qui pourraient appartenir au MST sont celles qui restent, et qu’elles définissent en effet un arbre couvrant, ce doit être le MST.
FR 
EN 
ES