Inscription / Connexion Nouveau Sujet
posté de travail avec contraintes (spécialité:graphe)
Bonjour
Je voudrais de l aide sur cette exercice car j arrive même avec à le commencer
Voilà l'énoncé:
Huit jeunes hommes veulent travailler dans un hypermarché.le responsable n'a que trois postes à pourvoir.
Il désire tenir compte des problèmes entre eux:
Adrien ne peut supporter Damien et Cyril:
Benjamin et Franck ne veulent pas travailler ensemble :
Cyril refuse de travailler avec Benjamin ;
Damien ne travaille pas avec Greg ;
Erik ne veut travailler ni avec Benjamin ni avec Franck ni avec Hector ;
Franck ne veut pas travailler avec Greg ou avec Hector;
Greg ne s'entend pas avec Adrien;
Hector refuse de travailler avec Franck ou avec cyril.
1) construire un graphe traduisant cette situation d'incompatibilité d'humeur .
Faut-il orienter ce graphe ou non?
2) si le responsable veut embaucher Erik quels sont les deux autres personnes qu'il peut embaucher?
Donner un combinaison possible de trois jeunes,autres qu'Erik, qui peuvent avoir trois emplois.
Bonjour,
Non, inutile d'orienter le graphe.
Trace un graphe à 8 sommets A,B,C,D,E,F,G,H (comme les premières lettre des personnes), et à chaque fois qu'il y a une incompatibilité (quelle qu'elle soit) entre deux personnes, relie leurs sommets par une arête.
Ensuite place-toi au sommet E et observe.
Donc la question 2
Si le responsable veut embaucher Erik il peut embaucher aussi Hector et Franck.
Juste?
Ben non :
Erik ne veut travailler ni avec Benjamin ni avec Franck ni avec Hector
Non :
Adrien ne peut supporter Damien et Cyril
Plutôt : Dans ton graphe A et D doivent être reliés par une arête car incompatibilité. Donc impossible qu'ils travaillent ensemble.
Relis mon post de 19:28.
Oui. C'est sa
il y a 3 arêtes en A
A-C A-D A-G
B 3 aretes
B-C B-E B-F
C 3 arêtes
C-B C-A C-G
D 2 arêtes
D-A D-G
E 3 arêtes
E-B E-H E-F
F 4 arêtes
F-B F-E F-H F-G
G 3 arêtes
G-D G-F G-A
H 3 arêtes
H-F H-C H-E
Voilà mon graphe
Attendez je crois que j'ai compris
Si le responsable embauche Erik il peut embaucher Cyril et Adrien
Deuxième combinaison S'il embauche Greg il peut embaucher Adrien Et Benjamin
Mais non :
- s'il embauche Erik, il ne peut pas embaucher en même temps Cyril et Adrien puisque
Adrien ne peut supporter Damien et Cyril
- et s'il embauche Greg il ne peut embaucher Arien et Benjamin puisque
Greg ne s'entend pas avec Adrien
1) Dans ton graphe, tu dois chercher deux sommets dont aucun n'est relié directement par une arête à Erik, et non reliés ensemble directement par une arête.
Regarde bien : repère les sommets non reliés directement à Erik, puis parmi eux cherche ceux qui ne sont pas reliés par une arête.
2) Essaie de repérer un autre trio possible.
Décidément... Heureusement que je l'avais fait à la main sur une feuille avant. "Le mieux est (parfois) l'ennemi du bien".
La dernière question est
Donner un combinaison possible de trois jeunes,autres qu'Erik, qui peuvent avoir trois emplois.
Annuler
connectez vous