Probleme de garph

par **amine801** » 06 Jan 2007, 01:40

salut
De connaître le nombre de graphes existant pour n sommet
Dans le cas ou le renomage des sommets importe peux
Soit a un isomorphisme pres
On a ainsi
(1)--->(2)--->(3)
(3)--->(1)--->(2)
represente le meme graph

par **amine801** » 06 Jan 2007, 02:04

je vois que j'ai copier mon msg n'importe coment je me permet de rectifier:

salut
pour des graph non oriente avec n somet je recherche
le nombre exacte de graph a un isomorphime pres
(sans nomage de sommet)

dans le cas ou on nome les somets ca fait du

NB:
(1)--->(2)--->(3)
(3)--->(1)--->(2)
represente le meme graph
__________________

par **bauzau** » 06 Jan 2007, 10:57

bonjour,

je pense que tu peux chercher du coté des groupes de permutation Sn

en effet par exple le groupe S3 agit sur le graphe a 3 sommet.

or le groupe Sn possede (n!) permutation

par exple S3={id,(ab),(bc),(ac),(abc),(acb)}

où id peut représenter le graphe a b c (sans arrete)
(ab) represente le graphe a --> b
...
(abc) le graphe a --> b --> c (equivalent à b-->c-->a et c-->a-->b )

de meme on a S4=S3U{(ad),(bd),(cd),(abd),(acd),(abcd),(abdc),(adbc),...}

je sais pas trop si c'est ce que tu cherches...

par **amine801** » 06 Jan 2007, 11:08

pour n=4 dans le cas du nomage des somets le nombre de graph est 64
si les somet ne sont pas nome ca fait du 11
donc ce que je veux c'est de calculer le nombre de graph
dans le cas ou le nomage importe peux
ainsi par exemple il existe un seul graph sous forme de triangle

par **amine801** » 06 Jan 2007, 11:39

si c'est pas claire dite le moi je pourais essayer de mieu m'exprime
Jen est besoin et je seche help please :marteau:

par **bauzau** » 06 Jan 2007, 11:50

je suis sur d'avoir deja vu quelque chose de ce type où le groupe des permutation agissait sur un carré, et où on devait retrouvé le nombre de possibilité de couleur d'arrete (2 couleur qui peuvent représenter le sens), et dont les nom des sommets n'intervenaient pas: on devait regrouper en classe d'équivalence les carrés de même "nature".

il y a peut etre un moyen plus simple ou plus rapide, perso je n'es pas trop le temp de me mettre dessu, je suis en pleine révision dsl!

par **amine801** » 06 Jan 2007, 14:05

si quelqu'un a une idee il faut esitez

par **amine801** » 06 Jan 2007, 14:21

Il ya pas damateur Excuse moi de vous harceler mais jai besoin du résultat pour calculer la complexité optimal
Dun certain algorithme

par **amine801** » 06 Jan 2007, 21:10

Je me résigne je crois que cest incalculable
Au mieux jarrive à trouver une majoration

Probleme de garph

probleme de garph

Qui est en ligne