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

[Obsidian]

Ah, effectivement si on parle des sous-ensembles de E, alors ok. Mais ce que j'ai compris de l'exemple de Deallyra [...] j'en ai conclu qu'elle voulait l'ensemble des partitions (+ l'element vide) , c'est à dire Bell(3)+1 = 6

Je pense également comme toi, mais sa définition semble erronée (et biaise son approche) :

En fait, le nombre de sous graphe se fait fonction du nombre d'arrêtes et non pas de sommet.

Un sous-graphe s'obtient bien en retirant des sommets d'un graphe initial et − par conséquent − les arêtes qui les rallient, à l'exception de toutes les autres (c'est nécessaire car, sinon, on se retrouverait avec des arêtes ayant des extrémités dans le vide).

Un graphe partiel s'obtient en retirant des arêtes, mais en conservant tous les sommets.

Dans les deux cas, on s'aperçoit que l'approche est la même : on inclut ou exclut un élément indépendamment des autres (dans le cas du sous-graphe, les arêtes exclues par induction sont déterminées automatiquement. Il n'y a pas plusieurs cas possibles). Le seul problème est que dans l'exemple du graphe complet K5 présenté ici, il y a dix arêtes (5 × 4 ÷ 2 = 10). Ça fait donc 2^10 = 1024 graphes partiels possibles, mais ça reste faisable.

[Deallyra]

Bonjour Pseudocode, Bonjour Obsidian,

Merci à vous deux et toutes mes excuses de ne pas être intervenue plus tôt.

En effet, on parle bien de 1024 graphes possibles...
J'étais arrivée à 32 graphes en faisant seulement des... rotations avec les sommets.

A savoir, je cherchais à voir combien de graphes je pouvais faire en prenant un sommet (5)
Puis, combien je pouvais faire en prenant deux sommets. Puis trois. Puis quatre, puis cinq.
Et également zéro... Mais celui ci je l'avais oublié la première fois
(donc en fait, on rejoint ton système de balles dans des boites Pseudocode)
edit: en fait non >.< On ne rejoint pas ton système de balles ^^'
J'avais mal compris

Mais comme exprimé ensuite, je n'avais pas vu toutes les possibilités de sous ensemble pour le graphe de base.

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

Oui dans le cas où on s'occupe des sommets mais en ce cas on ne gère que les sommets et non pas les arêtes.
C'était cependant ma première approche du problème.
avec le sous ensemble {3,2,1}, on peut obtenir plusieurs graphes selon les arrêtes que l'on choisi de prendre en compte ou non.

Mais pour le coup, oui il s'agissait bien du 2^n :3

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.
(...)
Soit un total de 52 partitions (non vides)

Je vais voir ton lien sur Bell cependant ce n'est pas réellement ce que je souhaite. Ou du moins, selon l'approche que tu as laissée dans ton message.

On est toujours en train de gérer des sommets alors que j'aimerai être plus rapidement orientée sur des arêtes.

Par exemple, je donnerai en entrée de mon algo un fichier où j'ai l'ensemble de mes arrêtes de décrites.

Le problème est que j'ai l'impression qu'avec ce que tu as mis Pseudocode, je n'aurai aucune gestion réelle des arrêtes que je peux avoir dans mon graphe mais réellement toutes les connexions possibles entre tous les sommets...

Je pense également comme toi, mais sa définition semble erronée (et biaise son approche) :

Je suis vraiment désolée du fait de mon manque de connaissance ne me permettant pas de vous parler avec des termes précis ce qui permettrait de mieux me faire comprendre

[pseudocode]

On est toujours en train de gérer des sommets alors que j'aimerai être plus rapidement orientée sur des arêtes.

Par exemple, je donnerai en entrée de mon algo un fichier où j'ai l'ensemble de mes arrêtes de décrites.

Le problème est que j'ai l'impression qu'avec ce que tu as mis Pseudocode, je n'aurai aucune gestion réelle des arrêtes que je peux avoir dans mon graphe mais réellement toutes les connexions possibles entre tous les sommets...

Tu veux dire que ton graphe de départ n'est pas forcément complet ? Et que tu veux énumérer tous les sous-graphes de ce graphe ?

[Obsidian]

A savoir, je cherchais à voir combien de graphes je pouvais faire en prenant un sommet (5) Puis, combien je pouvais faire en prenant deux sommets. Puis trois. Puis quatre, puis cinq.

Dans l'absolu, une infinité, puisque tu peux faire un multigraphe en tirant plusieurs arêtes entre deux mêmes sommets. C'est ce qui se passe avec les ponts de Kœnigsberg, d'ailleurs. Après, tu peux poser des limites, mais il faut au moins dire si tu considères ton graphe comme orienté ou pas, et si tu autorises les boucles.

Le problème est que j'ai l'impression qu'avec ce que tu as mis Pseudocode, je n'aurai aucune gestion réelle des arrêtes que je peux avoir dans mon graphe mais réellement toutes les connexions possibles entre tous les sommets...

Si tu veux savoir combien on peut faire de relations entre n sommets, avec une seule arête au maximum entre deux mêmes sommets, ça s'appelle le lemme des poignées de mains et c'est égal à n × (n-1) ÷ 2. C'est assez facile à expliquer : si tu as dix sommets, chacun d'un est relié aux neuf autres, soit 10 × 9 et comme une arête relie toujours deux sommets, il y a deux fois moins d'arêtes que de degrés. Donc, pour dix sommets, on a 45 arêtes.

Après, pour faire des graphes partiels avec, ça fait 2^45 possibilités. On comprend que cela explose vite (doublement du nombre de possibilité avec chaque nouvelle arête).

Je suis vraiment désolée du fait de mon manque de connaissance ne me permettant pas de vous parler avec des termes précis ce qui permettrait de mieux me faire comprendre

Oui, enfin, je gaze un peu mais, en réalité, je n'ai pas beaucoup plus de connaissances :-) Par contre, il y a un glossaire très précis en théorie des graphes que l'on apprend généralement en début de cursus parce que beaucoup de notions sont proches mais distinctes. Du coup, on a vite fait de se perdre. Par exemple, une boucle est un arc qui part et arrive vers le même sommet, un cycle est un chemin transitif qui revient à son point de départ, un circuit est la même chose, mais dans un graphe orienté, etc.

http://rperrot.developpez.com/articl...eorie/graphes/
http://cours.ensem.inpl-nancy.fr/cou.../glossary.html

[Deallyra]

Lorsque j'avais dessiné le pseudo graphe de petersen, j'avais pour idée de me limiter à lui.

Maintenant, tant qu'à faire un algo, autant qu'il soit générique.

Par exemple, me dire que j'ai un graphe de quatre sommets et que j'ai

A -> B
B -> C
B -> D
C -> A
D -> B

Et là, comment je fais pour trouver tous les sous graphes de ce graphe...

C'était un peu l'idée que j'avais

[Obsidian]

Lorsque j'avais dessiné le pseudo graphe de petersen, j'avais pour idée de me limiter à lui.

Attention : le graphe de Petersen, ce n'est pas le K5. Il a dix sommets et quinze arêtes : [ame]http://fr.wikipedia.org/wiki/Graphe_de_Petersen[/ame]

A -> B
B -> C
B -> D
C -> A
D -> B

Et là, comment je fais pour trouver tous les sous graphes de ce graphe...

Encore une fois, si tu te penches sur les sous-graphes, tu te penches sur la suppression de sommets et le nombre de sous-graphes est alors forcément égal à 16 puisque qu'un sommet peut faire partie de ton graphe même si aucune arête ne l'atteint.

Si tu te penches sur les graphes partiels, tu laisses les sommets intacts, mais tu retires des arêtes. Comme il y en a cinq, tu as forcément 2^5 = 32 graphes partiels possibles.

Si, enfin, tu veux trouver toutes les combinaisons possibles en enlevant sommets et arrêtes, alors il faut d'abord énumérer chaque sous-graphe et faire le bilan des arêtes qu'il lui reste. De là, tu trouves la puissance de 2 correspondant à ce nombre et tu la cumules avec celles des autres sous-graphes.

[pseudocode]

Et là, comment je fais pour trouver tous les sous graphes de ce graphe...

Si tu parles des sous-graphes connexes, a part une exploration complète des chemins, je ne vois pas trop...

[Deallyra]

@Obsidian

Oui enfin un graphe ressemblant au graphe de Petersen :s
J'étais partie de ce graphe que j'ai modifié


je suis de moins en moins claire :s

@Pseudocode

Les graphes connexes... Ce serait peut être plus simple si je partais de ça...
Et ça limiterait le nombre de résultat.


Pour ce faire, il me "suffirait" de tester tous les chemins passant par tous les sommets une seule fois

[Obsidian]

@Obsidian

je suis de moins en moins claire :s

C'est-à-dire que tu as visiblement une idée précise derrière la tête mais on ne sait pas encore laquelle.

Pour trouver tous les graphes partiels, sachant qu'il y a deux possibilité par arête (l'inclure ou pas), on peut faire un compteur binaire qui compte de 0 à (2^n)-1 et mapper chaque arête sur un bit. Ainsi, tu obtiendras A, B, AB, C, AC, BC, ABC, D, AD, etc. et tu seras sûre de ne pas en oublier.

Maintenant, si tu cherches à faire des groupes au sein d'un graphe en conservant tous ses éléments (sommets et arêtes), il s'agit effectivement de faire des partitions et, dans ce cas, il faut suivre les indications de Pseudocode.