Théorie des graphes : Graphes et modelisation exercices corriges
Télécharger PDFTD n°2 – Théorie des Graphes
Exercice 1
On considère le sous-ensemble S des pays d’Europe suivants :
1. Autriche (A)
2. Benelux (B)
3. Suisse (Ch)
4. Allemagne (D)
5. Espagne (E)
6. France (F)
7. Grèce (G)
8. Italie (I)
9. Portugal (P)
10. Grande-Bretagne (Uk)
Soient P1 et P2 deux pays de S, on définit la relation ÷ par :
P1 ÷ P2 ⇐⇒ ≪on peut aller de P1 à P2 en traversant une seule frontière terrestre≫.
1. Cette relation était-elle réflexive, symétrique, antisymétrique, transitive ?
2. Est-il préférable de représenter ÷ par un graphe orienté ou simple ?
3. Représenter ce graphe. Quelle est son ordre et sa taille ? Quel est son nombre chromatique ?
4. Ce graphe est-il connexe ? Combien possède-t-il de composantes connexes ?
5. On note ⊲⊳ la relation associée à la fermeture transitive de ce graphe.
Exprimer par une phrase la plus simple possible la relation P1 ⊲⊳ P2.
6. Donner la matrice d’adjacence de ce graphe et de sa fermeture transitive.
Exercice 2 – Lemme des poignées de mains
1. Montrer que dans un graphe non orienté, la somme des degrés est un nombre pair.
2. Est-il possible de relier 5 ordinateurs de sorte que chaque appareil soit relié à exactement trois autres ?
3. Montrer que dans un graphe, le nombre de sommets de degré impair est pair.
4. Existe-t-il un graphe non orienté dont les sommets ont pour degré 1, 1, 2, 2, 3 ?
5. Montrer que dans un graphe d’ordre n et de taille m, où tous les sommets ont le même degré r (graphe régulier), on a m = 1/2 × n × r.
6. Soit G un graphe simple et non orienté avec 4 sommets tous de degré 2. Combien y a-t-il d’arêtes ? Représenter un tel graphe.
7. Soit G un graphe simple et non orienté avec 15 arêtes, 3 sommets de degré 4 et tous les autres sommets de degré 3. Quel est le nombre de sommets du graphe ? Représenter un tel graphe.
Indication : Une fois n connu, placer les sommets de degré 4 au centre et les sommets de degré 3 autour.
Exercice 3 – Graphe complet
Soit G = (S, A) un graphe complet d’ordre n.
1. Quelle est la taille m du graphe suivant que :
(a) G est un graphe orienté quelconque
(b) G est un graphe orienté et simple
(c) G est un graphe non orienté et simple
(d) G est un graphe non orienté quelconque
Indication : Raisonner à partir de la matrice d’adjacence du graphe ou utiliser le lemme des poignées de mains.
2. Dans un tournoi de football, le premier tour est organisé sous forme de « poule » de 4 équipes où chaque équipe doit rencontrer toutes les autres.
(a) Représenter la situation par un graphe. Combien de matchs joue chaque équipe ? Combien de matchs y a-t-il en tout ?
(b) Que deviennent ces résultats avec des poules de 5 équipes ?
(c) Dans une des poules, les cinq équipes ont gagné respectivement 3, 2, 2, 1, 1 matchs. Combien y a-t-il eu de match(s) nul(s) ?
(d) Le nombre de matchs étant trop important, les organisateurs décident de faire jouer seulement 3 matchs à chaque équipe. Comment l’organiser ?
Exercice 4 – Coloriage de graphes
Durant la soirée, sept étudiants A, B, C, D, E, F, G se sont rendus travailler dans la salle de TP « libre-service ». Le tableau suivant précise « qui a rencontré qui » :
Élève A B C D E F G
À rencontré D, E D, E, F G, E A, B, E A, B, C, D, F G, B E, G, B C, E, F
1. Représenter les données de ce tableau par un graphe G dont les sommets sont les étudiants. Préciser la nature du graphe (simple ou pas ? orienté ou pas ?) et justifier votre choix.
2. Donner un coloriage de G.
3. Justifier si ce coloriage est optimal et en déduire le nombre chromatique γ(G).
Indication : On pourra utiliser la plus grande clique de G.
4. Combien faut-il de PC dans la salle de TP pour que tous les étudiants aient pu travailler seul sur une machine ?
5. On sait qu’il y a eu constamment au moins 2 machines libres dans la salle. Combien la salle a-t-elle de machines ?
Exercice 5 – Mr et Mme X assistent à une réunion
Mr et Mme X assistent à une réunion. Il y a trois autres couples dans l’assistance et plusieurs poignées de mains sont échangées. Personne ne serre sa propre main et les époux ne se serrent pas la main. Deux personnes quelconques de l’assemblée se serrent la main au plus une fois.
Mr X constate que les 7 autres personnes ont échangé des poignées de mains en nombres tous distincts.
1. Quelles sont les valeurs possibles pour le nombre de poignées de mains serrées par chaque personne ? Que peut-on en déduire pour Mr X ?
2. Représenter la situation par un graphe et préciser le type de graphe.
Indication : Positionner les 8 sommets du graphe en 4 groupes de 2 et tracer les arêtes en commençant par le sommet de plus haut degré.
3. Combien de poignées de mains Mr et Mme X ont-ils échangées avec les autres membres de la réunion ?
Exercice 6 – Craquage de digicode
L’accès d’un bâtiment est contrôlé par un digicode dont la combinaison est formée d’une suite de 3 lettres X1 X2 X3 ne pouvant prendre que 2 valeurs Xi = A ou B. Pour entrer, sans connaître le code, il faut normalement tenter chacune des combinaisons possibles (AAA, AAB, ..., BBA).
En réalité, lorsqu’on saisit une chaîne de p lettres X1 X2 X3 ... Xp, le digicode teste successivement les sous-chaînes X1 X2 X3, X2 X3 X4, ..., Xp-2 Xp-1 Xp.
Pour trouver la chaîne la plus courte possible permettant d’entrer dans le bâtiment sans connaître le code, on représente le problème par un graphe orienté G dont :
• les sommets représentent les différentes combinaisons X1 X2 X3
• les arcs joignent des combinaisons obtenues successivement par ajout d’une lettre à la fin de la combinaison précédente.
1. Quel est l’ordre du graphe (c’est-à-dire le nombre de combinaisons possibles) ? Combien de lettres faut-il saisir pour essayer toutes ces combinaisons une à une ?
2. Quels sont les degrés entrant et sortant de chaque sommet ? En déduire la taille du graphe G (c’est-à-dire le nombre d’arcs) à l’aide du lemme des poignées de mains.
3. Représenter le graphe G du problème de telle sorte qu’il soit planaire.
4. À quel type de chemin du graphe G correspond la solution du problème ? Trouver la solution à partir du graphe (sous forme d’une chaîne de caractères composée de A et de B) et préciser la longueur de la chaîne trouvée.
FAQ
1. Qu’est-ce qu’un graphe régulier ?
Un graphe régulier est un graphe où tous les sommets ont le même degré.
2. Comment déterminer le nombre chromatique d’un graphe ?
Le nombre chromatique est le plus petit nombre de couleurs nécessaires pour colorier les sommets d’un graphe de sorte que deux sommets adjacents n’aient pas la même couleur. Il peut être déterminé en trouvant la plus grande clique du graphe.
3. À quoi sert le lemme des poignées de mains ?
Le lemme des poignées de mains permet de montrer que la somme des degrés des sommets d’un graphe non orienté est toujours un nombre pair et que le nombre de sommets de degré impair est également pair.