88

[Calculer, Modéliser.]
D’après bac ES, Polynésie, juin 2015
Un constructeur de planches de surf fabrique trois modèles. La conception de chaque modèle nécessite le passage par trois postes de travail.
Le tableau 1 indique le nombre d’heures nécessaires par modèle et par poste pour réaliser les planches et le tableau 2 indique le coût horaire par poste de travail.



1. Soient $\text{H}$ et $\text{C}$ les deux matrices suivantes :

a. Donner la matrice produit $\mathrm{P}=\mathrm{H}\times \mathrm{C}$.


b. Que représentent les coefficients de la matrice $\text{P}$ ?


2. Après une étude de marché, le fabricant souhaite que les prix de revient par modèle soient les suivants :

• modèle 1 : 500 € ;
• modèle 2 : 350 € ;
• modèle 3 : 650 €.

Il cherche à déterminer les nouveaux coûts horaires par poste, notés $a$, $b$ et $c$, permettant d’obtenir ces prix de revient.

a. Montrer que les réels $a$, $b$ et $c$ doivent être solutions du système $\mathrm{H}\times \left(\begin{array}{l}a\\ b\\ c\end{array}\right)=\left(\begin{array}{l}500\\ 350\\ 650\end{array}\right)$.


b. Déterminer les réels $a$, $b$ et $c$.

89

APPROFONDISSEMENT

[Modéliser, Représenter.]
D’après bac ES, Métropole, septembre 2016

Afin d’améliorer la qualité de ses services, un parc a réalisé une étude statistique pour relever la durée moyenne d’attente, en minute, à la billetterie en fonction de l’heure.
Cette mesure a eu lieu chaque heure de 9 h à 16 h. On obtient le relevé suivant.



Ainsi, à 10 h, il y avait 14 minutes d’attente.
On souhaite modéliser cette durée d’attente par une fonction qui, à l’heure, associe la durée d’attente en minute. Ainsi, il sera possible d’avoir une estimation de la durée d’attente.
On choisit de modéliser cette situation à l’aide de la fonction $f$ définie par $f(x)=a{x}^2+bx+c$, où $a$, $b$ et $c$ sont des réels avec $a\ne 0$ tels que les trois points $(9;9)$, $(11;20)$ et $(16;2)$ appartiennent à la représentation graphique de $f$.

1. Traduire les données de l’énoncé sous la forme d’un système de trois équations à trois inconnues $a$, $b$ et $c$.


2. Déterminer les trois réels $a$, $b$ et $c$.


3. En utilisant ce modèle, déterminer les plages horaires pour lesquelles l’attente peut être inférieure à dix minutes.

90

DEVOIR MAISON

[Calculer, Représenter.]
D’après bac S, Amérique du Nord, 2015
On donne les matrices $\mathrm{M}=\left(\begin{array}{ccc}1& 1& 1\\ 1& -1& 1\\ 4& 2& 1\end{array}\right)$ et $\mathrm{I}=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right)$

Partie A

1. Calculer la matrice ${\mathrm{M}}^2$.


On donne ${\mathrm{M}}^3=\left(\begin{array}{ccc}20& 10& 11\\ 12& 2& 9\\ 42& 20& 21\end{array}\right)$.

2. Vérifier que ${\mathrm{M}}^3={\mathrm{M}}^2+8\mathrm{M}+6\mathrm{I}$.


3. En déduire que $\text{M}$ est inversible et que :


Partie B

On cherche à déterminer trois nombres entiers $a$, $b$ et $c$ tels que la parabole d’équation $y=a{x}^2+bx+c$ passe par les points $\mathrm{A}(1;1)$, $\mathrm{B}(-1;-1)$ et $\mathrm{C}(2;5)$.

1. Démontrer que le problème revient à chercher trois entiers $a$, $b$ et $c$ tels que $\mathrm{M}\left(\begin{array}{l}a\\ b\\ c\end{array}\right)=\left(\begin{array}{c}1\\ -1\\ 5\end{array}\right)$.


2. Calculer les nombres $a$, $b$ et $c$ et vérifier que ces nombres sont des entiers.

