Inscription / Connexion Nouveau Sujet
Exercice graphe
Bonjour, j'ai un exercice à faire, mais je suis bloquer sur une partie d'une question.
Voici, l'énnoncé : " Un certain nombre de produits ne peuvent pas être transportés dans le même camion. Une croix dans une case du tableau (ci-dessous) indique une incompatibilité de transport pour deux produits. "
Les deux premières questions qui m'étaient posées étaient de construire le graphe d'incompatibilités de transport pour deux produits et de colorier ce graphe.
J'ai donc construit ce graphe et colorier ce graphe ( ci dessous dans un autre message ) à l'aide de l'algorithme de Welch-Powell
La troisième question qui m'est posée est la suivante : " En étudiant les sous graphes complets, demontrer que 4 couleurs sont nécessaires et suffisent "
Tout d'abord, Je ne sais pas comment étudier les sous graphes complets, car je ne sais pas quels sous-graphes je dois choisir. quels sommets dois-je prendre pour quel sous graphe complet?
Ensuite, pour la seconde partie de la question je pense qu'il faut utilisé la propriété suivante " Si m est l'ordre le plus grand des sous graphes complets d'un graphe, alors le nombre chromatique de ce graphe est supérieur ou égal à m. "
Mais je n'arrive pas à l'appliquer car il me manque les sous graphes complets à trouver, :s
Merci d'avance,
Sophie
Voici des sous graphes complets que j'ai trouver :
G H A B G
F A D F
E H A B C E
Mais, je ne suis pas sur de moi, :s et je n'arrive pas à trouver la deuxieme partie de la réponse :S
Hello Filicine,
es-tu sûre que C peut être colorié en rouge ?
GHABG n'est pas un sous-graphe complet H et B ne sont pas adjacents. EHABCE non plus car A et E ne sont pas adjacents.
Pour qu'un sous-graphe soit complet il faut que tous ses sommets pris deux à deux soient adjacents, c'est à dire reliés par une arête.
Comme par exemple FAD ( on ne répète pas un sommet comme tu l'as fait avec F ).
Effectivement, merci. Je viens de me rendres compte de mon erreur, j'ai donc refais le théorème, et j'ai colorié C en noir.
Pour les sous-graphes complets, je comprends mon erreur. Mais je ne comprends pas commment les trouvés :s
En tout cas il en un de quatre sommets et tous les autres de trois je te laisse chercher encore un peu.
Je crois avoir compris,
HADF pour celui a quatre sommets ?
Sinon, pour ceux a trois sommets : FAD
BCD
HAF?
Je n'en vois pas d'autre
Voilà je crois que tu les as tous trouvé.
Comme il y a en a de 4 sommets le nombre chromatique ne peut pas être inférieur à 4, or comme tu as trouvé 4 couleurs tu as une solution.
Ah d'accord, merci beaucoup 
,
Excusez moi, mais j'ai une dernière question qui me pose problème.
" Proposer une organisation du transport avec un nombre minimal de camions "
Je pensais que l'on pouvais utiliser les sous-graphes, mais non, car plusieurs lettres ont été répétés,
Mais sinon, peux on utilisé les couleurs ? Ce qui donnerais donc quatre camions ?
Avec le premier avec G E D
Le second avec H et B
Le troisième avec A et C
Eet le dernier, avec F ?
Annuler
connectez vous