Théorie des graphes : Td3 theorie des graphes coloriage chemins
Télécharger PDFMathématiques pour l’Informatique 2
http://www.lri.fr/~blsk/MI2
TD3 - Théorie des graphes, coloriage, chemins
Exercice 1Clique
Un clique est un graphe dont tous les sommets différents sont reliés par une seule arête. On noteKn la clique
qui ansommets.
— Dessiner les graphesK2 ,K3 ,K4 etK5 .
— Combien y a-t-il d’arêtes dansKn ?
— Combien de couleurs sont-elles nécessaires pour colorierKn ?
— Montrer que le grapheK4 est planaire (il peut être dessiné sans que les arêtes ne se croisent).
— A votre avis, le grapheK5 est-il planaire ?
Exercice 2Coloration
On se donne un ensembleEd’étudiants et un ensembleCde cours ainsi qu’une relationXtelle queX(e, c)
est vrai si et seulement si l’étudiantedoit passer l’examen du coursc.
Chaque épreuve se déroule sur une demi-journée. Le responsable de cours se demande quel nombre minimum
de demi-journées il doit réserver pour les examens afin que chaque étudiant puisse passer tous les examens auquel
il est inscrit sans conflit d’emploi du temps.
1. Montrer que ce problème se ramène à un problème de coloriage de graphe. On explicitera l’ensemble des
sommets, l’ensemble des arêtes et la signification du coloriage.
2. On suppose qu’il y a deux étudiantse1 , e2 et quatre coursc1 , c2 , c3 , c4 avec les contraintes suivantes :X(e 1
, c1 ), X(e1 , c2 ), X(e1 , c3 ), X(e2 , c3 ), X(e2 , c4 ), construire le graphe associé et déterminer le nombre
de demi-journées d’examens nécessaires.
3. On suppose qu’il y a 5 étudiants et 5 cours, que chaque cours est suivi par au moins un étudiant et que
chaque étudiant suit exactement 2 cours, trouver une configuration dans laquelle trois demi-journées sont
nécessaires.
Exercice 3Coloriage d’arêtes
On cherche à planifier les matchs d’un tournoi auquel participentnjoueurs. On construit un graphe dont
les sommets sont les joueurs, chaque match est représenté par une arête entre les deux joueurs qu’il oppose.
— Planifier les matchs dans le temps se ramène à associer une couleur à chaque arête. Exprimer quelle
condition doit vérifier ce coloriage pour que les matchs puissent se jouer sans conflit.
— Donnez une borne inférieure sur le nombre de couleurs nécessaires en fonction des caractéristiques dugraphe. — On se place maintenant dans le cas où chaque joueur doit rencontrer chaque autre joueur exactement
une fois.
— Reconnaissez-vous le graphe correspondant ? Combien a-t-il d’arêtes ?
— Quel est le nombre maximal de matchs qui peuvent avoir lieu en même temps ?
— Proposez un coloriage qui convient pourn= 4etn= 5.
Exercice 4Composantes connexes
La composante connexe d’un sommetadans un graphe non orientéGest définie comme l’ensemble des
pointsbtels qu’il existe un chemin (éventuellement vide) deaàb. Elle est notéeCCG (a).
1. Montrer que l’ensemble des composantes connexes forme une partition de l’ensemble des sommets :
— chaque composante est non vide
— tout sommet appartient à une composante
— deux composantes sont soit disjointes, soit égales
2. Quel est le nombre maximal de composantes connexes dans un graphe en fonction du nombre de sommets,
le nombre minimal ?
3. On suppose que le grapheGakcomposantes connexes. Soient deux sommetsaetbdeGet le grapheG′ qui est le même queGavec une arête de plus qui a pour extrémités{a, b}. Montrer que soitG′ contient
un cycle, soitG′ ak−1composantes connexes.
4. En déduire que si un graphe ansommets et ne contient pas de cycle alors il a au plusn−1arêtes.