91

[Calculer, Raisonner.]
Diagonalisation et puissance de matrices
On considère les matrices $\mathrm{A}=\left(\begin{array}{ll}1& 2\\ 3& 2\end{array}\right)$ et $\mathrm{P}=\left(\begin{array}{cc}1& 2\\ -1& 3\end{array}\right)$.

1. Justifier que $\text{P}$ est inversible et calculer son inverse.


2. Calculer le produit $\mathrm{D}={\mathrm{P}}^{-1}\times \mathrm{A}\times \mathrm{P}$.


3. En déduire que $\mathrm{A}=\mathrm{P}\times \mathrm{D}\times {\mathrm{P}}^{-1}$.


4. a. Pour tout entier naturel non nul $n$, conjecturer une expression de ${\mathrm{D}}^n$.


b. Démontrer cette conjecture par récurrence.


5. Exprimer alors ${\mathrm{A}}^n$ en fonction de $n$.

92

[Calculer, Raisonner.]
Diagonalisation et puissance de matrices
On considère les matrices $\mathrm{A}=\left(\begin{array}{ccc}0& 2& -1\\ 3& -2& 0\\ -2& 2& 1\end{array}\right)$ et $\mathrm{P}=\left(\begin{array}{ccc}1& 4& 2\\ 1& 3& -3\\ 1& -2& 2\end{array}\right)$.

1. Déterminer l’inverse de $\text{P}$.


2. Calculer le produit $\mathrm{D}={\mathrm{P}}^{-1}\times \mathrm{A}\times \mathrm{P}$.


3. En déduire que $\mathrm{A}=\mathrm{P}\times \mathrm{D}\times {\mathrm{P}}^{-1}$.


4. a. Pour tout entier naturel non nul $n$, conjecturer une expression de ${\mathrm{D}}^n$.


b. Démontrer cette conjecture par récurrence.


5. Exprimer alors ${\mathrm{A}}^n$ en fonction de $n$.

93

[Calculer, Raisonner.]
Soient $n$ un entier naturel supérieur ou égal à $2$ et $\text{A}$ la matrice carrée de taille $n$, formée de $0$ sur la diagonale et de $1$ partout ailleurs.

1. Calculer ${\mathrm{A}}^2$ et exprimer le résultat en fonction de $\text{A}$, de ${\mathrm{I}}_n$ et de $n$.


2. En déduire que $\text{A}$ est inversible et en déduire ${\mathrm{A}}^{-1}$.

94

[Calculer, Chercher.]
Matrices et changement de repère

Dans cet exercice, on munit le plan d’un repère orthonormé direct $(\mathrm{O};\overrightarrow{i},\overrightarrow{j})$.

Partie A : Changement de repère et translation

Soient $a$ et $b$ deux nombres réels.

1. Calculer l’image ${\mathrm{O}}^{\prime }$ de $\mathrm{O}$ par la translation de vecteur $\overrightarrow{t}=\left(\begin{array}{l}a\\ b\end{array}\right)$.


2. Déterminer l’image ${\mathrm{I}}^{\prime }$ du point $\mathrm{I}(1;0)$ par la translation de vecteur $\overrightarrow{t}$ , puis l’image ${\mathrm{J}}^{\prime }$ du point $\mathrm{J}(0;1)$ par cette même translation.


3. Démontrer que $\left({\mathrm{O}}^{\prime };\overrightarrow{{\mathrm{O}}^{\prime }{\mathrm{I}}^{\prime }},\overrightarrow{{\mathrm{O}}^{\prime }{\mathrm{J}}^{\prime }}\right)$ définit un repère orthonormé direct du plan.


4. On considère deux nombres réels $x$ et $y$ et le point $\text{M}$, dont les coordonnées dans le repère $(\mathrm{O};\overrightarrow{i},\overrightarrow{j})$ sont données par $\mathrm{M}(x;y)$.
Déterminer les coordonnées de $\text{M}$ dans le repère $\left({\mathrm{O}}^{\prime };\overrightarrow{{\mathrm{O}}^{\prime }{\mathrm{I}}^{\prime }},\overrightarrow{{\mathrm{O}}^{\prime }{\mathrm{J}}^{\prime }}\right)$.


