Théorie des graphes : Graphes et modelisation exercices corriges
Télécharger PDFphilippe.roux@univ-rennes1.fr licence CC-BY-NC-SA
DUT Informatique
semestre 2
Th ́eorie des Graphes
Graphes et mod ́elisation
Math ́ematiques
TD n◦ 2
Exercice1
On consid`ere le sous-ensembleSdes pays d’Europe suivants :
1. Autriche (A)
2. Benelux (B)
3. Suisse (Ch)
4. Allemagne (D)
5. Espagne (E)
6. France (F)
7. Gr`ece (G)
8. Italie (I)
9. Portugal (P)
10. Grande-Bretagne (Uk)SoientP 1etP 2
deux pays deS, on d ́efinit la relation÷par :P 1÷P 2⇐⇒ ≪
on peut aller deP1 `aP2 en traversant une seule fronti`ere terrestre≫ .
1. Cette relation ́etait-elle r ́eflexive, sym ́etrique, anti-sym ́etrique, transitive ?
2. Est-il pr ́ef ́erable de repr ́esenter÷par un graphe orient ́e ? simple ?
3. Repr ́esenter ce graphe ? Quelle est son ordre et sa taille ? Son nombre chromatique ?
4. Ce graphe est-il connexe ? Combien poss`ede-t-il de composantes connexes ?
5. On note⊲⊳la relation associ ́ee `a la fermeture transitive de ce graphe.
Exprimer par une phrase la plus simple possible la relationP1 ⊲⊳ P2 .
6. Donner la matrice d’adjacence de ce graphe et de sa fermeture transitive ?1 philippe.roux@univ-rennes1.fr licence CC-BY-NC-SA
DUT Informatique
semestre 2
Th ́eorie des Graphes
Graphes et mod ́elisation
Math ́ematiques
TD n◦ 2
Exercice2
Lemme des poign ́ees de mains
1. Montrer que dans un graphe non-orient ́e, la somme des degr ́es est un nombre pair.
2. Est-il possible de relier 5 ordinateurs de sorte que chaque appareil soit reli ́e avec
exactement trois autres ?
3. Montrer que dans un graphe, le nombre de sommets de degr ́e impair est pair.
4. Existe-t-il un graphe non-orient ́e dont les sommets ont pour degr ́e 1,1,2,2,3 ?
5. Montrer que dans un graphe d’ordrenet de taillemo`u tous les sommets ont le
mˆeme degr ́er(graphe r ́egulier) on am=1 2n×r. 6. SoitGun graphe simple et non-orient ́e avec 4 sommets tous de degr ́e 2.Combien
y a-t-il d’arˆetes ? Repr ́esenter un tel graphe.
7. SoitGun graphe simple et non-orient ́e avec 15 arˆetes, 3 sommets de degr ́e 4 et
tous les autres sommets de degr ́e 3. Quel est le nombrende sommets du graphe ?
Repr ́esenter un tel graphe.
Indication :Une foisnconnu, placer les sommets de degr ́e4au centre et les
sommets de degr ́e3autour.
Exercice3 Graphe complet
SoitG= (S, A) un graphe complet d’ordren
1. Quel est la taillemdu graphe suivant que
(a)Gest un graphe orient ́e quelconque
(b)Gest un graphe orient ́e et simple
(c)Gest un graphe non-orient ́e et simple
(d)Gest un graphe non-orient ́e quelconque
Indication :Raisonner `a partir de la matrice d’adjacence du graphe ou utiliser le
lemme des poign ́ees de mains
2. Dans un tournois de Football1 le premier tour est organis ́e sous forme de≪ poule≫ de
4 ́equipes o`u chaque ́equipe doit rencontrer toutes les autres.
(a) Repr ́esenter la situation par un graphe. Combien de matchs joue chaque ́equipe ?
Combien de matchs y a-t-il en tout ?
(b) Que deviennent ces r ́esultats avec des poules de 5 ́equipes ?
(c) Dans une des poules les cinq ́equipes ont gagn ́e respectivement 3,2,2,1,1 matchs.
Combien y a-t-il eu de match(s) nul(s) ?
(d) Le nombre de matches ́etant trop important les organisateurs d ́ecident de faire
jouer seulement 3 matchs `a chaque ́equipe. Comment l’organiser ?
1. vous pouvez remplacer Football par le sport collectif de votre choix2 philippe.roux@univ-rennes1.fr licence CC-BY-NC-SA
DUT Informatique
semestre 2
Th ́eorie des Graphes
Graphes et mod ́elisation
Math ́ematiques
TD n◦ 2
Exercice4
Coloriage de graphes [DS 2010,5pts]
Durant la soir ́ee sept ́etudiants A,B,C,D,E,F,G se sont rendus travailler dans la salle deTP ≪
libre-service≫ , le tableau suivant pr ́ecise≪ qui a rencontr ́e qui≫ :
l’ ́el`eveABCDEFG
`a rencontr ́eD,ED,E,F,GE,GA,B,EA,B,C,D,F,GB,E,GB,C,E,F
1. Repr ́esenter les donn ́ees de ce tableau par un grapheGdont les sommets sont les ́etudiants. Pr ́eciser la nature du graphe (simple ou pas ? orient ́eou pas ?) et justifier
votre choix.
2. Donner un coloriage deG.
3. Justifier si ce coloriage est optimal et en d ́eduire le nombre chromatiqueγ(G).
Indication :On pourra utiliser la plus grande clique deG
4. Combien faut il de PC dans la salle de TP pour que tous les ́etudiantsaient pu
travailler seul sur une machine ?
5. On sait qu’il y a eu constamment au moins 2 machines de libres dans la salles.
Combien la salle a-t-elle de machines ?
Exercice5 Mr et Mme X assistent `a une r ́eunion. Il y a trois autres couples dans l’assistance et
plusieurs poign ́ees de mains sont ́echang ́ees. Personne ne serre sa propre main et les ́epoux
ne se serrent pas la main. Deux personnes quelconques de l’assembl ́ee se serrent la main
au plus une fois. Mr X constate que les 7 autres personnes ont ́echang ́e des poign ́ees de
mains en nombres tous distincts.
1. Quelles sont les valeurs possibles pour le nombre de poign ́ees de mains serr ́ees par
chaque personne ? Que peut on en d ́eduire pour Mr X ?
2. Repr ́esenter la situation par un graphe, pr ́eciser le type de graphes.
Indication :Positionner les 8 sommets du graphes en4groupes de2et tracer les
arˆetes en commen ̧cant par le sommet de plus haut degr ́e
3. Combien de poign ́ees de mains Mr et Mme X ont-ils ́echang ́e avec les autres
membres de la r ́eunion ?3 philippe.roux@univ-rennes1.fr licence CC-BY-NC-SA
DUT Informatique
semestre 2
Th ́eorie des Graphes
Graphes et mod ́elisation
Math ́ematiques
TD n◦ 2
Exercice6
Craquage de digicode [5.5pts]
L’acc`es d’un bˆatiment est contrˆol ́e par un digicode dont la combinaison est form ́ee d’une
suite de 3 lettresX1 X2 X3 ne pouvant prendre que 2 valeursXi =AouB. Pour entrer,
sans connaˆıtre le code, il faut normalement tenter chacune des combinaisons possibles
(AAA,AAB,. . .) mais dans les faits il est possible d’entrer avec bien moins de tentatives.
En effet lorsqu’on saisit une chaˆıne deplettresX1 X2 X3 . . . Xp le digicode teste successi-
vement les sous-chaˆınesX1 X2 X3 ,X2 X3 X4 ,. . .,Xp−2 Xp−1 Xp (par exemple taperAAABB
revient `a testerAAA,AAB,ABB).
Pour trouver la chaˆıne la plus courte possible permettant d’entrerdans le bˆatiment
sans connaˆıtre le code, on repr ́esente le probl`eme par ungraphe orient ́eGdont :
•les sommets repr ́esentent les diff ́erentes combinaisonsX1 X2 X3 •les arcs joignent des combinaisons obtenues successivement par ajout d’une lettre
`a la fin de la combinaison pr ́ec ́edente, par exemple en ajoutantB`a la fin deAAA
on obtient une nouvelle chaˆıneAAABqui testera la combinaisonAABdonc on
aura un arc :AAA−→AAB
1. Quel est l’ordre du graphe (c’est `a dire le nombre de combinaisonspossibles) ?
Combien de lettres faut-il saisir pour essayer toutes ces combinaisons une `a une? 2. Quel sont les degr ́es entrant et sortant de chaque sommet ? En d ́eduire la taille du
grapheG(c’est `a dire le nombre d’arcs) `a l’aide du lemme des poign ́ees de mains.
3. Repr ́esenter le grapheGdu probl`eme de telle sorte qu’il soit planaire.4. `
A quel type de chemin du grapheGcorrespond la solution du probl`eme ? Trouver
la solution `a partir du graphe (sous forme d’une chaˆıne de caract`eres compos ́ee de
suite d’une de A et de B) et pr ́eciser la longueur de la chaˆıne trouv ́ee.