Loading AI tools
sous-graphe connexe De Wikipédia, l'encyclopédie libre
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.
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
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.
Une composante connexe d'un graphe non-orienté peut être définie comme un sous-graphe connecté qui n'est inclus dans aucun sous-graphe connecté plus grand. Par exemple, le graphe représenté sur l'illustration ci-dessus contient trois composantes connexes. Chaque sommet d'un graphe appartient à l'une de ses composantes connexes, qui est le sous-graphe induit de l'ensemble des sommets atteignables à partir de ce sommet. Tout graphe est constitué de l'union disjointe de ses composantes connexes.
Les exemples suivants illustrent différents cas particuliers de composantes connexes :
La recherche des composantes connexes d'un graphe est un problème classique qui peut être résolu en temps linéaire (en fonction du nombre de sommets et d'arêtes du graphe). On peut utiliser pour cela soit un algorithme de parcours en profondeur, soit un algorithme de parcours en largeur. Dans un cas comme dans l'autre, la recherche démarre sur un sommet quelconque du graphe et va identifier toute la composante connexe qui le contient une fois le parcours terminé. Il suffit alors de réitérer une recherche en profondeur ou en largeur à partir d'un sommet qui n'a pas encore été parcouru pour identifier progressivement toutes les composantes connexes[1].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
