Bonjour à tous,
Nous étudions en cours la théorie des graphes.
J'ai un peu près tout compris les quelques définitions que nous avons vus sauf lorsqu'il s'agit de composantes connexes et fortement connexes.
D'après ce que j'ai compris,une composante fortement connexe est en fait un sous graphe où on peux relier n'importe quel couple de sommets entre eux.
Mais comment se fait-il qu'ici par exemple,ils trouvent 3 composantes connexes?
Une composante connexe est intuitivement un groupe de sommets d'un seul tenant, qui n'est pas relié aux autres groupes. Sur cette figure, on voit bien qu'il y a trois groupes de sommets qui "tiennent ensembles". Ce sont les trois composantes connexes.
Plus formellement, deux sommets <math>\(u,v\)</math> appartiennent à des composantes connexes différentes si et seulement si il n'existe pas de chemin entre <math>\(u\)</math> et <math>\(v\)</math>.
D'après ce que j'ai compris,une composante fortement connexe est en fait un sous graphe où on peux relier n'importe quel couple de sommets entre eux.
Mais comment se fait-il qu'ici par exemple,ils trouvent 3 composantes connexes?
Les composantes connexes s'appliquent à des graphes non orientés et les composantes fortement connexes à des graphes orientés. L'image classique que l'on utilise pour décrire ces deux notions est la suivante : imagine une ville, les rues sont les arêtes du graphe et les sommets sont les croisements comme A2 dans le dessin ci-dessous (ou les fond d'impasses comme B ci-dessous). Si on se déplace à pied on peut circuler sur les trottoir dans n'importe quel sens. Si on se déplace en voiture, on peut circuler mais en respectant les sens interdits.
Dans ces conditions :
*) Une composante connexe est un quartier dont un piéton ne peut sortir mais dont tous les carrefours lui sont accessibles.
*) Une composante fortement connexe est un quartier dont une voiture ne peut sortir mais dont tous les carrefour lui sont accessibles.
Pour ce qui concerne le graphe que tu as proposé, il a bien trois composantes connexes :
D'une part, par exemple tu peux aller de n'importe quel point Ai à n'importe quel point Aj en suivant des arêtes mais tu ne peux aller de A1 par exemple à B. Donc A1 et B sont dans deux composantes connexes différentes. La troisième composante est constituée des sommets de la partie où je n'ai pas donné de noms.
Une composante connexe est toujours connexe bien sûr. C'est en fait une classe d'équivalence pour le relation "est reliée par un chemin à".
pourquoi faut-il que ces graphes fortement connexe soient orientés ?
La même propriété ne pourrait pas s'appliquer à des graphes non-orientés en disant qu'il est fortement connexe si pour tout u et v deux sommet du graphe, il existe un chemin de u à v.
et visuellement, un graphe non fortement connexe serait "séparé".
pourquoi faut-il que ces graphes fortement connexe soient orientés ?
C'est la définition de "fortement connexe" donc ta question "pourquoi" n'a pas de sens, cf. toutefois ta dernière question.
Citation : hedi07
La même propriété ne pourrait pas s'appliquer à des graphes non-orientés en disant qu'il est fortement connexe si pour tout u et v deux sommet du graphe, il existe un chemin de u à v.
Oui, on pourrait mais si le graphe est non orienté, l'usage est juste d'utiliser le terme de "connexe", sans plus. Toutefois, un graphe non-orienté est un cas particulier de graphe orienté (remplacer chaque arête par deux arcs, chacun orienté dans des sens différents).
Citation : hedi07
et visuellement, un graphe non fortement connexe serait "séparé".
Non, justement et c'est pour ça que le terme de fortement est justifié : si un graphe est fortement connexe alors si tu retires les orientations des arcs, le nouveau graphe doit être connexe. Mais cela ne suffit
pas pour être fortement connexe. La meilleure façon de comprendre la différence entre les deux est de reprendre l'image que j'ai donnée plus haut (les rues d'une ville).
Wikipedia dans un article sur la connexité des graphes orientés donne un excellent exemple d'un graphe qui, orienté, a trois composantes fortement connexes. Pourtant ce même graphe, si on enlève l'orientation, est parfaitement connexe.
Bah on peut faire encore plus simple: 2 sommets (a et b) joints par une arête orientée dans un seul sens (de a vers b).
Le graphe non orienté correspondant est connexe, mais le graphe orienté possède deux composantes fortement connexes (les deux sommets) car aucun chemin de va de b à a.
Avant de poster, demandez-vous si ce que vous allez dire apporte quelque chose au sujet. Si votre message n'apporte rien, vous ferez perdre du temps à tout le monde et le sujet pourrait dévier ou devenir difficile à suivre.
Aussi, vérifiez la date du topic. Le déterrage de topic nuit au bon fonctionnement du forum et est interdit. Utilisez les boutons pour dire merci. Si le topic date de plus de deux mois sans réponses, mieux vaut ne pas répondre. Si vous avez une question similaire, créez plutôt votre propre sujet en détaillant votre contexte
Moderateur forum || FAQ 3D || discord 3D francophone || OC Tweak script