programme enumérant les stables d'un graphe Fermé

Question

Bonjour,
Je dois réaliser un programme en java ( un pseudo-code me serait suffisant ) permettant de lister tous les stables d'un graphe non orienté . Je ne sais pas d'où commencer :s

Merci pour votre aide ...

Pacorabanix · Answer

Bonjour,
qu'est-ce que tu appelles les "stables" d'un graphe orienté ?

Pacorabanix · Answer

Et bien ça dépend de tes connaissances en algo et en structure de donnée.

J'imagine, juste pour le principe, quelque chose de récursif.

Tu as ton graphe (la liste des sommets).
Tu as la liste des arêtes associées à chaque sommet.

Le mieux seraient que ces listes soient en fait des "Set", des ensembles, ça rendraient les choses plus simple à programmer.

Fonction (récursive) qui trouve sous-graphe "stables"[ paramètres : un ensemble E de sommet d'un graphe ainsi qu'un ensemble F qui contient les sommets de ton sous graphe stable]
Si le graphe donné en paramètre n'est pas vide :
  Pour chaque sommet du graphe E
    Ajouter à F stable le sommet
    Supprimer du graphe E le sommet ajouté ainsi que tous les sommets connectés (en utilisant la liste d'aretes)
    Réappeler la même fonction avec comme graphe le graphe "élagué" E (avec les sommets supprimés), et le sous-graphe F avec le point en plus.
  Fin Pour
Sinon
  Afficher le sous-graphe stable F, car c'est fini.
Fin Si
je ne sais pas si cette manière de faire te parle. J'espère t'avoir aidé.

Programme enumérant les stables d'un graphe

2 réponses

Discussions similaires