Retour aux exercices sur les graphes
L’objectif des exercices de cette page est de manipuler sur papier les deux représentations des graphes vues en cours : les matrices d’adjacence et les listes de successeurs.
- Pour chaque graphe ci-dessous, donnez :
- sa matrices d’adjacence,
- ses listes de successeurs,
- ses listes de prédécesseurs.
- Pour chaque tableau ci-dessous, tracez le graphe correspondant et donnez sa matrice d’adjacence.
-
sommets a b c d e successeurs b c,d d e -
sommets a b c d e prédécesseurs b c,d d e -
sommet a b c d prédécesseurs b,c,d a,c b,a,d a,c
-
- Pour chaque matrice d’adjacence ci-dessous, tracez le graphe associé et donnez ses listes de successeurs et de prédécesseurs.
- \(\begin{pmatrix} 0 & 1 & 1\\ 1 & 0 & 0\\ 1 & 0 & 0\\ \end{pmatrix}\) associée à l’ensemble de sommets $S=\{a,b,c\}$.
- \(\begin{pmatrix} 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 0\\ \end{pmatrix}\) associée à l’ensemble de sommets $S=\{a,b,c,d\}$.
