Théorie des graphes : Graphes cheminements d un graphe fermeture transitive
Télécharger PDFTD n°3 : Théorie des Graphes
Exercice 1 : Cheminements dans un musée
Le plan ci-dessous représente un musée constitué de 8 salles communiquant par 11 portes.
Chacune des portes est ornée d’une décoration considérée comme une merveille architecturale (y compris la porte d’entrée du musée). On souhaite visiter l’ensemble des salles du musée en passant une fois par chaque porte et en perdant le moins de temps possible.
1. Modéliser ce problème par un graphe à 9 sommets.
2. À quoi correspond la solution du problème en théorie des graphes ?
3. Donner, si c’est possible, une solution. Sinon, justifier l’impossibilité.
4. Comment pourrait-on modifier le graphe pour qu’il devienne eulérien ? À quoi cela correspond-il concrètement sur le graphe ?
5. La salle 8 est en travaux et ne peut être visitée : peut-on encore trouver une solution au problème ? Même question avec la salle 4.
Exercice 2 : Fermeture transitive
Soit le graphe G = (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ésentation du graphe
(a) S’agit-il d’un graphe orienté ou non orienté ?
Réponse : orienté.
(b) Quel est l’ordre et la taille de ce graphe ?
Réponse : L’ordre est 6 et la taille est 8 arcs.
(c) Représenter ce graphe par un diagramme sagittal.
(d) Donner sa matrice d’adjacence M.
Exemple de matrice d’adjacence (à compléter selon les arcs) :
1 2 3 4 5 6 1 0 1 0 1 0 0 2 0 0 1 0 0 0 3 0 1 0 0 1 1 4 0 0 0 0 1 0 5 0 0 0 0 0 1 6 0 0 0 0 0 1
(e) Donner ses listes d’adjacences LS et TS.
Exemple :
Liste d’adjacence LS :
- 1 : 2, 4
- 2 : 3
- 3 : 2, 6
- 4 : 5
- 5 : 6
- 6 : 6
Liste de transitivité TS :
- 1 : 2, 3, 4, 5, 6
- 2 : 3
- 3 : 2, 6
- 4 : 5, 6
- 5 : 6
- 6 : 6
2. Fermeture transitive
(a) Justifier que le graphe G n’est pas transitif.
Réponse : Par exemple, il n’existe pas d’arc entre 1 et 3, bien que (1,2) et (2,3) soient présents.
(b) Ajouter les 7 arcs manquants à G pour obtenir un graphe transitif G*.
(c) Soit G' le graphe ayant pour matrice d’adjacence M' = M + M². Représenter le graphe G' et quelles sont les différences avec le graphe G.
M² est la matrice obtenue en multipliant M par elle-même (opération booléenne).
(d) Soit G'' le graphe ayant pour matrice d’adjacence M'' = M + M² + M³. Représenter le graphe G'' et quelles sont les différences avec G et G'.
(e) Que représente le graphe G'' par rapport au graphe G ?
Réponse : G'' est la fermeture transitive complète de G.
Exercice 3 : Chaînes de dominos
On considère des dominos dont les faces sont numérotées de 1 à 5.
1. On représente une chaîne de dominos par un graphe non orienté ayant pour sommets S = {1, 2, 3, 4, 5} et où chaque arête {x, y} représente le domino ayant pour numéros x et y. Quel est ce graphe en excluant les doubles ? En tenant compte des doubles ?
2. De combien de dominos dispose-t-on en tout, en excluant les doubles ? En tenant compte des doubles ?
3. En déduire que l’on peut arranger ces dominos de façon à former une boucle fermée (en utilisant la règle habituelle de contact entre les dominos).
4. Si l’on prend des dominos dont les faces sont numérotées de 1 à n, est-il possible de les arranger de façon à former une boucle ?
Exercice 4 : Décomposition en niveaux
Décomposer les graphes suivants en niveaux :
Graphe 1 : 1-2-3-4-5-6-7-8-9-10
Graphe 2 : 1-2-3-4-5-6-7-8-9-10-12
Graphe 3 : 1-2-3-4-5-6-7-8-9-10-3
Exercice 5 : Graphes τ-équivalents et graphes τ-minimaux
On note G* la fermeture transitive d’un graphe orienté G = (S, A), et on dira :
• Deux graphes sont τ-équivalents si et seulement s’ils ont la même fermeture transitive,
• Un graphe est τ-minimal si aucun graphe partiel ne lui est τ-équivalent.
1. Calculer la fermeture transitive des graphes ci-dessous (ajouter les arcs manquants) et vérifier s’ils sont τ-minimaux. Sinon, donner un graphe τ-minimal et τ-équivalent.
Exemple de graphe :
1 → 2 1 → 3 2 → 4 3 → 4
2. Pour chacun des 2 graphes suivants, calculer G* puis trouver G' un graphe τ-minimal et τ-équivalent à G.
Exemple de graphe :
1 → 2 → 3 → 4 → 5
3. Montrer que si un graphe possède 2 graphes τ-minimaux différents, alors il possède forcément des circuits.
4. Trouver un graphe qui possède plusieurs graphes τ-minimaux et τ-équivalents.
Indication : Considérer un graphe à 4 sommets dont 3 forment un circuit.
FAQ
1. Qu’est-ce qu’un graphe eulérien ?
Un graphe est dit eulérien s’il possède un chemin eulérien, c’est-à-dire un chemin qui utilise chaque arête exactement une fois.
2. Comment calculer la fermeture transitive d’un graphe ?
La fermeture transitive d’un graphe G = (S, A) est obtenue en ajoutant tous les arcs {x, y} tels qu’il existe un chemin de x à y dans G.
3. Que signifie τ-minimal ?
Un graphe est τ-minimal si aucun sous-graphe (obtenu en supprimant des arcs) ne possède la même fermeture transitive.