A voir également:
- Programme enumérant les stables d'un graphe
- Programme demarrage windows - Guide
- Mettre en veille un programme - Guide
- Desinstaller un programme - Guide
- Programme word gratuit - Guide
- Cette action ne peut pas être réalisée car le fichier est ouvert dans un autre programme - Guide
2 réponses
Bonjour,
qu'est-ce que tu appelles les "stables" d'un graphe orienté ?
qu'est-ce que tu appelles les "stables" d'un graphe orienté ?
alexie
Merci Pacorabanix pour ta réponse , au fait , les stables sont les sous-graphes ne contenant aucune arète ( les sommets sont deux à deux disjoints )
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.
je ne sais pas si cette manière de faire te parle. J'espère t'avoir aidé.
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é.
