Devoir surveillé – Graphes et matrices

Durée : 1 heure

Calculatrice autorisée

Exercice 1 (12 points)

On considère le graphe $G$ représenté ci-dessous.

Donner l'ordre de $G$.

Corrigé

L'ordre de $G$ est égal au nombre de sommets de $G$. Il y a 8 sommets, donc l'ordre de $G$ est 8.
Dresser un tableau donnant les degrés des sommets de $G$.

Corrigé

Sommet Degré

A 2

B 2

C 4

D 3

E 2

F 4

G 2

H 3
En déduire le nombre d'arêtes de $G$.

Corrigé

Le nombre d'arêtes de $G$ peut être calculé en utilisant la formule suivante :

\[\text{Nombre d'arêtes} = \frac{1}{2} \sum_{v \in V} \text{degré}(v)\]

En sommant les degrés des sommets, on obtient :

\[2 + 2 + 4 + 3 + 2 + 4 + 2 + 3 = 22\]

Donc, le nombre d'arêtes de $G$ est :

\[\dfrac{22}{2} = 11\]
$G$ est-il complet ?

Corrigé

Un graphe est complet s'il existe une arête entre chaque paire de sommets.

Dans $G$, il n'existe pas d'arête entre les sommets $A$ et $C$, par exemple. Par conséquent, $G$ n'est pas complet.
$G$ est-il connexe ?

Corrigé

Un graphe est connexe s'il existe un chemin entre chaque paire de sommets.

Dans $G$, il existe un chemin qui relie tous les sommets, par exemple : $A - B - C - G - H - F - D - E$.

Par conséquent, $G$ est connexe.
$G$ admet-il un cycle eulérien? Si oui, en donner un.

Corrigé

Dans $G$, on a deux sommets de degré impair : $D$ et $H$. Le départ et l'arrivée d'une chaîne eulérienne doivent être des sommets de degré impair. Comme ces sommets sont différents, $G$ admet une chaîne eulérienne mais pas de cycle eulérien.
$G$ admet-il une chaîne eulérienne? Si oui, en donner une.

Corrigé

D'après la question précédente, $G$ admet une chaîne eulérienne. En voici une :

\[H - A - B - C - G - H - F - C - D - F - E - D\]

Cette chaîne eulérienne commence à $H$ et se termine à $D$.
Déterminer $M$, matrice d'adjacence de ce graphe $G$. Les sommets seront pris dans l'ordre alphabétique.

Corrigé

La matrice d'adjacence $M$ de $G$ est donnée par :

\[M = \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \end{pmatrix}\]
Déterminer par un habile calcul le nombre de chaînes de longueur 4 reliant $C$ à $G$. Les donner toutes.
Corrigé

Le nombre de chaînes de longueur 4 reliant $C$ à $G$ peut être déterminé en calculant la puissance de la matrice d'adjacence $M^4$ et en regardant l'élément de la ligne correspondant à $C$ et de la colonne correspondant à $G$.

En effectuant le calcul, on trouve que l'élément $(C,G)$ de $M^4$ est égal à 4. Cela signifie qu'il existe 4 chaînes de longueur 4 reliant $C$ à $G$.

On a les chaînes suivantes :
1. $C - B - A - H - G$
2. $C - D - F - H - G$
3. $C - D - F - C - G$
4. $C - F - D - C - G$
Combien y a-t-il de chaînes de longueur 4 issues de $A$ ?

Corrigé

Le nombre de chaînes de longueur 4 issues de $A$ peut être déterminé en calculant la puissance de la matrice d'adjacence $M^4$ et en sommant les éléments de la ligne correspondant à $A$.

En effectuant le calcul, on trouve que la somme des éléments de la ligne correspondant à $A$ dans $M^4$ est égale à 40. Cela signifie qu'il existe 40 chaînes de longueur 4 issues de $A$.

Exercice 2 (4 points)

Une société doit transporter par camions six produits chimiques, notés $P_1$,...,$P_6$ depuis l'usine de production jusqu'à l'entreprise utilisatrice. Pour des raisons de sécurité, certains produits ne peuvent pas être transportés ensemble : $P_1$ et $P_2$, $P_1$ et $P_4$, $P_2$ et $P_3$, $P_2$ et $P_5$, $P_3$ et $P_4$, $P_5$ et $P_6$.

Déterminer le nombre minimum de camions nécessaires en expliquant la démarche suivie.

Corrigé

On peut modéliser ce problème à l'aide d'un graphe dont les sommets représentent les produits chimiques et dont les arêtes représentent les interdictions de transport ensemble.

Le graphe est le suivant :

Le nombre minimum de camions nécessaires correspond au nombre de couleurs nécessaires pour colorier ce graphe de manière à ce que deux sommets adjacents n'aient pas la même couleur (c'est-à-dire le nombre chromatique du graphe).

En coloriant le graphe, par exemple en utilisant l'algorithme de coloration de Welsh-Powell, on trouve que le nombre chromatique du graphe est égal à 2. Par conséquent, le nombre minimum de camions nécessaires pour transporter les produits chimiques est de 2.

Exercice 3 (4 points)

On considère un graphe orienté fini de matrice d’adjacence $M$.

On suppose qu'il existe un entier $k$ tel que :

\[M^k = 0\]

Montrer qu'alors le graphe ne contient aucun cycle.

Corrigé

S'il existe un entier $k$ tel que $M^k = 0$, alors pour tout entier $n \geq k$, on a $M^n = 0$.

Si le graphe admet un cycle de longueur $l$, alors le coefficient de la matrice $M^l_(i,i)>=1 (avec $i$ correspondant à un sommet du cycle).

De plus, le coefficient $M^lp_(i,i)>=1$ pour tout entier $p \geq 1$ (où $p$ correspond au nombre de fois que l'on parcourt le cycle).

Comme il existe un entier $p$ tel que $lp \geq k$, on aurait $M^lp_(i,i) >= 1$, ce qui contredit le fait que $M^k = 0$.

Par conséquent, un tel graphe ne peut pas contenir de cycle.

Sommet	Degré
A	2
B	2
C	4
D	3
E	2
F	4
G	2
H	3