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

nombre de cycle hamiltonien



  1. #1
    an1982

    nombre de cycle hamiltonien


    ------

    Bjr, est ce que quelqu'un peut m'aider pour repondre à cette question !
    Combien de cycles hamiltoniens possède le graphe Kn?
    merci

    -----

  2. #2
    invite986312212
    Invité

    Re : nombre de cycle hamiltonien

    ça doit être (n-1)! puisque chaque ordonnancement des n sommets correspond à un cycle hamiltonien unique au choix du point de départ près.

  3. #3
    Amanuensis

    Re : nombre de cycle hamiltonien

    Extrait du Wiki anglophone, consulté pour avoir le sens précis de l'expression "cycle hamiltonien" :

    Number of different Hamiltonian cycles for a complete graph = (n-1)! / 2.
    La direction de parcours ne distingue pas deux cycles...

  4. #4
    Amanuensis

    Re : nombre de cycle hamiltonien

    Je précise, puisque la question ne le fait pas totalement (au cas où Kn serait employée aussi pour un graphe orienté), que la réponse que j'ai donnée est pour un graphe non-orienté.

Sur le même thème :

Discussions similaires

  1. Lagrangien et Hamiltonien
    Par ordage dans le forum Physique
    Réponses: 5
    Dernier message: 09/05/2010, 19h48
  2. [Génétique] Nombre de molecules d' ADN en fonctions de la phase du cycle cellulaire
    Par melancia dans le forum Biologie
    Réponses: 10
    Dernier message: 15/10/2009, 14h40
  3. Hamiltonien en Phi4
    Par alovesupreme dans le forum Physique
    Réponses: 4
    Dernier message: 09/01/2009, 22h27
  4. Hamiltonien
    Par rouviv dans le forum Chimie
    Réponses: 4
    Dernier message: 10/05/2007, 21h49
  5. Le Hamiltonien me turlupine
    Par mikeuline dans le forum Physique
    Réponses: 12
    Dernier message: 05/07/2005, 09h52