Discussion:Composante fortement connexe
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Cet article est indexé par le projet Mathématiques.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| Ébauche | À évaluer |  | Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues) |
Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.
Connexité et forte connexité ; orienté et non-orienté[modifier le code]
Il me semble que le terme connexe et fortement connexe se s'adressent pas respectivement aux graphes non orienté et orienté, mais: connexe: si il existe une chaine reliant tous sommet de G, il est dit connexe (graphe orienté ou non orienté) fortement connexe: il existe un chemin reliant tout sommet de G, il est dit fortement connexe (graphe orienté ou non orienté)
Mais sachant que dans un graphe non orienté, si un chemin existe entre deux sommets, lui et son inversion droite gauche (permutation de lecture) sont des chemins, donc tout graphe non orienté, s'il est connexe est fortement connexe.
Ce qui n'est pas forcément vrai pour le graphe orienté car si un chemin orienté existe, sa permutation droite gauche de lecture n'existe pas forcément (puisque justement orienté).
Cordialement Bmoraut (d) 30 mars 2011 à 10:17 (CEST)Bmoraut 30/03/2011
- Usuellement, la forte connexité n'est définie que pour les graphes orientés, justement parce qu'elle est équivalente à la connexité tout court sur les graphes non orientés.
- Inversement, on parle parfois de composante connexe (pas fortement) sur un graphe orienté. Ça veut dire qu'on "oublie" l'orientation des arêtes. Mais c'est plus un abus de langage, je ne suis pas sûr que cet emploi soit généralisé.
- La présentation actuelle correspond à ce qui est fait Introduction to Algorithms (annexe B) par exemple. Mais effectivement, le lien entre les deux notions n'est pas très clair en l'état. N'hésitez pas à reprendre les articles si ça vous intéresse.
- Cordialement,
- Nordald (d) 30 mars 2011 à 13:18 (CEST)
Maximalité[modifier le code]
Bonjour,
est-ce que la maximalité mentionnée dans le RI est toujours présente dans la définition ? Je n'avais pas cette aspect dans ma définition... --Roll-Morton (discuter) 22 juin 2018 à 14:46 (CEST)
- Ça me paraît correct : un sous-graphe est fortement connexe s'il y a des chemins entre toute paire de sommets, et une composante fortement connexe est un sous-graphe maximal avec cette propriété (et la version anglaise est d'accord). -- ManiacParisien (discuter) 29 juin 2018 à 19:55 (CEST)
- Ok, ça marche, merci ! --Roll-Morton (discuter) 6 juillet 2018 à 12:14 (CEST)