Théorie des graphes : Graphes relations binaires matrices d'adjacence
Télécharger PDFExercice 1 : Relations binaires
On considère les deux ensembles A = {1, 2, 3, 4, 5} et B = {a, b, c, d}.
(a) Diagramme sagittal et matrice d’adjacence de S
Les relations R et S de A → B sont définies par les matrices suivantes :
Matrice de R :
MR =
0 0 0 1
0 1 0 0
0 0 0 1
0 0 1 0
1 0 0 0
Avec A = {1, 2, 3, 4, 5} et B = {a, b, c, d}.
Matrice de S :
MS =
0 0 1 0
0 1 0 0
0 0 0 1
1 0 0 0
0 0 0 0
Avec A = {1, 2, 3, 4, 5} et B = {a, b, c, d}.
(b) Propriétés de R
Parmi les propriétés suivantes, lesquelles s’appliquent à R ?
- fonction
- application
- injection
- surjection
- bijection
- aucune
(c) Propriétés de S
Parmi les propriétés suivantes, lesquelles s’appliquent à S ?
- fonction
- application
- injection
- surjection
- bijection
- aucune
Exercice 2 : Matrices d’adjacence et propriétés des relations
On considère de nouveau les relations R de A → B et T de A → A.
(a) Composition de relations : R ◦ T ou T ◦ R
Laquelle des deux relations R ◦ T ou T ◦ R est bien définie ? Calculer sa matrice d’adjacence en précisant la formule utilisée.
(b) Ensembles de départ et d’arrivée de R−1 ◦ R
Quels sont les ensembles de départ et d’arrivée de la relation R−1 ◦ R ? Calculer sa matrice d’adjacence en précisant la formule utilisée.
Exercice 3 : Liste d’adjacence et prédécesseurs
1. Liste d’adjacence du graphe
Calculer les listes d’adjacence du graphe donné par les arêtes suivantes :
- 1-2
- 3-4
- 5-6
- 2-3
- 4-5
2. Construction du graphe à partir des listes d’adjacence
Construire le graphe à partir des listes d’adjacence suivantes :
LS = {3, 5, 1}, {5, 2}, {1, 3}, {4, 5}, {2, 3, 5}
3. Liste des prédécesseurs de l’arbre
Calculer la liste des prédécesseurs de l’arbre défini par les arêtes suivantes :
- 1-2
- 3-4
- 5-6
- 7-8
4. Dessiner l’arbre à partir de la liste des prédécesseurs
Dessiner l’arbre ayant pour liste de prédécesseurs : P = {5, 1}, {5, 7}, {0}, {7, 8}, {5}
FAQ
Qu’est-ce qu’une matrice d’adjacence ?
Une matrice d’adjacence est une représentation tabulaire d’un graphe où chaque ligne et chaque colonne correspondent à un sommet. La valeur à l’intersection d’une ligne et d’une colonne indique si les deux sommets sont connectés par une arête.
Comment calculer la composition de deux relations ?
Pour calculer la composition de deux relations R et S, on utilise la formule suivante : (R ◦ S)ij = Σk (Rik × Skj). Cela signifie qu’un élément i est en relation avec j si i est en relation avec un élément intermédiaire k, et que k est en relation avec j.
Quelle est la différence entre une liste d’adjacence et une liste de prédécesseurs ?
Une liste d’adjacence indique les sommets directement connectés à un sommet donné (successeurs), tandis qu’une liste de prédécesseurs indique les sommets qui ont une arête pointant vers le sommet considéré.