Déterminer la matrice adjacente d'un graphe Exercice

Ce contenu a été rédigé par l'équipe éditoriale de Kartable.

Dernière modification : 07/08/2019 - Conforme au programme 2019-2020

Quelle est la matrice adjacente au graphe suivant ?

A =\begin{pmatrix} 0 &0&0&0&0&0 \cr\cr 0&0&0 &0&1&1\cr\cr 0&0&0&1&0&0 \cr\cr 0&1&0&0&1&0 \cr\cr 1&0&0&0&1&0 \cr\cr 0&0&1&0&0&0 \end{pmatrix}

A =\begin{pmatrix} 1 &0&1&0&0&1 \cr\cr 0&0&1 &0&1&0\cr\cr 0&0&1&1&0&0 \cr\cr 0&1&0&0&0&1 \cr\cr 1&0&0&0&1&0 \cr\cr 0&0&1&0&0&0 \end{pmatrix}

A =\begin{pmatrix} 0 &0&1&0&0&1 \cr\cr 0&0&0 &0&0&0\cr\cr 0&0&0&1&1&0 \cr\cr 0&1&0&0&1&0 \cr\cr 1&0&0&0&0&0 \cr\cr 0&0&1&0&0&0 \end{pmatrix}

A =\begin{pmatrix} 0 &0&0&0&0&1 \cr\cr 0&0&0 &0&1&0\cr\cr 0&0&0&1&0&0 \cr\cr 0&1&0&0&0&0 \cr\cr 1&0&0&0&0&0 \cr\cr 0&0&1&0&0&0 \end{pmatrix}

D'après le cours, on sait qu'un graphe orienté d'ordre n admet une matrice adjacente carrée A de format \left(n ;n\right) dont les coefficients a_{i;j} sont égaux au nombre de flèches issues de i à destination de j.

Ainsi toutes les flèches issues d'un même sommet sont récapitulées sur une même ligne de la matrice.

On peut ainsi détailler les différentes arêtes sommet par sommet :

Le sommet A relie uniquement le sommet F.
Le sommet B relie uniquement le sommet E.
Le sommet C relie uniquement le sommet D.
Le sommet D relie uniquement le sommet B.
Le sommet E relie uniquement le sommet A.
Le sommet F relie uniquement le sommet C.

On en déduit la matrice adjacente A :

A =\begin{pmatrix} 0 &0&0&0&0&1 \cr\cr 0&0&0 &0&1&0\cr\cr 0&0&0&1&0&0 \cr\cr 0&1&0&0&0&0 \cr\cr 1&0&0&0&0&0 \cr\cr 0&0&1&0&0&0 \end{pmatrix}

Quelle est la matrice adjacente au graphe suivant ?

A =\begin{pmatrix} 0 & 1&0&0&0 \cr\cr 1&0 &0&1&0\cr\cr 0&1&0&1&0 \cr\cr 0&0&0&0&1 \cr\cr 0&0&0&1&0 \end{pmatrix}

A =\begin{pmatrix} 0 & 1&0&1&0 \cr\cr 1&0 &0&1&0\cr\cr 0&0&0&1&0 \cr\cr 0&0&1&0&1 \cr\cr 0&0&0&1&0 \end{pmatrix}

A =\begin{pmatrix} 0 & 1&0&1&0 \cr\cr 1&0 &1&1&0\cr\cr 0&0&0&1&0 \cr\cr 0&1&1&0&1 \cr\cr 0&0&0&0&0 \end{pmatrix}

A =\begin{pmatrix} 0 & 1&1&1&0 \cr\cr 1&0 &1&1&0\cr\cr 0&0&0&1&0 \cr\cr 0&0&1&0&1 \cr\cr 0&0&0&1&0 \end{pmatrix}

Ainsi toutes les flèches issues d'un même sommet sont récapitulées sur une même ligne de la matrice.

On peut ainsi détailler les différentes arêtes sommet par sommet :

Le sommet A relie les sommets B et D uniquement.
Le sommet B relie les sommets A et D uniquement.
Le sommet C relie le sommets D uniquement.
Le sommet D relie les sommets C et E uniquement.
Le sommet E relie le sommets D uniquement.

On en déduit la matrice adjacente A :

