Graphe: forte connexité

[ugoboss]

Bonjour tout le monde!

Voila le sujet que je dois traiter.

http://yfrog.com/e0piix038j

J'ai déjà répondu à toutes les questions mais je ne suis pas certains de les avoir bien traiter.

Je vais donc essayer de synthétiser mes réponses aux questions auxquelles je ne suis pas certain d'avoir juste afin que vous me corrigiez éventuellement.

a) Interpréter âij=1

Si âij=1 alors il existe un chemin de longueur quelconque entre i et j.

b) On a démontrer que la relation F est réflexive, transitive et symétrique (immédiat).



Comment obtient-on A' à partir de A?

On obtient A' a partir de A en mettant que des 0 sur la diagonale et des 1 sur la partie supérieur (ou inférieur de la diagonale)
(âij=1 U âji=1) ^ âii=0 )



Quel propriété possède le graphe G?

Le graphe G est un graphe complet: chaque point du graphe ne possèdent pas de boucle sur lui-même, il existe une chaîne reliant x à y (x et y € G).


a) Interpréter âij=1

Il existe une chaîne de longueur 1 entre i et j (longueur 1 car les sommets i et j sont adjacents, et il existe une chaîne car G' est un graphe complet).

b) On définit dans X une nouvelle relation S:

- Elle est réflexive car par convention tout sommet est une chaîne de longueur 0.

-Elle est symétrique car il existe une chaîne ]x...y[, donc une chaine ]y...x[, donc on a quelque soit x,y appartenant à X, xSy => ySx

-Elle est transitive car tout les points du graphe sont adjacent (graphe complet) donc quelque soit x,y,z € X [(xSy)^(ySz)]=>(xSz).

La relation S est une relation d'équivalence. Cette classe d'équivalence est appelée composante connexe de x.

Sachant qu'on a â'ij=1, on a donc j€ C(i).



Merci d'avance.