Théorie des graphes : Graphes cheminements d un graphe fermeture transitive
Télécharger PDFphilippe.roux@univ-rennes1.fr licence CC-BY-NC-SA
DUT Informatique
semestre 2
Th ́eorie des Graphes
Cheminements dans un graphe
Math ́ematiques
TD n◦ 3
Exercice1
Le plan ci-dessous repr ́esente un mus ́ee constitu ́e de 8 salles communiquant par 11 portes.
Chacune des portes est orn ́ee d’une d ́ecoration consid ́er ́ee comme une merveille architec-
turale (y compris la porte d’entr ́ee du mus ́ee). On voudrait donc visiter l’ensemble des
salles du mus ́ee en passant une fois par chaque porte et en perdant le moins de temps
possible bien sˆur.678 34521 1. Mod ́eliser ce probl`eme par un graphe `a 9 sommets.2. `
A quoi correspond la solution du probl`eme en th ́eorie des graphes ?
3. Donner si c’est possible une solution, sinon justifier l’impossibilit ́e.
4. Comment pourrait-on modifier le graphe pour qu’il devienne Eulerien ?` A quoi cela
correspond-il concr`etement sur le graphe ?
5. La salle 8 est en travaux et ne peux ˆetre visit ́ee, peut-on encore trouver une solution
au probl`eme. Mˆeme question avec la salle 4.
Exercice2 Fermeture transitive
Soit le grapheG= (S, A) avec :
S={1; 2; 3; 4; 5; 6}A={(1,2); (1,4); (2,3); (3,2); (4,5); (5,6); (6,6); (3,6)}
1. Repr ́esentation du graphe
(a) S’agit-il d’un graphe orient ́e ou non-orient ́e ?
(b) Quel est l’ordre et la taille de ce graphe ?
(c) Repr ́esenter ce graphe par un diagramme sagittal.
(d) Donner sa matrice d’adjacenceM.
(e) Donner ses listes d’adjacencesLSetTS.
2. Fermeture transitive
(a) Justifier que le grapheGn’est pas transitif.
(b) Ajouter les 7 arcs manquants `aGpour obtenir un graphe transitifG∗ (c) SoitG′ le graphe ayant pour matrice d’adjacenceM′ =M+M2 . Repr ́esenter
le grapheG′ , quelles sont les diff ́erences avec le grapheG?
(d) SoitG′′ le graphe ayant pour matrice d’adjacenceM′′ =M+M2 +M3 .
Repr ́esenter le grapheG′′ quelles sont les diff ́erences avecGetG′ ?
(e) Que repr ́esente le grapheG′′ par rapport au grapheG?1 philippe.roux@univ-rennes1.fr licence CC-BY-NC-SA
DUT Informatique
semestre 2
Th ́eorie des Graphes
Cheminements dans un graphe
Math ́ematiques
TD n◦ 3
Exercice3
Chaˆınes de dominos
On consid`ere des dominos dont les faces sont num ́erot ́ees 1, 2,3, 4 et 5.
1. On repr ́esente une chaˆıne de dominos par un graphe non-orient ́e ayant pour som-
metsS={1; 2; 3; 4; 5}et o`u chaque arˆete{x;y}repr ́esente le domino ayant pour
num ́erosxety. Quel est ce graphe en excluant les doubles ? En tenant compte les
doubles ?
2. De combien de dominos dispose-t-on en tout, en excluant les doubles ? En tenant
compte les doubles ?
3. En d ́eduire que l’on peut arranger ces dominos de fa ̧cons `a former une boucle
ferm ́ee (en utilisant la r`egle habituelle de contact entre les dominos).
4. Si l’on prend des dominos dont les faces sont num ́erot ́ees de 1 `a n, est-il possible
de les arranger de fa ̧con `a former une boucle ?
Exercice4 D ́ecomposition en niveaux
D ́ecomposer les graphes suivants en niveaux :1 23 45 67 8910 123 456 78 9102 philippe.roux@univ-rennes1.fr licence CC-BY-NC-SA
DUT Informatique
semestre 2
Th ́eorie des Graphes
Cheminements dans un graphe
Math ́ematiques
TD n◦ 312 34 567 8910 12 34 56 78 910 3
philippe.roux@univ-rennes1.fr licence CC-BY-NC-SA
DUT Informatique
semestre 2
Th ́eorie des Graphes
Cheminements dans un graphe
Math ́ematiques
TD n◦ 3
Exercice5
Graphesτ- ́equivalents et graphesτ-minimaux
On noteG∗ la fermeture transitive d’un graphe orient ́eG= (S, A), et on dira :
•Deux graphes sontτ- ́equivalents ssi ils ont la mˆeme fermeture transitive,
•Un graphe estτ-minimal si aucun graphe partiel ne lui estτ- ́equivalent,[G 1τG 2⇔G ∗1 =G∗ 2
]et[G= (S, A)τ-minimal⇔ ∀A′ ⊂A, G′ = (S, A′ )⇒G′ 6τG]
1. Calculer la fermeture transitive des graphes ci-dessous (ajouter les arcs man-
quants) :1 23 412 341 23 412 34 Ces graphes sont-ilsτ-minimaux ? Sinon donner un grapheτ-minimal etτ- ́equivalent.
2. Pour chacun des 2 graphes suivants : calculerG∗ puis trouverG′ un grapheτ-
minimal etτ- ́equivalent `aG:1 234 51 23 456 3. Montrer que si un graphe poss`ede 2 graphesτ-minimaux diff ́erents alors il poss`ede
forc ́ement des circuits.
4. Trouver un graphe qui poss`ede plusieurs graphesτ-minimaux etτ- ́equivalents.
Indication :consid ́erer un graphe `a 4 sommets dont 3 forment un circuit.