Bonjour,
Dans le cadre de mon master, on a un cour de Graphe et Recherche Opérationnelle et je voulais m'amuser un peu... à mon dépend pour finir...
En fait, j'avais commencé à retracer un graphe représentant un pentagramme fermé (on venait de parler du graphe de Petersen)
Puis j'ai commencé à faire toutes les combinaisons possibles, tous les sous ensembles de graphes possible à partir de ce graphe...
J'ai commencé seulement et mal de surcroît parce que j'avais fait en fonction des sommets et non pas des arêtes...
Du coup je trouvais un nombre de sous graphe possible de
Bon c'est faux puisque je me suis rendue compte que j'oubliais un bon nombre de cas...
Ne serait-ce qu'en gardant trois sommets A, B, C
Je peux obtenir les graphes {ABC}, {AB,C}, {AC, B}, {BC, A}, {A,B,C} {}
En fait, le nombre de sous graphe se fait fonction du nombre d'arrêtes et non pas de sommet.
Toujours est-il que je me suis dit que je n'avais qu'à écrire un algorithme qui me permettrait de sortir tous les sous ensembles existant pour ce graphe...
Et là j'ai bloqué directement... J'ai tenté de faire une relation avec un parcours de graphe en profondeur... voir si je pouvais jouer avec et de la récursivité...
Mais je n'arrive pas à modéliser cet algorithme...
Je n'arrive pas non plus à trouver d'algorithme déjà existant pour... construire (lister) tous les sous ensembles possible de ce graphe...
Donc auriez vous des sources concernant ce type d'algorithme exhaustif ?
Ou alors un point de départ sur lequel je pourrai démarrer ?
Merci à vous :3
Partager