Graphes et matrices

On considère le graphe orienté (G) ci-dessous :

$1.~a)$ Tableau résumant les degrés extérieurs et intérieurs des sommets :

$\begin{array} {|c|ccc|ccc|ccc|ccc|ccc|ccc|ccc|ccc|} \hline \text{Sommet}&&A && & B&& & C&& & D && & E & \\ \hline &&&&&&&&&&&&&&&\\d^+& &2&&&2&& &1 & & &1 & & &1 &\\&&&&&&&&&&&&&&& \\ \hline &&&&&&&&&&&&&&&\\d^-& &2&&&1&& &1 & & & 2& & &1 &\\&&&&&&&&&&&&&&& \\ \hline \end{array}$

$1.~b)$ Justifions que le graphe (G) n'admet pas un cycle orienté eulérien.

En effet, un graphe connexe admet un cycle eulérien si tous ses sommets sont de degré pair.

Or les degrés de B et de D sont égaux à 3, donc impairs.

Dès lors, le graphe (G) n'admet pas un cycle orienté eulérien.

$1.~;c)$ Montrons que (G) admet une chaîne orientée eulérienne.

Pour qu'un graphe comporte une chaîne eulérienne, il faut qu'il possède 0 ou deux sommets de degré impair.

Dans le cas de deux sommets de degré impair, ils seront situés au début et à la fin de la chaîne.

Dans cet exercice, le graphe (G) possède deux sommets de degré impair : les sommets B et D.

Il existe donc une chaîne eulérienne commençant par B et se terminant par D.

Par exemple, la chaîne B - A - B - E - D - C - A - D.

$2.$ Ci-dessous, la matrice ${ M }$ associée au graphe (G).

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

$3.$ On donne les matrices : ${ M^3=\begin{pmatrix} 1 &1 &0 &2 &0 \\ 1& 0 &2 &0 &1 \\ 1& 0 &1 & 0&1 \\ 0&1 &0 &1 &0 \\ 1&0 &0 &0 &0 \end{pmatrix} \text{ et } M^4=\begin{pmatrix} 1 &1 &2 &1 &1 \\ 2&1 & 0 & 2 &0 \\ 1& 1& 0 & 2 & 0\\ 1& 0& 1& 0 &1 \\ 0& 1 & 0& 1 & 0 \end{pmatrix} }$

$3.~a)$ Déterminons le nombre de chaînes orientées de longueur 3 arrivant au sommet B.

Additionnons les éléments de ${ M^3 }$ correspondant à l'arrivée au sommet B, soient les éléments de la 2^ème colonne.

Nous obtenons : 1 + 0 + 0 + 1 + 0 = 2.

Il y a donc deux chaînes orientées de longueur 3 arrivant au sommet B.

$3.~b)$ Déterminons le nombre de chaînes orientées de longueur 7 allant de E à C.

Ce nombre est l'élément de la matrice ${ M^7 }$situé à la 5^eme ligne 3^eme colonne.

Cet élément est le produit de la matrice-ligne correspondant à la 5^eme ligne de ${ M^3 }$ par la matrice-colonne correspondant à la 3^eme colonne de ${ M^4. }$ $\begin{pmatrix}1&0&0&0&0\end{pmatrix}\times \begin{pmatrix}2\\0\\0\\1\\0\end{pmatrix}=2+0+0+0+0=2$

Il existe donc deux chaînes orientées de longueur 7 allant de E à C.

Ces deux chaînes sont : ${\boxed{E - D - C - A - B - E - D - C} }$ et ${\boxed{E - D - C - A - B - A - D - C} }$