5. Inversement, on considère deux nombres réels $x^{\prime }$ et $y^{\prime }$ et le point ${\mathrm{M}}^{\prime }$ dont les coordonnées dans le repère $\left({\mathrm{O}}^{\prime };\overrightarrow{{\mathrm{O}}^{\prime }{\mathrm{I}}^{\prime }},\overrightarrow{{\mathrm{O}}^{\prime }{\mathrm{J}}^{\prime }}\right)$ sont données par ${\mathrm{M}}^{\prime }\left(x^{\prime };y^{\prime }\right)$.
Déterminer les coordonnées de ${\mathrm{M}}^{\prime }$ dans le repère $(\mathrm{O};\overrightarrow{i},\overrightarrow{j})$.


Partie B : Changement de repère (cas général)

Dans cette partie, on considère quatre nombres réels $a$, $b$, $c$ et $d$. On note $\text{T}$ la matrice $\left(\begin{array}{ll}a& b\\ c& d\end{array}\right)$.

1. Calculer l’image ${\mathrm{O}}^{\prime }$ de $\mathrm{O}$ par cette transformation.


2. Calculer de même l’image ${\mathrm{I}}^{\prime }$ et ${\mathrm{J}}^{\prime }$ des points $\mathrm{I}(1;0)$ et $\mathrm{J}(0;1)$.


3. a. À quelle condition sur $a$, $b$, $c$ et $d$ le triplet $\left({\mathrm{O}}^{\prime };\overrightarrow{{\mathrm{O}}^{\prime }{\mathrm{I}}^{\prime }},\overrightarrow{{\mathrm{O}}^{\prime }{\mathrm{J}}^{\prime }}\right)$ définit‑il un repère du plan ?


b. Que signifie cette condition pour la matrice $\text{T}$ ?


4. On suppose dans la suite que la condition de la question 3. est vérifiée.
a. Soit $\text{M}$ un point du plan dont les coordonnées dans le repère $(\mathrm{O};\overrightarrow{i},\overrightarrow{j})$ sont $\mathrm{M}(x;y)$.
Calculer les coordonnées de $\mathrm{M}$ dans le repère $\left({\mathrm{O}}^{\prime };\overrightarrow{{\mathrm{O}\mathrm{T}}^{\prime }},\overrightarrow{{\mathrm{O}}^{\prime }{\mathrm{J}}^{\prime }}\right)$ en fonction de $x$ et de $y$.


b. Inversement, si on note $\left(x^{\prime };y^{\prime }\right)$ les coordonnées de $\text{M}$ dans le repère $\left({\mathrm{O}}^{\prime };\overrightarrow{{\mathrm{O}}^{\prime }{\mathrm{I}}^{\prime }},\overrightarrow{{\mathrm{O}}^{\prime }{\mathrm{J}}^{\prime }}\right)$, par quelle matrice doit‑on multiplier $\left(\begin{array}{l}{x}^{\prime }\\ y^{\prime }\end{array}\right)$ pour obtenir les coordonnées de $\mathrm{M}$ dans le repère $(\mathrm{O};\overrightarrow{i},\overrightarrow{j})$ ?

95

[Chercher, Raisonner.]
Racine carrée de matrice

Partie A : Étude de quelques exemples

1. Dans cette question, on note $\text{A}$ la matrice $\left(\begin{array}{ll}-26& 70\\ -21& 51\end{array}\right)$ et on considère la matrice $\mathrm{B}=\left(\begin{array}{cc}-2& 10\\ -3& 9\end{array}\right)$.
a. Montrer que ${\mathrm{B}}^2=\mathrm{A}$.
On dit que $\text{B}$ est une racine carrée de $\text{A}$.


b. Montrer que $\left(\begin{array}{ll}-38& 70\\ -21& 39\end{array}\right)$, $\left(\begin{array}{ll}38& -70\\ 21& -39\end{array}\right)$ et $\left(\begin{array}{ll}2& -10\\ 3& -9\end{array}\right)$ sont également des racines carrées de $\text{A}$.


