Inscription / Connexion Nouveau Sujet
Graphes
Bonjour, j'ai cet exo de maths-spé sur les graphes à faire:
"Une grande-surface est concue de telle facon que six secteurs (alimentation, hi-fi..) notés A, B, C, D, E, F sont reliés par des allées selon le graphe G ci dessous
1) a) Quels sont les degrés de chaque sommet ?
b) le graphe G est-il connexe
2) Un visiteur désir parcourire l'ensemble des allées en ne passant par celles-ci qu'une seule fois
a) Cela est-il réalisable ?
b) Donner un exemple d'un tel parcours
3) Le directeur désire associer chaque secteur à une couleur de sorte que deux secteurs (sommets) ne portent pas la meme couleur
a) Démontrer que le nombre chromatique n du graphe vérifie 
n 4
b) Expliquez pourquoi n 
5
c) Proposer un coloriage du graphe permettant de déterminer son nombre chromatique
4) Une famille se tropuve dans le secteur E et doit se rendre dans le secteur F. Cela étant, les parents connaissent suffisamment les allées pour savoir que, pour chacune d'elles, les enfants ne résistants pas, il leur faudra débourser une somme (en euros) avec AB= 40, AC= 10, AD= 10, AE= 30, BC=20 , BF =20 , CD = 40 , CE = 40, DE = 10, DF = 70. Indiquer une chaine qui minimise la dépense de cette famille"
Alors, jusqu'à la question 4 tout va bien:
1)a) A = degré 4
B = degré 3
C = degré 4
D = degré 4
E = degré 3
F = degré 2
b) ce graphe est connexe car il existe une chaine entre 2 sommets quelconques du graphe.
2) a) On sait que le graphe a 2 sommets de degré impairs (B et E), il y a donc une chaine eulérienne, donc on peut passer une seule fois et une seule dans chaque allée du magasin
b) exemple: B A C E A D C B F D E
3)a) sommet de plus haut degré :A, C et D = degré 4
Donc le nombre chromatique du graphe n 4
b) Mais n 5 (4+1)
c) Après coloration, on trouve n = 4 = il faut 4 couleurs pour colorier le graphe
Mais je bloque à la question 4, où il faut utiliser l'algorithme de Dijkstra, moi, après avoir rempli le tableau, je fixe les sommets : E D A C B F et je trouve que la chaine la plus courte est : E A C B F (= 80 euros)
Qu'en pensez-vous. J'ai un doute pour la question 4
Merci de votre aide.
Bonjour,
Pour la 4) je trouve avec l'algo de Dijskstra la chaine EDACBF de longueur 70. Sauf erreur de ma part !
Pour la 3a) pour justifier que n4 je ne pennse pas que ton argument soit bon.
Le graphe contient un sous-graphe complet d'ordre 4 (c'est E,A,C,D) donc n4.
Merci à tous les deux. Littleguy, je ne comprends pas comment vous avez fait. Je trouve 80 à chaque fois, et à vrai dire Dijkstra est assez dur à appliquer...
jonjon71 ne semble plus connecté, aussi je réponds.
Tu as dû apprendre une présentation pratique sous forme de tableau.
Je pars de E ; parmi les sommets qui lui sont adjacents je sélectionne le plus "proche", en l'occurrence D (à une distance de 10)
Puis je fais la même chose pour les sommets adjacents à D (E exclu bien sûr). Je trouve A (distance 10). Je sélectionne donc A
Et on reconduit l'opération.
A la la fin j'arrive à F qui vient de B, lequel vient de C, lequel vient de A, ....
Et on reconstitue ainsi le chemin suivi et la distance totale.
En inscrivant les "distances" sur les arêtes et en observant les différents trajets pour aller de E à F, on pouvait trouver ce résultat rapidement sans avoir recours à l'algorithme. On trouve plusieurs chemins de poids 80 mais il y avait mieux.
Ok, j'ai compris, merci beaucoup. Donc le chemin le moins onéreux pour la famille est : E D A C B F (= 70 euros). Encore merci.
Annuler
connectez vous