Théorie des graphes : Graphes theorie des graphes representation des graphes exer
Télécharger PDFphilippe.roux@univ-rennes1.fr licence CC-BY-NC-SA
DUT Informatique
semestre 2
Th ́eorie des Graphes
R ́epr ́esentation des graphes
Math ́ematiques
TD n◦ 1
Exercice1
[DS avril 2008, Relations binaires, 5pts]
Soit l’ensembleE={Andr ́e ;Brigitte ;Christian ;Didier ; ́
Eric ;Fran ̧coise}={a;b;c;d;e;f}
ordonn ́e, par d ́efaut, suivant l’ordre alphab ́etique.
1. On consid`ere la relation binairePsurEd ́efinie par
xPy⇐⇒xest le p`ere ou la m`ere dey
et dont le diagramme sagittal est :ab cde fE P
(a) Calculer la matrice d’adjacenceMP deP.
(b) Donner le domaine de d ́efinition dePet son image.
(c)Pest elle une fonction ?
2. On consid`ere la relation binaireFsurEd ́efinie par
xFy⇐⇒xest le fr`ere ou la sœur dey
et dont la matrice d’adjacence est :MF =
0 0 0 1 0 0
0 0 1 0 0 0
0 1 0 0 0 0
1 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 1 0
(a) Faire le diagramme sagittal deF.
(b)Fest elle une relation d’ ́equivalence ?
3. On consid`ere la relation binaireCsurEd ́efinie par
xCy⇐⇒xest le cousin ou la cousine dey
(a) D ́emontrer queC=P ◦ F ◦ P−1 (b) En d ́eduire (par le calcul) la matrice d’adjacenceMC deCet son diagramme
sagittal.1 philippe.roux@univ-rennes1.fr licence CC-BY-NC-SA
DUT Informatique
semestre 2
Th ́eorie des Graphes
R ́epr ́esentation des graphes
Math ́ematiques
TD n◦ 1
Exercice2
Matrice et listes d’adjacence
1. (a) Calculer les listes d’adjacence et la matrice d’adjacence du graphe suivant :1 23 45 6
(b) Construire le graphe ayant pour listes d’adjacence :LS= 4131512TS= 124568
2. (a) calculer les listes d’adjacence et la matrice d’adjacence du graphe suivant :1 23 45 (b) Si on ajoute l’arc (2,4) que deviennent les listes d’adjacence ?
(c) construire le graphe ayant pour listes d’adjacence :LS= 36724235667371TS= 146710121415
(d) Si on enl`eve l’arc (4,3) que deviennent les listes d’adjacence ?2 philippe.roux@univ-rennes1.fr licence CC-BY-NC-SA
DUT Informatique
semestre 2
Th ́eorie des Graphes
R ́epr ́esentation des graphes
Math ́ematiques
TD n◦ 1
Exercice3
Arbres et listes de pr ́ed ́ecesseurs
1. Cas des graphes orient ́es :
(a) calculer la liste de pr ́ed ́ecesseurs
de l’arbre suivant :12 34 56 789 10
(b) construire l’arbre ayant pour liste de pr ́ed ́ecesseurs :
98607104487
2. Cas des graphes non-orient ́es :
(a) calculer la liste de pr ́ed ́ecesseurs
de l’arbre suivant :1 23 45 67 89 10
(b) construire l’arbre ayant pour liste de pr ́ed ́ecesseurs :
386101054430
(c) que remarquez vous ?
(d) De mˆeme, redessiner cet arbre en prenant comme racine le sommet 1 et calculer
la liste de pr ́ed ́ecesseurs associ ́ee.3 philippe.roux@univ-rennes1.fr licence CC-BY-NC-SA
DUT Informatique
semestre 2
Th ́eorie des Graphes
R ́epr ́esentation des graphes
Math ́ematiques
TD n◦ 1
Exercice4
Graphes valu ́es et Matrice des Poids
1. Calculer la matrice d’adjacence et la matrice des poids des graphessuivants :1 23 45 1417 41 719 165 12 34 514 174 17 1916 5
2. On modifie les deux graphes pr ́ec ́edents comme suit, modifier encons ́equence les
matrices des poids :1 23 45 1417 41 70 165 2−3 12 34 514 174 17 016 52 4