A =\begin{pmatrix} 0 & 1&0&1&0 \cr\cr 1&0 &0&1&0\cr\cr 0&0&0&1&0 \cr\cr 0&0&1&0&1 \cr\cr 0&0&0&1&0 \end{pmatrix}

Quelle est la matrice adjacente du graphe suivant ?

A =\begin{pmatrix} 0 & 1&0&1&0 \cr\cr 0&0 &0&0&0\cr\cr 0&1&0&1&1 \cr\cr 0&0&0&0&0\cr\cr 0&0&0&0&1 \end{pmatrix}

A =\begin{pmatrix} 0 & 1&0&1&0 \cr\cr 1&0 &1&0&0\cr\cr 0&1&0&1&1 \cr\cr 1&0&1&0&0\cr\cr 0&0&1&0&1 \end{pmatrix}

A =\begin{pmatrix} 0 & 1&0&1&0 \cr\cr 0&0 &0&0&0\cr\cr 0&1&0&1&1 \cr\cr 0&0&0&0&0\cr\cr 0&0&1&0&1 \end{pmatrix}

A =\begin{pmatrix} 0 & 1&0&1&0 \cr\cr 1&0 &0&0&0\cr\cr 0&1&0&1&1 \cr\cr 0&0&0&0&0\cr\cr 0&0&0&0&0 \end{pmatrix}

Quelle est la matrice adjacente du graphe suivant ?

A =\begin{pmatrix} 0 & 1&0&1&1 \cr\cr 0&0&0&0&0\cr\cr 1&0&0&1&0 \cr\cr 0&0&0&0&0\cr\cr 0&0&1&0&0 \end{pmatrix}

A =\begin{pmatrix} 0 & 1&0&1&0 \cr\cr 0&0 &0&0&0\cr\cr 0&1&0&1&1 \cr\cr 0&0&0&0&0\cr\cr 0&0&0&0&1 \end{pmatrix}

A =\begin{pmatrix} 0 & 1&0&1&1 \cr\cr 0&0&0&0&0\cr\cr 1&0&0&1&0 \cr\cr 0&0&0&0&0\cr\cr 1&0&1&0&E \end{pmatrix}

A =\begin{pmatrix} 0 & 1&0&1&0 \cr\cr 1&0 &0&0&0\cr\cr 0&1&0&1&1 \cr\cr 0&0&0&0&0\cr\cr 0&0&0&0&0 \end{pmatrix}

Quelle est la matrice adjacente du graphe suivant ?

A =\begin{pmatrix} 0 & 1&1&1 \cr\cr 1&0 &1&1\cr\cr 1&1&1&0 \cr\cr 1&1&0&0\end{pmatrix}

A =\begin{pmatrix} 0 & 1&1&1 \cr\cr 1&1 &1&1\cr\cr 1&1&1&0 \cr\cr 1&1&0&0\end{pmatrix}

A =\begin{pmatrix} 0 & 0&1&1 \cr\cr 1&0 &1&0\cr\cr 1&1&1&0 \cr\cr 0&1&0&0\end{pmatrix}

A =\begin{pmatrix} 0 & 1&0&1 \cr\cr 1&0 &1&1\cr\cr 1&1&1&0 \cr\cr 1&1&0&0\end{pmatrix}

Quelle est la matrice adjacente du graphe suivant ?

A =\begin{pmatrix} 1 & 1&1&0&0 \cr\cr 0&1 &1&0&0\cr\cr 0&0&1&1&1 \cr\cr 0&1&1&0&0 \cr\cr0&0&1&0&0 \cr\cr \end{pmatrix}

A =\begin{pmatrix} 1 &0&1&0&0 \cr\cr 0&1 &1&0&0\cr\cr 0&1 &1&0&0\cr\cr 0&0&1&1&1 \cr\cr 0&1&0&0&0 \cr\cr \end{pmatrix}

A =\begin{pmatrix} 1 & 0&1&0&0 \cr\cr 0&0 &0&1&1\cr\cr 0&0&1&1&1 \cr\cr 1&0&0&0&0 \cr\cr 0&1&0&0&0 \cr\cr\end{pmatrix}

A =\begin{pmatrix} 0& 1&1&0&0 \cr\cr 0&1 &1&0&0\cr\cr 0&0&1&1&1 \cr\cr 0&1&0&0&0 \cr\cr0&1 &1&0&0\cr\cr \end{pmatrix}