Discussion :

[Deallyra]

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

[pseudocode]

Salut Deallyra,

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.

Visiblement, tu cherches a calculer le nombre de partitions d'un ensemble de N éléments (ici N=3). => [ame]http://en.wikipedia.org/wiki/Bell_numbers[/ame]

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 ?

on peut voir le problème comme étant celui de mettre N balles dans 1, 2, ..., N boites.

Balles = A, B, C

Configurations avec 1 boite : {ABC}
Configurations avec 2 boites : {A,BC} {AB,C} {AC,B}
Configurations avec 3 boites : {A,B,C}

Est-ce que ca t'aide ?

[Obsidian]

Si ce sont vraiment des sous-ensembles qu'elle cherche, alors c'est plus simple que ça : il s'agit de l'ensemble des parties d'un autre ensemble et ça se détermine assez facilement :

Si on considère que chaque élément peut être soit inclus, soit exclu d'un sous-ensemble, et que le fait de choisir un élément n'affecte pas le choix des suivants, alors on en déduit qu'il y exactement 2^n sous-ensembles possibles, dont l'ensemble vide et le sous-ensemble contenant quand même tous les éléments. Donc, avec cinq sommets, ça fait 32 cas possibles.

{ {∅}, {1}, {2}, {1,2}, {3}, {3,1}, {3,2}, {3,2,1}, {4}, {4,1} ... }

[pseudocode]

Si on considère que chaque élément peut être soit inclus, soit exclu d'un sous-ensemble, et que le fait de choisir un élément n'affecte pas le choix des suivants, alors on en déduit qu'il y exactement 2^n sous-ensembles possibles, dont l'ensemble vide et le sous-ensemble contenant quand même tous les éléments. Donc, avec cinq sommets, ça fait 32 cas possibles.

Hum... J'ai du mal a voir d'ou sort le 2^n.

L'ensemble des partitions d'un ensemble de N éléments est égal a l'union des partitions à 1 élément + les partitions à 2 éléments + ... + les partitions à N élements. C'est à dire la somme des nombres de Stirling (= le nombre de Bell).

Pour N=5.

Partitions à 1 élément : {ABCDE}

Partitions à 2 éléments : {ABCD,E} {ABCE,D} {ABC,DE} {ABED,C} {ABE,CD} {ABD,CE} {AB,CED} {ADEC,B} {ADE,BC} {ADC,BE} {AD,BEC} {ACE,BD} {AC,BDE} {AE,BDC} {A,BDCE}

Partitions à 3 éléments : {ABC,D,E} {ABE,C,D} {AB,CE,D} {ABD,C,E} {AB,CD,E} {AB,C,ED} {ADE,B,C} {AD,BE,C} {ADC,B,E} {AD,BC,E} {AD,B,EC} {AC,BD,E} {A,BDC,E} {AE,BD,C} {A,BDE,C} {A,BD,CE} {AEC,B,D} {AE,BC,D} {AE,B,DC} {AC,BE,D} {A,BEC,D} {A,BE,DC} {AC,B,DE} {A,BC,DE} {A,B,DEC}

Partitions à 4 éléments : {AB,C,E,D} {AD,B,E,C} {A,BD,C,E} {AE,B,D,C} {A,BE,D,C} {A,B,DE,C} {AC,B,D,E} {A,BC,D,E} {A,B,DC,E} {A,B,D,EC}

Partitions à 5 éléments : {A,B,D,E,C}

Soit un total de 52 partitions (non vides)

[Obsidian]

Hum... J'ai du mal a voir d'ou sort le 2^n.

Parce que l'ensemble des parties, ou ensemble des sous-ensembles, n'est pas la même chose que l'ensemble des partitions. On l'utilise surtout en proba (premier exemple au pif : http://www.maths-express.com/bac-exo...partiesdee.htm )

Dans un sous-ensemble, tous les éléments choisis sont dans le même sac, mais rien n'oblige à sélectionner tous les éléments de l'ensemble original.

[pseudocode]

Parce que l'ensemble des parties, ou ensemble des sous-ensembles, n'est pas la même chose que l'ensemble des partitions. On l'utilise surtout en proba (premier exemple au pif : http://www.maths-express.com/bac-exo...partiesdee.htm )

Dans un sous-ensemble, tous les éléments choisis sont dans le même sac, mais rien n'oblige à sélectionner tous les éléments de l'ensemble original.

Ah, effectivement si on parle des sous-ensembles de E, alors ok.

Mais ce que j'ai compris de l'exemple de Deallyra:

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} {}

J'en ai conclu qu'elle voulait l'ensemble des partitions (+ l'element vide) , c'est à dire Bell(3)+1 = 6