Répondre à la discussion
Affichage des résultats 1 à 11 sur 11

graph



  1. #1
    sahdow

    graph


    ------

    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)

    -----

  2. Publicité
  3. #2
    rvz

    Re : graph

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

    __
    rvz

  4. #3
    sahdow

    Re : graph

    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

  5. #4
    sahdow

    Re : graph

    hello je pourais avoir une reponse svp

  6. A voir en vidéo sur Futura
  7. #5
    isozv

    Re : graph

    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

  8. #6
    sahdow

    Re : graph

    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

  9. Publicité
  10. #7
    fderwelt

    Re : graph

    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
    Les optimistes croient que ce monde est le meilleur possible. Les pessimistes savent que c'est vrai.

  11. #8
    sahdow

    Re : graph

    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

  12. #9
    fderwelt

    Re : graph

    Citation Envoyé par sahdow
    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
    Les optimistes croient que ce monde est le meilleur possible. Les pessimistes savent que c'est vrai.

  13. #10
    sahdow

    Re : graph

    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

  14. #11
    invite986312212
    Invité

    Re : graph

    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.

Discussions similaires

  1. Utilisation de la casio GRAPH 65
    Par LicenceXP dans le forum Électronique
    Réponses: 7
    Dernier message: 06/11/2013, 21h01
  2. visualisation d'un graph
    Par sahdow dans le forum Logiciel - Software - Open Source
    Réponses: 1
    Dernier message: 15/11/2007, 13h30
  3. Graph de phase de l'ethanol
    Par nico_de_pablo dans le forum Chimie
    Réponses: 13
    Dernier message: 15/08/2007, 11h41
  4. Casio Graph 35+ !
    Par Miouz dans le forum Mathématiques du collège et du lycée
    Réponses: 3
    Dernier message: 11/02/2007, 19h55
  5. Un graph en forme de... hyperbole ?
    Par NorbO dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 13/01/2006, 10h40