Composante connexe (théorie des graphes)

Carte Commune · n° 345018

En théorie des graphes, une composante connexe d'un graphe non orienté est un sous-graphe connexe qui ne fait partie d'aucun sous-graphe connexe plus grand. Les composantes connexes de tout graphe divisent ses sommets en ensembles disjoints et sont les sous-graphes induits de ces ensembles. Un graphe connexe a exactement une composante connexe, constituée du graphe entier. Le nombre de composantes connexes dans un graphe donné est un invariant important du graphe et est étroitement lié aux invariants des matroïdes, des espaces topologiques et des matrices. Dans les graphes aléatoires, un phénomène fréquent est l'existence d'une composante connexe géante, nettement plus grande que les autres, et d'un seuil de percolation, une densité d'arêtes limite au-dessus de laquelle une composante géante apparaît et en dessous de laquelle elle n'existe pas. Les composantes connexes d'un graphe peuvent être construites en temps linéaire.

Lire sur Wikipédia · Image David Eppstein, Public domain