Devoir sur les graphes

Un soin particulier sera apporté à la clarté de la rédaction et des justifications.

L'usage de la calculatrice est autorisé.

Durée : strictement moins d'une heure.

Exercice 1 (D'après bac ES, Liban 2006)

Pour chaque question dire si chaque affirmation est juste ou fausse, en justifiant.

Question 1

La matrice d'un graphe non orienté G, de sommets A, B, C, D, E est :

\[\begin{pmatrix} 0& 0& 1& 0& 1\\ 0& 0& 1& 1& 1\\ 1& 1& 0 &1& 0\\ 0 &1& 1& 0& 0\\ 1& 1& 0& 0& 0\\ \end{pmatrix}\]

a. Le graphe G comporte 12 arêtes.

Corrigé

Le graphe étant non orienté, chaque 1 compte pour l'extrémité d'une arête, comme il y a 12 extrémités, on a 6 arêtes. FAUX

b. Le graphe G admet une chaîne eulérienne.

Corrigé

Le graphe admet deux sommets de degrès impairs, donc l'affirmation est VRAIE

c. Le graphe G est complet.

Corrigé

Il n'y a pas d'arête entre A et B, donc le graphe n'est pas complet. FAUX

Question 2

M est la matrice d'un graphe G dont les sommets A, B, C et D sont rangés dans cet ordre.

\[\text{M}=\begin{pmatrix} 1& 1& 0& 1\\ 0& 0& 1& 1\\ 1& 0& 0& 0\\ 0& 1& 1& 0\\ \end{pmatrix}\]

On donne:

\[\text{M}^4 =\begin{pmatrix} 7& 6& 6& 6\\ 3& 4& 3& 3\\ 3& 3& 4& 3\\ 3& 3& 3& 4\\ \end{pmatrix}\]

a. Il y a 16 chemins de longueur 4 partant de B.

Corrigé

On compte les chemins partant de B en ajoutant les coefficients de la deuxième ligne de \(M^4\): \(3+4+3+3=13\) et \(13 \neq 16\). L'affirmation est FAUSSE.

b. Il y a 3 chemins de longueur 4 partant de C pour arriver à B : CABDB, CACAB et CAADB.

Corrigé

D'après la matrice \(M^4\) il y a bien 3 chemins de longueur 4 de C à B, mais au moins l'un des chemins proposés est incorrect : CACAB car A est un voisin de C mais C n'est pas un voisin de A. FAUX

c. Il y a 3 chemins de longueur 4 partant de B pour arriver à C : BCABC, BCADC et BDBDC.

Corrigé

D'après la matrice \(M^4\) il y a bien 3 chemins de longueur 4 de B à C, et tous les chemins proposés sont corrects VRAI

Exercice 2

Une exposition est organisée dans un parc. On décide d'y instaurer un plan de circulation : certaines allées sont à sens unique, d'autres sont à double sens. Le graphe ci-dessous modélise la situation.

{ width=30%}

1. Donner la matrice d'adjacence M de ce graphe (dans l'ordre alphabétique).

   Corrigé

   \[\text{M}=\begin{pmatrix} 0& 1& 0& 0& 1\\ 0& 0& 1& 1& 0\\ 0& 1& 0& 1& 0\\ 0& 0& 1& 0& 1\\ 1& 0& 0& 1& 0\\ \end{pmatrix}\]

2. Combien y-a-t-il de chemins de longueur 5 permettant de rendre de D à B ? Les donner tous.

   Corrigé

   Avec la calculatrice, on obtient:

   \[\text{M}^5=\begin{pmatrix} 1& 6& 9& 6& 10\\ 4& 5& 7& 11& 5\\ 4& 6& 6& 11& 5\\ 1& 5& 10& 6& 10\\ 6& 5& 5& 14& 2\\ \end{pmatrix}\]

   Donc il y a 5 chemins (coefficient \(m_{4,2}=5\)) qui relient D à B.

   Ces chemins sont DCBDCB, DCDEAB, DEDEAB, DEAEAB et DEABCB.

3. Montrer qu'il n'existe qu'un seul circuit de longueur 5 passant par le sommet A. Quel est ce cycle ? En est-il de même pour B ?

   Corrigé

   Le coefficient \(m_{1,1}=1\) donc un seul circuit : ABCDEA

   En revanche \(m_{2,2}=5\) donc 5 chaines de B à B (par exemple BCDEAB, BCB, BDCB... pas attendu).