TD 1 - Graphes [PDF]

Zitiervorschau

ESSECT

Théorie des graphes et optimisation

AU : 2020-2021

Travaux Dirigés 1 Exercice 1 Un tournoi d’échecs oppose 6 personnes. Chaque joueur doit affronter tous les autres. 1. Construisez un graphe représentant toutes les parties possibles. 2. Quel type de graphe obtenez-vous ? 3. Si chaque joueur ne joue qu’un match par jour, combien de jours faudra-t-il pour terminer le tournoi ? 4. Aidez-vous du graphe pour proposer un calendrier des matches.

Exercice 2 Est-il possible de relier 15 ordinateurs de sorte que chaque appareil soit relié avec exactement trois autres ?

Exercice 3 Montrez que ce graphe est biparti :

Exercice 4 Montrez que dans un groupe de personnes, il y a toujours deux personnes ayant le même nombre d’amis présents.

Exercice 5 Huit jeunes hommes veulent travailler dans un supermarché dans lequel trois postes sont disponibles. Le responsable, soucieux d'éviter les problèmes, veut tenir compte des inimitiés entre ces jeunes hommes : Adrien ne peut supporter Damien; Benjamin ne parle plus à Adrien; Cyril refuse de travailler avec Benjamin;

ESSECT

Théorie des graphes et optimisation

AU : 2020-2021

Damien ne supporte pas Greg; Eric ne veut cotoyer ni Benjamin, ni Frank, ni Hector; Frank n'apprécie pas Greg et Hector; Greg ne s'entend pas avec Adrien; Hector refuse de travailler avec Frank ou Cyril. 1. Construire un graphe non-orienté traduisant cette situation d'incompatibilité d'humeur. 2. Eric a le meilleur CV. Qui peut-on embaucher avec lui? 3. Donner une autre combinaison possible de trois jeunes, autres qu'Eric, que l'on peut embaucher.

Exercice 6 Le conseil municipal d'une ville comprend 7 commissions, qui obéissent aux règles Suivantes: Règle 1 : tout conseiller municipal fait partie de 2 commissions exactement. Règle 2 : deux commissions quelconques ont exactement un conseiller en commun 1. Modéliser le problème à l’aide d’un graphe (préciser les sommets et les liaisons) 2. Combien y a-t-il de membres dans le conseil municipal ? 3. En déduire le nombre de membre de chaque commission.