Inscription / Connexion Nouveau Sujet
Graphes non orientés
bonjour, en voulant m'exercer pour comprendre les graphes, je suis tombé sur cette exercice, le probléme est que je bloque dans l'énoncé:
"On a 6 wagons à trier. Dans la gare de triage, les wagons entrent dans l'ordre 2, 5, 3, 6, 1, 4 et doivent sortir dans l'ordre croissant. Deux wagons i et j peuvent être mis sur la même voie si et seulement s'ils entrent dans l'ordre dans lequel ils doivent sortir.
Dessinez un graphe illustrant la situation, en indiquant ce que représentent les sommets et les arêtes de votre graphe.
Quel sera le nombre minimal de voies nécessaires au tri? "
-->Ce que je comprends, c'est que les wagons entre dans l'ordre 2,5, 3, 6, 1, 4 et doivent resortir dans l'ordre 1, 2, 3, 4, 5, 6 .
"Deux wagons i et j peuvent être mis sur la même voie si et seulement s'ils entrent dans l'ordre dans lequel ils doivent sortir."
--> c'est pas possible dans cette exemple, car aucun wagons i , j ne satisfait ce qui a été dit dans l'énoncé.
J'ai réaliser le graphe, est ce qu'il est bon ?
je ne crois pas que ton dessin d'aidera bcp:
voici l'idée: tu as 6 wagons qui entres en gare.
(les 6 sommets de ton graphe)
tu peux mettre des wagons sur une meme voix s'il se suivent.
i c'est possible tu relies ces sommets
dans ton cas tu peux mettre sur une premiere voix: 2 3 et 4
qui sotn dans l'ordre
sur une autre voix tu peu mettre 5 et 6 qui eux aussi sont dans le bon ordre
et enfin il te faut une troisieme voix pour mettre le wagon 1
ca s'appelle de la COLORATION de graphe (tu mets de meme couleurs les sommets qui correspondanet a des wagons qui peuvent aller sur une meme voix car dans le bon ordre) ici ton graphe se colorie entierement avec trois couleurs
defintiondu graphe:
1)les sommets sont les wagons
2) les aretes: tu relies 2 wagons i et (i+1) si et seulement si et seulement il arrivent dans le bon ordre à l'entrée dans la gare. (meme s'il y a d'autres wagons entre peu importe)
le nombre de sousgraphe ainsi obtenu te donne le nombre de voix necessaire, encore une fois c'a s'appelle de la coloration de graphe
Annuler
connectez vous
algèbre en Bts