Université Sultan Moulay Slimane Année universitaire 2023/2024
Faculté des Sciences et Techniques Enseignant : Dr. Lekbir Afraites
Département Informatique Matière : R.O
TD-1
Exercice 1
Trois professeurs P1, P2, P3 devront donner lundi prochain un certain nombre d’heures de cours à trois classes
C1, C2, C3 :
P1 doit donner 2 heures de cours à C1 et 1 heure à C2 ;
P2 doit donner 1 heure de cours à C1, 1 heure à C2 et 1 heure à C3 ;
P3 doit donner 1 heure de cours à C1, 1 heure à C2 et 2 heures à C3.
1. Comment représenter cette situation par un graphe ? Quel type de graphe obtenez-vous ?
2. Combien faudra-t-il de plages horaires au minimum ?
3. Aidez-vous du graphe pour proposer un horaire du lundi pour ces professeurs.
Exercice 2
On souhaite organiser un tournoi de handball entre 7 équipes. Pour des raisons d’organisation, on doit
limiter le nombre de matchs.
1. Est-il possible de faire jouer à chaque équipe exactement 5 matchs ?
2. Est-il possible de faire jouer à chaque équipe exactement 4 matchs ?
Exercice 3
Un tournoi de football intercommunal réunit plusieurs équipes. Chaque équipe rencontre toutes les
autres, soit à domicile, soit à l’extérieur. Le stade de la commune A étant inondé, l’équipe A ne jouera
aucun match à domicile. On voudrait que les autres équipes jouent chacune autant de matchs à
domicile.
1. Est-ce possible si le tournoi réunit 7 équipes ?
2. Est-ce possible si le tournoi réunit 6 équipes ?
Exercice 4
Un parcours de santé est aménagé pour les sportifs au parc des Prébendes en centre ville de Tours. Il
est composé de chemins à sens unique et de quatre points de repères tous distants de 500 mètres.
1
1. Exprimer la matrice d'adjacence de ce graphe.
2. Combien de chemins différents de 1,5 kilomètre peut-on effectuer de A vers D ? Les
déterminer.
3. Même question avec des chemins de 2 kilomètres.
Exercice 5
Un réseau informatique est constitué de 7 ordinateurs O1, O2, ⋯, O7 et d’une imprimante I, reliés
par des câbles.
1. Si l'on retire le câble entre O4 et I peut-on accéder à l’imprimante à partir de n’importe quel
ordinateur ?
2. Même question avec le câble entre O7 et I.
