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:Envoyé par christophe_de_Berlin
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...
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).
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.
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?
supprimé.....
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.
?? Euh... ton message est succint.
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.
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é?
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.
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.
ben voilà, merci
