Bonjour à tous, voici un exercice que j'ai eu en spé maths. Aucun de mes camarades n'a encore réussi a résoudre, on a tout essayé. Toute aide est bienvenue!
Quatres professeurs X,Y,Z et T doivent donner des cours à quatres classes notées 1,2,3 et 4
X Doit donner une heure à 1 et une heure à 4
Y Doit donner une heure à 1, une heure à 2 et une heure à 4
Z Doit donner une heure à 1, une heure à 2 et une heure à 3
T Doit donner une heure à 1, une heure à 3 et une heure à 4
1. Trouver, d'après l'énoncé, le nombre minimum d'heures qu'il faut pour enseigner tous les cours
2. Modéliser la situation par un graphe biparti
3. Déterminer, par une coloration des arêtes, l'horaire inimum nécessaire pour enseigner tous les cours.
Proposer deux plannings correspondants à cet horaire minimal.
Merci d'avance
Salut,
Pour la 1 :
Il est clair qu'il faut au moins 4 heures, car 1 doit recevoir une heure de chaque prof.
Dans un tableau 5 lignes 5 colonnes,
Première ligne : 1ère case vide , puis 1 , 2 , 3 et 4 (ce sont les classes).
Première colonne : 1ère case vide , puis a , b , c et d (ce sont les heures).
On peut placer X,Y,Z et T sous le "1" : ainsi la classe 1 a ses 4 heures de cours.
Puis on complète le tableau de façon à ce que tout rentre (il y a plusieurs possibilités).
Par exemple, on peut obtenir :
heure a : X(1) ; Y(2) ; Z(3) ; T(4)
heure b : Y(1) ; Z(2) ; T(4)
heure c : Z(1) ; T(3) ; Y(4)
heure d : T(1).
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :