Exercices Graphes

Soit le graphe suivant :

Quel est l’ordre du graphe et le degré de chaque sommet ?

Soit le graphe suivant :

Quel est l’ordre du graphe et le degré de chaque sommet ?

Une résidence comporte 4 bâtiments ($A$, $B$, $C$ et $D$). Le plan de cette résidence est schématisé par un graphe de sommets $A$, $B$, $C$ et $D$. Dans la matrice $M$ associée à ce graphe, $a_{ij}=1$ s’il est possible de se déplacer entre le bâtiment $i$ et le bâtiment $j$.

$M= \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{pmatrix}$

Tracer le graphe associé à la matrice d’adjacence $M$.