Théorie des graphes : Graphes relations binaires matrices d'adjacence
Télécharger PDFDUT Informatique
semestre 2
Th ́eorie des Graphes
r ́evision matrices d’adjacence
Math ́ematiques
Soutien n◦ 1
Exercice1
Relations binaires
On consid`ere les deux ensemblesA={1; 2; 3; 4; 5}et B={a;b;c;d}
1. Soient les deux relationsRetSdeA→B, d ́efinies ci-dessous :M R= 0 0 0 1
0 1 0 0
0 0 0 1
0 0 1 0
1 0 0 0 1 23 45 ab cd ABS
(a) faire le diagramme sagittal deRet calculer la matrice d’adjacence deS(`a 2 ensembles)1 23 45 ab cd ABR MS =
(b) Parmi les propri ́et ́es suivantes lesquelles s’appliquent `aR:
fonction
application
injection
surjection
bijectionaucune (c) Parmi les propri ́et ́es suivantes lesquelles s’appliquent `aS:
fonction
application
injection
surjection
bijectionaucune 1
DUT Informatique
semestre 2
Th ́eorie des Graphes
r ́evision matrices d’adjacence
Math ́ematiques
Soutien n◦ 1
2. Soient les deux relationsT, deA→A, etU, deB→B, d ́efinies ci-dessous :M T= 1 0 0 1 1
0 1 0 0 0
0 0 1 0 0
0 0 0 1 1
1 1 0 0 1 a bc d
(a) Faire le diagramme sagittal deTet calculer la matrice d’adjacence deU(`a 1 ensemble)1 23 45 MU =
(b) Parmi les propri ́et ́es suivantes lesquelles s’appliquent `aT:
r ́eflexive
sym ́etrique
anti-sym ́etrique
transitive
relation d’ordre
relation d’ ́equivalence
(c) Parmi les propri ́et ́es suivantes lesquelles s’appliquent `aU:
r ́eflexive
sym ́etrique
anti-sym ́etrique
transitive
relation d’ordre
relation d’ ́equivalence2 DUT Informatique
semestre 2
Th ́eorie des Graphes
r ́evision matrices d’adjacence
Math ́ematiques
Soutien n◦ 1
3. On consid`ere de nouveau les relationsR, deA→B, etT, deA→A:M R= 0 0 0 1
0 1 0 0
0 0 0 1
0 0 1 0
1 0 0 0 M T= 1 0 0 1 1
0 1 0 0 0
0 0 1 0 0
0 0 0 1 1
1 1 0 0 1
(a) Laquelle des deux relationsR ◦ TouT ◦ Rest bien d ́efinie ? Calculer sa matrice
d’adjacence en donnant la formule utilis ́ee.
(b) Quels sont les ensembles de d ́epart et d’arriv ́e de la relationR−1 ◦ R? Calculer sa
matrice d’adjacence en donnant la formule utilis ́ee.3 DUT Informatique
semestre 2
Th ́eorie des Graphes
r ́evision matrices d’adjacence
Math ́ematiques
Soutien n◦ 1
Exercice2
bf liste adjacence et pr ́ed ́ecesseurs
1. Calculer les listes d’adjacence du graphe :12 34 56 2. Construire le graphe de listes d’adjacence :LS= 351521345235
TS=1356101013
3. Calculer la liste des pr ́ed ́ecesseurs de l’arbre :1 23 456 78
4. Dessiner l’arbre ayant pour liste de pr ́ed ́ecesseurs :P= 51570785