2. Justifier que $\left(\begin{array}{cc}1& 0\\ 0& -1\end{array}\right)$ et $\left(\begin{array}{cc}2& -3\\ 1& -2\end{array}\right)$ sont des racines carrées de ${\mathrm{I}}_2$.


Partie B : Cas d’une matrice diagonale

Dans cette partie, on considère deux réels $x$ et $y$ positifs et distincts et on note $\mathrm{D}=\left(\begin{array}{ll}x& 0\\ 0& y\end{array}\right)$.

1. Montrer que $\left(\begin{array}{cc}\sqrt{x}& 0\\ 0& \sqrt{y}\end{array}\right)$ est une racine carrée de la matrice $\text{D}$.


2. On cherche à déterminer les autres racines carrées de $\text{D}$.
On suppose donc qu’il existe une matrice $\mathrm{R}=\left(\begin{array}{ll}a& b\\ c& d\end{array}\right)$ telle que ${\mathrm{R}}^2=\mathrm{D}$.

a. Montrer que déterminer $\text{R}$ revient à résoudre le système d’équations $\{\begin{array}{lcc}{a}^2+bc& =& x\\ b(a+d)& =& 0\\ c(a+d)& =& 0\\ cb+d^2& =& y\end{array}$.


b. On souhaite montrer que $b$ et $c$ sont nuls.
On raisonne par l’absurde en supposant que $b$ ou $c$ est non nul. Justifier qu’on a alors $a=-d$ puis aboutir à une contradiction.


c. Conclure sur l’expression des racines carrées de la matrice $\text{D}$.


d. Que se passe‑t‑il si on ne suppose pas les réels $x$ et $y$ distincts ? (On pourra considérer les matrices $\left(\begin{array}{cc}1& 2\\ 1& -1\end{array}\right)$ et $\left(\begin{array}{ll}3& 0\\ 0& 3\end{array}\right)$.)


Partie C : Cas d’une matrice diagonalisable

Soient $\text{C}$ une matrice d’ordre $n$ admettant une racine carrée $\text{R}$ et $\text{P}$ une matrice carrée d’ordre $n$ inversible.

1. Montrer que ${\mathrm{P}\mathrm{R}\mathrm{P}}^{-1}$ est une racine carrée de la matrice ${\mathrm{P}\mathrm{C}\mathrm{P}}^{-1}$.


2. On note dans la suite la matrice $\mathrm{C}=\left(\begin{array}{cc}-21& 50\\ -15& 34\end{array}\right)$.

a. Soit $\text{P}$ la matrice $\left(\begin{array}{ll}2& 5\\ 1& 3\end{array}\right)$.
Justifier que $\text{P}$ est inversible et calculer ${\mathrm{P}}^{-1}$.


b. Montrer que $\mathrm{C}=\mathrm{P}\left(\begin{array}{ll}4& 0\\ 0& 9\end{array}\right){\mathrm{P}}^{-1}$.


c. Déterminer les racines carrées de la matrice $\left(\begin{array}{ll}4& 0\\ 0& 9\end{array}\right)$.


d. En déduire les racines carrées de la matrice $\text{C}$.

96

[Chercher, Modéliser.]
D’après bac S, Centres étrangers, 2017

L’arbre de Stern-Brocot a été découvert séparément par le mathématicien allemand Moritz Abraham Stern (1858) et par Achille Brocot (1861), horloger français qui l’a utilisé pour concevoir des systèmes d’engrenages avec un rapport entre rouages proche d’une valeur souhaitée.
Cet exercice aborde la méthode avec des matrices carrées.
On considère les deux matrices $\mathrm{G}=\left(\begin{array}{ll}1& 0\\ 1& 1\end{array}\right)$ et $\mathrm{D}=\left(\begin{array}{ll}1& 1\\ 0& 1\end{array}\right).$


On construit à partir d’une matrice initiale un arbre descendant de la façon suivante : de chaque matrice carrée $\text{M}$ de l’arbre partent deux nouvelles branches vers les deux autres matrices $\mathrm{M}\times \mathrm{G}$ (à gauche) et $\mathrm{M}\times \mathrm{D}$ (à droite). Ces deux nouvelles matrices sont appelées les matrices filles de $\text{M}$.
Dans la méthode considérée, on prend comme matrice initiale la matrice $\mathrm{I}=\left(\begin{array}{ll}1& 0\\ 0& 1\end{array}\right)$.

1. Déterminer les deux matrices manquantes $\text{A}$ et $\text{B}$ dans la troisième ligne de l’arbre de Stern‑Brocot ci‑dessous.



Dans la suite de l’exercice, on admet que, pour toute matrice $\mathrm{M}=\left(\begin{array}{ll}a& c\\ b& d\end{array}\right)$, de l’arbre de Stern‑Brocot, les nombres $a$, $b$, $c$ et $d$ sont des entiers vérifiant : $b+d\ne 0$.

2. On associe à une matrice $\mathrm{M}=\left(\begin{array}{ll}a& c\\ b& d\end{array}\right)$ de l’arbre de Stern‑Brocot la fraction $\frac{a+c}{b+d}$. Montrer que, dans cette association, le trajet « gauche - droite - gauche », à partir de la matrice initiale dans l’arbre, aboutit à une matrice correspondant à la fraction $\frac{3}{5}$.


3. Soit $\mathrm{M}=\left(\begin{array}{ll}a& c\\ b& d\end{array}\right)$ une matrice de l’arbre.
On rappelle que $a$, $b$, $c$ et $d$ sont des entiers.
On note ${\Delta }_{\mathrm{M}}=ad-bc$, la différence des produits diagonaux de cette matrice.

a. Montrer que si $ad-bc=1$, alors $d(a+c)-c(b+d)=1$.


b. En déduire que si $\mathrm{M}=\left(\begin{array}{ll}a& c\\ b& d\end{array}\right)$ est une matrice de l’arbre de Stern-Brocot telle que ${\Delta }_{\mathrm{M}}=ad-bc=1$, alors ${\Delta }_{\mathrm{M}\times \mathrm{G}}=1$, c’est‑à‑dire que la différence des produits diagonaux de la matrice $\mathrm{M}\times \mathrm{G}$ est aussi égale à $1$.
On admet de même que ${\Delta }_{\mathrm{M}\times \mathrm{D}}=1$, et que toutes les autres matrices $\text{N}$ de l’arbre de Stern-Brocot vérifient l’égalité ${\Delta }_{\mathrm{N}}=1$.


4. Déduire de la question précédente que toute fraction associée à une matrice de l’arbre de Stern‑Brocot est irréductible.


5. Soit $m$ et $n$ deux entiers naturels non nuls premiers entre eux. Ainsi, la fraction $\frac{m}{n}$ est irréductible. On considère l’algorithme suivant.



a. Recopier et compléter le tableau suivant.
Indiquer ce qu’affiche l’algorithme lorsqu’on le fait fonctionner avec les valeurs $m=4$ et $n=7$.



b. Conjecturer le rôle de cet algorithme. Vérifier à l’aide d’un calcul matriciel le résultat obtenu avec les valeurs $m=4$ et $n=7$.

97

[Chercher, Calculer.]
Partie A : Permutations d’un ensemble à trois éléments

Soit $\text{E}$ l’ensemble $\{1;2;3\}$. On s’intéresse dans cet exercice aux permutations de l’ensemble $\text{E}$.

1. $\left(\begin{array}{lll}1& 2& 3\\ 3& 1& 2\end{array}\right)$ est la permutation définie par $1\mapsto 3$, $2\mapsto 1$ et $3\mapsto 2$.
Déterminer les 5 autres permutations de l’ensemble $\text{E}$.


2. La signature d’une permutation $\sigma$ est le nombre, noté $\epsilon (\sigma )$, défini par : Calculer la signature de chacune des permutations précédentes.


Partie B : Déterminant d’une matrice $3\times 3$

Considérons la matrice $\mathrm{M}=\left(\begin{array}{lll}a& b& c\\ d& e& f\\ g& h& i\end{array}\right)$.
Le déterminant de la matrice $\text{M}$, noté $\det (\mathrm{M})$ ou encore $\left|\begin{array}{lll}a& b& c\\ d& e& f\\ g& h& i\end{array}\right|$ , est le nombre défini par :

où ${\sigma }_1,\dots ,{\sigma }_6$ désignent les permutations de la Partie A.

1. a. Montrer que :



b. Calculer le déterminant des matrices $\mathrm{A}=\left(\begin{array}{ccc}5& -3& -6\\ 2& -4& 7\\ 0& 0& 8\end{array}\right)$ et $\mathrm{B}=\left(\begin{array}{lll}1& 5& 3\\ 2& 4& 7\\ 4& 6& 2\end{array}\right)$.


c. Soient $x$, $y$ et $z$ des nombres réels.
Montrer que $\left|\begin{array}{lll}1& x& x^2\\ 1& y& y^2\\ 1& z& z^2\end{array}\right|=(z-y)(z-x)(y-x)$.


2. a. Vérifier que :

où $\left|\begin{array}{ll}e& f\\ h& i\end{array}\right|$ désigne le déterminant de $\left(\begin{array}{ll}e& f\\ h& i\end{array}\right)$.


b. Montrer que $\left|\begin{array}{lll}a& b& c\\ 0& d& e\\ 0& 0& f\end{array}\right|=a\times d\times f$.

98

[Modéliser, Calculer.]
Soit $f$ une fonction définie, pour tout réel $x$, par $f(x)=a{x}^3+b{x}^2+cx+d$, où $a$, $b$, $c$ et $d$ désignent des nombres réels avec $a\ne 0$. On a représenté ci‑dessous la courbe représentative ${\mathcal{C}}_f$ de la fonction $f$ dans un repère $(\mathrm{O};\overrightarrow{i},\overrightarrow{j})$.


Les points $\mathrm{A}(-5;6)$, $\mathrm{B}(-1;3)$, $\mathrm{C}(2;4)$ et $\mathrm{D}(5;-2)$ appartiennent à ${\mathcal{C}}_f$.

1. Traduire les données de l’énoncé sous la forme d’un système $\text{(S)}$ de quatre équations à quatre inconnues $a$, $b$, $c$ et $d$.


2. Déterminer les matrices $\text{M}$, $\text{X}$ et $\text{P}$ telles que le système $\text{(S)}$ s’écrit sous la forme $\mathrm{M}\times \mathrm{X}=\mathrm{P}$.


3. On admet que la matrice $\text{M}$ est inversible.
À l’aide de la calculatrice, déterminer ${\mathrm{M}}^{-1}$.


4. En déduire les réels $a$, $b$, $c$ et $d$ solutions du système $\text{(S)}$.

99

APPROFONDISSEMENT

Dans tout l’exercice, on suppose que les graphes sont connexes et non orientés.

Partie A : Cas d’une chaîne eulérienne

Une chaîne eulérienne est une chaîne qui passe par toutes les arêtes du graphe une et une seule fois.
Le théorème d’Euler affirme qu’une telle chaîne existe si, et seulement si, tous les sommets du graphe sont de degré pair sauf éventuellement deux. Dans ce cas, les extrémités de la chaîne sont ces sommets.
On souhaite démontrer la condition nécessaire de ce théorème. Supposons que le graphe admette une chaîne eulérienne.

1. Expliquer pourquoi tous les sommets sont d’ordre pair, sauf éventuellement le premier et le dernier de la chaîne.


2. On se place dans le cas où les extrémités sont confondues. Considérons un sommet $\text{S}$ par lequel la chaîne est passée $k$ fois $(k\in \mathbb{N})$. Quel est le degré de $\text{S}$ ?


3. On se place à présent dans le cas où les extrémités ne sont pas confondues. Quel est le degré d’une extrémité par lequel la chaîne est passée $k$ fois $(k\in \mathbb{N})$ ?


4. Conclure.


Partie B : Cas d’un cycle eulérien

Un cycle est une chaîne dont les sommets de départ et d’arrivée sont confondus.
Un cycle eulérien est un cycle qui passe par toutes les arêtes du graphe une et une seule fois.
Le théorème d’Euler affirme qu’un tel cycle existe si, et seulement si, tous les sommets du graphe sont de degré pair. On dit alors que le graphe est eulérien.

Démontrer ce théorème.


Partie C : Algorithme de détermination d’un cycle ou d’une chaîne eulérienne

Pour construire une chaîne eulérienne, on utilise l’algorithme suivant.

Déterminer si chacun des graphes ci-dessous admet un cycle eulérien et le déterminer.

a.


b.


c.


d.


Partie D : Application

Dans un plan de lutte contre la pollution urbaine, une municipalité a décidé de développer un réseau de navettes, mis en place entre des parkings situés aux abords de la ville et les principaux sites de la ville.
Le graphe ci‑dessous indique les liaisons entre ces différents sites.

1. Peut‑on envisager un itinéraire qui relierait le parking $\text{P}$ à la gare $\text{G}$ en desservant une et une seule fois tous les sites ?


2. Peut‑on envisager un itinéraire qui emprunterait une et une seule fois toutes les voies ?

100

COLORATION DE GRAPHE

Partie A : Étude du problème

Colorier un graphe, c’est affecter une couleur à chaque sommet, de sorte que deux sommets adjacents ne portent pas la même couleur.
Le nombre chromatique, noté $\gamma$, est le plus petit nombre de couleurs nécessaires pour colorier un graphe.
Considérons un graphe $\mathcal{G}$.
Un sous‑graphe de $\mathcal{G}$ est un graphe ${\mathcal{G}}^{\prime }$ composé de certains sommets de $\mathcal{G}$ et de toutes les arêtes reliant ces sommets.
Notons $m$ l’ordre du plus grand des sous-graphes complets de $\mathcal{G}$ et $\Delta$ le plus grand degré des sommets de $\mathcal{G}$. Alors $m⩽\gamma ⩽\Delta +1$.
Prouver cette inégalité.


Partie B : Algorithme de Welsh-Powell

Pour colorier un graphe, on utilise l’algorithme suivant.

• Étape 1 : Lister les sommets par ordre de degré décroissant.
• Étape 2 : Attribuer une couleur ${\text{C}}_1$ au premier sommet de la liste.
• Étape 3 : Attribuer cette même couleur à tous les sommets qui ne sont pas adjacents avec le premier sommet de la liste et qui ne sont pas adjacents entre eux.
• Étape 4 : Répéter les étapes 2 et 3 tant que tous les sommets ne sont pas coloriés. Répéter les étapes 2 et 3 tant que tous les sommets ne sont pas coloriés.

Colorier le graphe ci‑dessous à l’aide de cet algorithme.


Partie C : Application

Camille est éducatrice de chiens : elle donne des leçons de dressage le samedi après‑midi.
Neuf chiots sont présents : Aéro, Banjo, Carrousel, Dirka, Erald, Farore, Gipsy, Hyacinthe et Igor.
Camille souhaite réaliser des exercices d’apprentissage par petits groupes de deux ou trois chiens.
Farore ne pense qu’à jouer si elle est trop proche de Banjo, Carousel ou Erald.
De même, Dirka est très distraite si Banjo ou Farore sont à proximité !
Igor ne supporte pas le caractère trop fougueux de Gipsy.
Enfin, le turbulent Aéro ne supporte la présence d’aucun autre chiot, sauf Erald et Hyacinthe.

1. Représenter cette situation à l’aide d’un graphe $\mathcal{G}$, dont les sommets sont les noms des chiots et relier entre eux les chiots que l’on ne peut pas mettre ensemble pour ce travail de groupe.


2. Le graphe $\mathcal{G}$ est‑il connexe ? Justifier.


3. a. Déterminer un sous‑graphe complet d’ordre maximal du graphe $\mathcal{G}$.


b. Que peut‑on en déduire pour le nombre chromatique du graphe $\mathcal{G}$ ?


4. Donner la valeur du nombre chromatique du graphe $\mathcal{G}$.


5. Peut‑on proposer une répartition des chiots en groupes de deux à trois chiots pouvant travailler ensemble ?