Discussion :

[Tarrke]

Salut à tous,

voilà je cherche à créer un graphe d'une certaine manière. je possède les sommets de mon graphe mais pas les arcs correspondants. La seule contrainte sur ce graphe est qu'a patir d'un sommet on doit pouvoir atteindre tous les sommets.

Si quelqu'un pouait me fournir une piste de recherche...

Merci,
Tarrke

[Pouic]

http://fr.wikipedia.org/wiki/Th%C3%A9orie_des_graphes

graphe connexe...

[Tarrke]

yeah !

merci pour le nom de ces graphes, ils m'échappaient depuis ce matin

[FrancisSourd]

S'agit-il d'un graphe orienté (graphe connexe) ou non orienté (graphe fortement connexe)?

Le principe le plus simple est de rajouter des arcs aléatoirement jusqu'à obtenir un graphe connexe. On peut continuer après d'ailleurs, si on veut plus d'arc. Les composantes connexes sont des classes d'équivalences, on peut utiliser la structure union/find pour effectuer rapidement la réunion de deux composantes connexes.

Inversement, on peut partir d'un graphe complet et enlever des arêtes aléatoirement (sauf lorsqu'on tombe sur une arête qui diviserait le graphe en 2 composantes et donc on la garde, une telle arête est appelée un isthme).

[Clad3]

La seule contrainte sur ce graphe est qu'a patir d'un sommet on doit pouvoir atteindre tous les sommets

Si c'est la SEULE contrainte , moi je mettrai des arcs entre tout les sommets :p