Discussion :

[jophar]

Bonjour à tous,

quelqu'un pourrait m'expliquer comment reconnaitre ou trouver une composante connexe ou fortement connexe?

Merci...

[Nemerle]

pourrait-on avoir plus de détails?

[jophar]

Bonjour à tous
Voilà un graphe,pour mieux comprendre quelqu'un pourrait m'aider à déterminer si le graphe est fortement connexe ou non et s'il ne l'est pas m'aider à retrouver les composantes connexes et fortements connexes
la matrice d'adjacence
Urgence,
Merci

[Alexis.M]

Quelle est la définition d'un graphe connexe ? Quelle est la définition d'un graphe fortement connexe ?

La matrice d'adjacence est construite en mettant un 1 à l’élément ij si il existe un arc allant de i vers j.

[jophar]

Bonjour,
Pour mon graphe ma matrice est:

1 2 3 4 5 6 7
1 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0
3 0 0 0 0 1 0 0
4 0 0 0 1 0 0 0
5 0 0 1 0 0 0 0
6 0 1 0 0 0 1 0
7 0 0 0 0 1 0 0

un graphe est connexe si chaque sommet est accessible depuis tous les autres sommets.si je m'en tiens à cette définition,je peux dire que mon graphe n'est pas connexe.
Un graphe peut ne pas être connexe et avoir des compasantes connexes?
d'après cette définition,est ce qu'il est possible de dire que {4},{6},{5,3} sont des composantes connexes de mon graphe?

Pour un graphe fortement connexe, les couples de sommets sont accessibles chacun depuis l'autre.
composante fortement connexe ici pour mon graphe est {3,5}

Je ne sais pas si j'ai bien compris cette partie.

Merci.

[Alexis.M]

Cela me semple correct, mais je ne suis pas spécialiste

[pseudocode]

Bonjour,
Pour mon graphe ma matrice est:

1 2 3 4 5 6 7
1 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0
3 0 0 0 0 1 0 0
4 0 0 0 1 0 0 0
5 0 0 1 0 0 0 0
6 0 1 0 0 0 1 0
7 0 0 0 0 1 0 0

un graphe est connexe si chaque sommet est accessible depuis tous les autres sommets.si je m'en tiens à cette définition,je peux dire que mon graphe n'est pas connexe.
Un graphe peut ne pas être connexe et avoir des compasantes connexes?
d'après cette définition,est ce qu'il est possible de dire que {4},{6},{5,3} sont des composantes connexes de mon graphe?

Pour un graphe fortement connexe, les couples de sommets sont accessibles chacun depuis l'autre.
composante fortement connexe ici pour mon graphe est {3,5}

Je ne sais pas si j'ai bien compris cette partie.

Merci.

Les composantes connexes ne sont définies que sur un graphe non-orienté. L'orientation des arcs n'intervient donc pas, il suffit que les sommets soient reliés entre eux : {6,2} {3,5,7} {4}

Les composantes fortement connexes sont définies sur un graphe orienté. Tous les sommets d'une composante doivent être atteignables depuis un autre sommet quelconque de la composante: {3,5} {4} {6}

Pour trouver les composantes connexes, il suffit de parcourir le graphe.

Pour trouver les composantes fortement connexes, on peut par exemple parcourir le graphe deux fois (dans un sens, puis dans l'autre).

[jophar]

Bonjour,

Merci pour l'explication,
par conte {4} est atteignable depuis lui même et {6} également,
est ce suffisant pour dire que ce sont des composantes fortement connexes?

[pseudocode]

Bonjour,

Merci pour l'explication,
par conte {4} est atteignable depuis lui même et {6} également,
est ce suffisant pour dire que ce sont des composantes fortement connexes?

Bah, je suis parti du principe que s'il y a un arc réflexif sur {4} et {6}, c'est que par défaut les sommets ne sont pas atteignables a partir d'eux même. Et donc {4} est bien une composante fortement connexe, alors que {1] ne l'est pas.

[jophar]

Merci pour les explications,

J'aurai une autre question à poser???

A quoi sert le sert le calcul de la complexité dans un graphe orienté ou non?

Merci...

[Alexis.M]

Je ne suis pas bien sûr de ce que tu appelles le "calcul de la complexité" dans les graphes, mais les graphes en général dans mon expérience servent à modéliser des réseaux ou des relations entre des éléments pour ensuite par exemple effectuer des calculs de distance entre élément ou de temps de parcours à partir d'un graphe.

[jophar]

Ok,

je te remercie...