graph

[invitea121f130]

salut
pour des graph nom oriente je recherche
je recherche le nombre exacte de graph a un isomorphime pres
dans le cas ou on nome les somets je sais que sa fait du
2^(n(n-1)/2)
-----

[invite6b1e2c2e]

Salut,
il suffit de calculer le nombre de liaisons possibles entre n points. C'est un petit exo de combinatoire assez facile.

__
rvz

[invitea121f130]

ca marche si les somets du graphe sont diferencie par nomage
ansi pour des graphes d'ordre n=4 ou les somets sont nome
le nombre de graph est 64
si les somet ne sont pas nome ca fait du 11 je crois

[invitea121f130]

hello je pourais avoir une reponse svp

[A voir en vidéo sur Futura]

[inviteccb09896]

Slt

Va voir sur :

http://www.sciences.ch/htmlfr/geomet...egraphes01.php

Définition (D5) il est indiqué comme c'est calculé (c'est de la combinatoire niveau terminale)

Si tu ne comprends toujours pas fait savoir je détaillerai si nécessaire.

Cordialement

[invitea121f130]

je crois que vous repondez pas exactement a la question
que j'ai pose il exacte qu'il trivial de trouve le nombre de graphe de n somet dans le cas ou les somets sont distinge par nomage[ 2^(n(n-1)/2) ]
mais ma question c'est de trouve le nombre de graphe si les somets ne sont pas nome et ou
les deux graphe
G: . .
.
F: . .
.
represente le meme graphe
j'espere que cette foit on repondra exactement a la
question que j'ai pose sans me demande d'aller revise ma combinatoire

[invite6de5f0ac]

Bonjour,

Je crois que je saisis ton problème... J'en ai eu un similaire, avec des graphes à n sommets, mais moi ils pouvaient être de deux couleurs différentes (noir ou blanc). Ça ne doit pas changer grand'chose à la question.

Je n'ai pas réussi à trouver de formule générale. À part une énumération bourrine, suivie d'un écrémage plus ou moins astucieux, suivi d'une détection rigoureuse des isomorphismes... Et encore, je n'avais besoin que jusqu'à n=8...

Si quelqu'un a une meilleure idée, je reste preneur. Et je suis d'accord que ce n'est pas "que" de la bête combinatoire.

-- françois

[invitea121f130]

moi je reusit au mieux a trouve une majoration cinom
cinom pour ce qui est de la valeur exacte j'avoue que j'ai
du mal

[invite6de5f0ac]

moi je reusit au mieux a trouve une majoration cinom
cinom pour ce qui est de la valeur exacte j'avoue que j'ai
du mal

Re,

Une majoration, oui, mais moi il me fallait la liste exacte desdits graphes, et pas simplement leur dénombrement. Quant à avoir même leur nombre exact, tintin, rien que pour n=4 j'ai déjà une famille exceptionnelle (qui n'existe que pour n=4), et puis d'autres pour n=6, 7 ou 8, et puis après ça redevient régulier, j'en suis sûr pour des raisons physico-géométriques, mais je n'ai pas de preuve...
Et en plus j'avais des contraintes, style pas de chaîne du type B-N-N-N-B (B blanc, N noir), et d'autres joyeusetés.

Bon courage, et appel os'cours à qui que ce soit de compétent!

-- françois

[invitea121f130]

moi aussi il me faut un chiffre exacte en faite j'ai besoin de cela pour ellabore un algorithme qui poure trouve le plus
long chemin elemantaire dans un graphe
ci qui est je te le cache pas un probleme np complet

[invite986312212]

essaie de te procurer l'article de Polya qui s'intitule quelque-chose comme "enumeration of graphs and chemical compounds". Il a été publié récemment en Anglais chez Springer. Ca traite un problème un peu plus compliqué que le tien, i.e. le cas où des valeurs sont attachées aux sommets (par exemple le type d'atome dans une molécule) mais ça te donnera sûrement des idées pour traiter ton problème.