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

Nombres de Ramsey



  1. #1
    aNyFuTuRe-

    Nombres de Ramsey


    ------

    Salut à tous,

    J'aimerai en savoir un plus sur la relation entre nombres de Ramsey et théorie des graphes? Quelqu'un aurait-il l'amabilité de m'expliqué simplement le rapport : comment ca marche quoi en gros

    J'aimerai traité des question du types : " Soit E un groupe formé d'un nombre impair de personnes. Montrer qu'il existe au moins un personne dont le nombre de connaissance est pair".

    Au premier abord ça peut paraître évident (?) mais a montrer c'est dur...
    Il faut compter de deux manières différentes le nombre de couples (x,y) de personne où x connaît y.


    Merci d'avance

    -----
    « la sensation varie comme le logarithme de l'excitation ». loi de Weber-Fechner

  2. #2
    Médiat

    Re : Nombres de Ramsey

    Citation Envoyé par aNyFuTuRe- Voir le message
    Au premier abord ça peut paraître évident (?) mais a montrer c'est dur...
    Cette partie est effectivement facile, en langage des graphes : si tu comptes les arêtes du graphe qui partent de chaque sommet et que tu les ajoutes, tu obtiens une somme d'un nombre impair de nombres impairs, le résultat est donc impair, sauf que tu as ainsi compté chaque arête 2 fois (une fois pour chacun des sommets) le résultat devrait donc être pair...
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  3. #3
    aNyFuTuRe-

    Re : Nombres de Ramsey

    Merci pour votre réponse mais pourriez vous m'en dire plus sur le lien entre nombre de Ramsey et théorie des graphes?
    « la sensation varie comme le logarithme de l'excitation ». loi de Weber-Fechner

  4. #4
    Médiat

    Re : Nombres de Ramsey

    Citation Envoyé par aNyFuTuRe- Voir le message
    Merci pour votre réponse mais pourriez vous m'en dire plus sur le lien entre nombre de Ramsey et théorie des graphes?
    Les nombre de Ramsey que je connais sont liés à la bicoloration des graphes, c'est donc bien une partie de la théorie des graphes...
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  5. A voir en vidéo sur Futura
  6. #5
    aNyFuTuRe-

    Re : Nombres de Ramsey

    Pourriez vous m'expliciter ce lien entre nombre de Ramsey et bicoloration des graphes?

    Par exemple, si l'on considère un graphe a 6 sommets (donc 6 personnes) de quelle manière montre t-on que l'on peut trouver soit 3 personnes qui se connaissent deux a deux soit 3 qui ne se connaissent pas ? (c'est le problème de base pour illustrer les nombres de Ramsey que j'ai résolu avec une autre méthode que celle qui utilise les graphes )

    Dernière question: la présence de triangles dans les graphes est est-elle nécessaire dans ce genre de problème ?

    Merci de m'éclairer
    « la sensation varie comme le logarithme de l'excitation ». loi de Weber-Fechner

Discussions similaires

  1. Nombres premiers, y aurait-il des nombres premiers jumeaux
    Par RSSBot dans le forum Commentez les actus, dossiers et définitions
    Réponses: 2
    Dernier message: 19/04/2007, 08h45
  2. nombres complexes
    Par kate29 dans le forum Mathématiques du collège et du lycée
    Réponses: 2
    Dernier message: 15/02/2007, 11h48
  3. Nombres complexes
    Par yuna60 dans le forum Mathématiques du collège et du lycée
    Réponses: 7
    Dernier message: 29/01/2007, 17h50
  4. Nombres complexes
    Par luca dans le forum Mathématiques du supérieur
    Réponses: 71
    Dernier message: 07/01/2006, 12h30