Supposons que nous exécutions l'algorithme de Kruskal pour déterminer l'arbre couvrant de poids minimal sur le graphe ci-dessous. Dans quel ordre les arêtes seront-elles ajoutées à l'arbre couvrant minimal ?

Soit le graphe  suivant :

Répondre aux questions suivantes par vrai ou faux.

Si un graphe non-orienté connexe comporte une arête e de coût minimum qui est unique, alors cette arête est forcément incluse dans tout ..........................

Si un graphe G contient un sous-graphe complet de p sommets, alors   ?

................... d'un graphe est le nombre minimum de couleurs affecté aux arêtes, c’est-à-dire attribution de couleurs aux arêtes de telle sorte qu'aucun sommet ne soit incident à deux arêtes de même couleur (*)

L'algorithme de Prim et l'algorithme de Dijkstra résolvent tous deux le problème du chemin le plus court à partir d'une source unique.

Exécutez l'algorithme de Kruskal sur le graphe ci-après. Dans votre réponse, listez l'ordre dans lequel les arêtes sont ajoutées à l'arbre couvrant de poids minimal.

Listez les arêtes dans ce format : E1, E2, E3,...

Existe-t-il une coloration à 2 couleurs du graphe suivant ?

Existe-t-il une coloration à 2 couleurs du graphe suivant ?

Supposons que nous exécutions l'algorithme de Kruskal pour déterminer l'arbre couvrant de poids minimal sur le graphe ci-dessous. Dans quel ordre les arêtes seront-elles ajoutées à l'arbre couvrant minimal ?