Théorie des graphes : Graphes theorie des graphes representation des graphes exer
Télécharger PDFTD n°1 – Théorie des Graphes : Représentation des Graphes
Exercice 1 : Relation binaire P (parenté)
Soit l’ensemble E = {André, Brigitte, Christian, Didier, Eric, Françoise}, noté par défaut {a, b, c, d, e, f} selon l’ordre alphabétique.
On considère la relation binaire P sur E définie par :
xPy ⇐⇒ x est le père ou la mère de y.
Le diagramme sagittal de P est donné par :
a → b, c, d, e,
f → E
(a) Calculer la matrice d’adjacence MP de P.
(b) Donner le domaine de définition de P et son image.
(c) P est-elle une fonction ?
Exercice 2 : Matrices et listes d’adjacence
1. (a) Calculer les listes d’adjacence et la matrice d’adjacence du graphe suivant :
1 → 2, 3
4 → 5, 6
(b) Construire le graphe ayant pour listes d’adjacence :
LS = 4 → 1, 3 ; 1 → 5 ; 1 → 2
TS = 1 → 2, 4 ; 5 → 6, 8
2. (a) Calculer les listes d’adjacence et la matrice d’adjacence du graphe suivant :
1 → 2, 3
4 → 5
(b) Si on ajoute l’arc (2, 4), que deviennent les listes d’adjacence ?
(c) Construire le graphe ayant pour listes d’adjacence :
LS = 3 → 6, 7 ; 2 → 4 ; 2 → 3 ; 5 → 6 ; 6 → 7 ; 3 → 7 ; 1 → 4
TS = 1 → 4, 6, 7 ; 10 → 12 ; 14 → 15
(d) Si on enlève l’arc (4, 3), que deviennent les listes d’adjacence ?
Exercice 3 : Arbres et listes de prédécesseurs
1. Cas des graphes orientés :
(a) Calculer la liste de prédécesseurs de l’arbre suivant :
1 → 2
3 → 4, 5
6 → 7, 8, 9
10 → (racine)
(b) Construire l’arbre ayant pour liste de prédécesseurs :
9 → 8, 6
0 → 7, 10
4 → 4
8 → 7
2. Cas des graphes non orientés :
(a) Calculer la liste de prédécesseurs de l’arbre suivant :
1 → 2
3 → 4, 5
6 → 7, 8
9 → 10
(b) Construire l’arbre ayant pour liste de prédécesseurs :
3 → 8, 6
10 → 10, 5
4 → 3
0 → (racine)
(c) Que remarquez-vous ?
(d) De même, redessiner cet arbre en prenant comme racine le sommet 1 et calculer la liste de prédécesseurs associée.
Exercice 4 : Graphes valués et Matrice des Poids
1. Calculer la matrice d’adjacence et la matrice des poids des graphes suivants :
Graphe 1 :
1 → 2 (poids 3)
1 → 4 (poids 5)
4 → 7 (poids 1)
7 → 19 (poids 1)
Graphe 2 :
1 → 2 (poids 1)
3 → 4 (poids 5)
5 → 12 (poids 3)
17 → 19 (poids 5)
2. On modifie les deux graphes précédents comme suit. Modifier en conséquence les matrices des poids :
Graphe 1 modifié :
1 → 2 (poids 3)
1 → 4 (poids 5)
4 → 7 (poids 1)
7 → 19 (poids 0)
Graphe 2 modifié :
1 → 2 (poids -3)
3 → 4 (poids 5)
5 → 12 (poids 1)
17 → 19 (poids 0)
16 → 5 (poids 2)
4 → 2 (poids 4)
FAQ
1. Qu’est-ce qu’une matrice d’adjacence ?
Une matrice d’adjacence est une représentation tabulaire d’un graphe où chaque ligne et colonne correspond à un sommet. Une entrée à 1 indique la présence d’un arc entre deux sommets, et 0 son absence.
2. Comment différencier un graphe orienté d’un non orienté dans les listes d’adjacence ?
Dans un graphe orienté, les listes d’adjacence indiquent les arcs sortants (successeurs) ou entrants (prédécesseurs) pour chaque sommet. Dans un graphe non orienté, les listes sont symétriques, car un arc (x, y) implique un arc (y, x).
3. Pourquoi la matrice des poids est-elle importante dans les graphes valués ?
Elle permet de stocker et manipuler les valeurs associées aux arcs, essentielles pour des calculs comme les plus courts chemins (ex. algorithme de Dijkstra) ou l’analyse des coûts.