RO03

Evolution des composantes connexes

Qu'est-ce qui arrive quand on démarre avec un graphe vide et on ajoute des arêtes entre les sommets d'une manière aléatoire? En ajoutant de plus en plus d'arêtes, le nombre de composantes connexes dans le graphe pourrait diminuer au fur et à mesure, jusqu'à ce que, finalement, le graphe soit connecté.

Cette animation nous montre l'évolution de la grande composante par des insertions aléatoires de sommets. La composante formée par la fusion de deux autres composantes différentes, prend la couleur de la plus grande des deux parties. Donc, nous pouvons remarquer comment la couleur orange domine le graphe quand les éléments se fusionnent.