Théorie des graphes : Td3 theorie des graphes coloriage chemins
Télécharger PDFMathématiques pour l’Informatique 2 – Théorie des graphes, coloriage et chemins
Exercice 1 : Clique
Un clique est un graphe dont tous les sommets différents sont reliés par une seule arête. On note Kn la clique qui a n sommets.
— Dessiner les graphes K2, K3, K4 et K5.
— Combien y a-t-il d’arêtes dans Kn ?
— Combien de couleurs sont nécessaires pour colorier Kn ?
— Montrer que le graphe K4 est planaire (il peut être dessiné sans que les arêtes ne se croisent).
— À votre avis, le graphe K5 est-il planaire ?
Exercice 2 : Coloration
On se donne un ensemble E d’étudiants et un ensemble C de cours, ainsi qu’une relation X telle que X(e, c) est vrai si et seulement si l’étudiant e doit passer l’examen du cours c.
Chaque épreuve se déroule sur une demi-journée. Le responsable de cours cherche à déterminer le nombre minimum de demi-journées nécessaires pour organiser les examens afin que chaque étudiant puisse passer tous ceux auxquels il est inscrit sans conflit d’horaire.
1. Montrer que ce problème peut être modélisé comme un problème de coloriage de graphe. Définir : - L’ensemble des sommets - L’ensemble des arêtes - La signification du coloriage
2. Avec deux étudiants e1, e2 et quatre cours c1, c2, c3, c4, et les contraintes suivantes : X(e1, 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. Avec cinq étudiants et cinq cours, chaque cours suivi par au moins un étudiant et chaque étudiant inscrit à exactement deux cours, trouver une configuration où trois demi-journées sont nécessaires.
Exercice 3 : Coloriage d’arêtes
On cherche à planifier les matchs d’un tournoi avec n joueurs. On construit un graphe dont les sommets sont les joueurs, et chaque match est représenté par une arête reliant les deux joueurs concernés.
1. Planifier les matchs dans le temps revient à attribuer une couleur à chaque arête. La condition pour que les matchs se déroulent sans conflit est que deux arêtes reliées à un même sommet n’aient pas la même couleur.
2. Donner une borne inférieure sur le nombre de couleurs nécessaires en fonction du degré maximal du graphe.
3. Dans le cas où chaque joueur affronte chaque autre joueur exactement une fois : - Reconnaître le graphe correspondant (complet ? autre ?) - Combien a-t-il d’arêtes ? - Quel est le nombre maximal de matchs pouvant avoir lieu simultanément ? - Proposer un coloriage adapté pour n = 4 et n = 5.
Exercice 4 : Composantes connexes
La composante connexe d’un sommet a dans un graphe non orienté G est définie comme l’ensemble des points b tels qu’il existe un chemin (éventuellement vide) de a à b. On la note CCG(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 ? Et le nombre minimal ?
3. Si le graphe G a k composantes connexes et qu’on ajoute une arête entre deux sommets a et b de G pour former G', montrer que : - Soit G' contient un cycle - Soit G' a k − 1 composantes connexes
4. En déduire que si un graphe a n sommets et ne contient aucun cycle, alors il a au plus n − 1 arêtes.
FAQ sur la théorie des graphes
1. Qu’est-ce qu’un graphe planaire ?
Un graphe planaire est un graphe qui peut être dessiné sur un plan sans que ses arêtes ne se croisent. Par exemple, K4 est planaire, mais K5 ne l’est pas.
2. Comment déterminer le nombre minimal de couleurs pour un graphe ?
Le nombre minimal de couleurs nécessaires pour colorier un graphe est appelé le nombre chromatique. Pour un graphe complet Kn, il est égal à n car chaque sommet doit avoir une couleur différente.
3. Pourquoi le coloriage d’arêtes est-il utile pour planifier des matchs ?
Le coloriage d’arêtes permet d’assigner des créneaux horaires distincts aux matchs impliquant un même joueur. Chaque couleur représente un créneau sans conflit.