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

théorie des graphes, énigme



  1. #1
    christophe_de_Berlin

    théorie des graphes, énigme


    ------

    Bonjour, j´ai un problème de théorie des graphes, et franchement je sais pas du tout par où commencer. Cet exo est sous forme d´une énigme, à priori assez sympatique, mais je ne sais pas comment la modéliser grâce aux graphes:

    Un groupe de sept amis décide que chacun d´eux enverra un paquet à trois autres. Est-il possible que les paquets que chacun reçoit viennent exactement de ceux à qui il en a envoyé?

    Par où commencer? À priori je ne vois même pas de rapport avec les graphes...

    -----

  2. #2
    rhomuald

    Re : théorie des graphes, énigme

    Citation Envoyé par christophe_de_Berlin Voir le message
    Bonjour, j´ai un problème de théorie des graphes, et franchement je sais pas du tout par où commencer. Cet exo est sous forme d´une énigme, à priori assez sympatique, mais je ne sais pas comment la modéliser grâce aux graphes:

    Un groupe de sept amis décide que chacun d´eux enverra un paquet à trois autres. Est-il possible que les paquets que chacun reçoit viennent exactement de ceux à qui il en a envoyé?

    Par où commencer? À priori je ne vois même pas de rapport avec les graphes...
    Salut, je pense que tu peux commencer par faire un dessin:

    tu fais septs points (sommets) qui sont tes personnages, chaque sommet est reliée à trois autres sommets par des arêtes (les transferts de paquets réciproques).

  3. #3
    christophe_de_Berlin

    Re : théorie des graphes, énigme

    merci, j´avais pensé à ça mais je me demande si on peut modéliser comme ça car un transfert de paquet a un sens, tandis qu´un arête d´un graphe n´en a pas. Mais je vais quand même essayer.

  4. #4
    christophe_de_Berlin

    Re : théorie des graphes, énigme

    Ah mais si t´as raison!! En fait la modélisation se fait par un graphe simple puisqu´on ne peut pas s´envoyer un paquet à soit-même, donc pas de boucle, et qu´on ne peut pas envoyer deux paquet au même ami.

    Donc la question semble être: existe-t-il un graphe simple de 7 sommet dont chaque sommet est de degré 3?

    C´est ça?

  5. A voir en vidéo sur Futura
  6. #5
    invite986312212
    Invité

    Re : théorie des graphes, énigme

    supprimé.....

  7. #6
    homotopie

    Re : théorie des graphes, énigme

    Citation Envoyé par christophe_de_Berlin Voir le message
    Donc la question semble être: existe-t-il un graphe simple de 7 sommet dont chaque sommet est de degré 3?
    Oui si ce graphe existe alors en associant un ami à chaque sommet, la distribution des paquets se fait selon la règle : "j'envoie aux amis aux sommets liés au mien". Il y a bien réciprocité.
    L'autre sens tu l'as déjà fait : on prend pour sommet chacun des amis et on les lie selon l'envoi des paquets, il n'y a bien que trois arêtes partant de chaque sommet.
    Ensuite ce n'est plus qu'un simple calcul de correspondance entrre sommets et arêtes pour montrer que ce n'est pas possible.

  8. #7
    christophe_de_Berlin

    Re : théorie des graphes, énigme

    Citation Envoyé par ambrosio Voir le message
    supprimé.....
    ?? Euh... ton message est succint.

  9. #8
    christophe_de_Berlin

    Re : théorie des graphes, énigme

    Intuitivement j´aurais tendance à dire que la propriété demandée est possible ssi le graphe est fait de 4-cliques: en effet une 4-clique est constituée de 4 sommets tous voisins entre eux, donc chaque sommet est voisin de 3 autres.

    Dans ce cas la réponse est non car pour qu´un graphe soit constitué de 4-cliques, il faudrait que son ordre soit un multiple de 4.

  10. #9
    invite986312212
    Invité

    Re : théorie des graphes, énigme

    tu peux raisonner sur la somme des degrés.

  11. #10
    christophe_de_Berlin

    Re : théorie des graphes, énigme

    Citation Envoyé par ambrosio Voir le message
    tu peux raisonner sur la somme des degrés.
    J´ai trouvé un théorème comme quoi dans un multigraphe le nombre de sommets de degré impair est pair.

    Je devrais pouvoir utiliser ce théorème non? puisqu´un graphe simple est aussi un multigraphe. Donc je ne peux pas avoir un graphe simple possédant 7 sommets de degré 3.

    Ayé?

  12. #11
    invite986312212
    Invité

    Re : théorie des graphes, énigme

    un graphe et composé d'un nombre entier d'arêtes et chaque arête a deux extrémités et chaque extrémité compte pour +1 dans la somme des degrés, qui est donc paire. Ici, tu devrais avoir 7*3 et c'est impair.

  13. #12
    homotopie

    Re : théorie des graphes, énigme

    Ou en plus simple :
    à chaque arête est associé deux sommets
    à chaque sommet est associé trois arêtes
    donc nombre d'arêtes =3x7/2 ce qui pose un problème.

  14. #13
    christophe_de_Berlin

    Re : théorie des graphes, énigme

    ben voilà, merci

Discussions similaires

  1. Théorie des graphes
    Par NAGHAM dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 01/01/2008, 13h18
  2. Théorie des graphes
    Par -Zweig- dans le forum Lectures scientifiques
    Réponses: 4
    Dernier message: 21/12/2007, 11h05
  3. Theorie des graphes
    Par BioBen dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 29/11/2007, 18h25
  4. Théorie des graphes et graphes de liaisons
    Par Eogan dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 08/12/2006, 22h59
  5. Théorie des graphes: un seul chemin
    Par Brumaire dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 11/12/2004, 00h36