Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
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.
Tableau 1
Poste 1
Poste 2
Poste 3
Modèle 1
8 h
10 h
14 h
Modèle 2
6 h
6 h
10 h
Modèle 3
12 h
10 h
18 h
Tableau 2
Poste 1
25 €/h
Poste 2
20 €/h
Poste 3
15 €/h
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.
Histoire des maths
Le terme de matrice pour désigner un tableau de
nombres est introduit par James Sylvester en 1850.
Il est repris par Arthur Cayley qui en donne une
première théorie, mais dans le cadre de problèmes
géométriques très spécifiques. Il faudra attendre les
années 1920‑1930 pour qu'elle devienne une théorie
intégratrice et l'un des fondements de ce qu'on appelle
aujourd'hui l'algèbre linéaire.
Afficher la correction
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
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.
Le zoom est accessible dans la version Premium.
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}+b x+c, où a, b et c sont des réels avec a \neq 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.
Afficher la correction
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
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 :
On cherche à déterminer trois nombres entiers a, b et
c tels que la parabole d'équation y=a x^{2}+b x+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.
Histoire des maths
La méthode dite « du pivot de Gauss » ou
« élimination de Gauss‑Jordan » pour des systèmes
d'équations linéaires était d'usage courant bien
avant ces deux mathématiciens du XIXe siècle. Mais
Gauss en fera une méthode puissante utile aux
calculs astronomiques et géodésiques. C'est avec le
développement du calcul matriciel (milieu XXe siècle),
qu'on attribuera à Gauss cette méthode d'inversion
d'une matrice.
Afficher la correction
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
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.
Afficher la correction
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
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.
Afficher la correction
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
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}.
Afficher la correction
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
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{OT}^{\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}) ?
Afficher la correction
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
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 \left\{\begin{array}{l}
a^{2}+b c & = & x \\
b(a+d) & = & 0 \\
c(a+d) & = & 0 \\
c b+d^{2} & = & y
\end{array}\right..
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{PRP}^{-1} est une racine carrée de la matrice \mathrm{PCP}^{-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}.
Afficher la correction
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
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).
Le zoom est accessible dans la version Premium.
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.
Le zoom est accessible dans la version Premium.
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 \neq 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}}=a d-b c, la différence des produits
diagonaux de cette matrice.
a. Montrer que si a d-b c=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}}=a d-b c=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.
\boxed{\begin{array}{l}
\text { Tant que }(m \neq n) \text { faire : } \\
\quad \text { Si }(m\lt n): \\
\quad \quad \quad \text {Afficher } « \text { Gauche } » \\
\quad \quad \quad n \leftarrow n-m \\
\quad \text { Sinon : } \\
\quad \quad \quad \text {Afficher } « \text { Droite } » \\
\quad\quad\quad m \leftarrow m-n \\
\quad\text { Fin Si } \\
\text { Fin Tant que }
\end{array}}
a. Compléter le tableau suivant.
Indiquer ce qu'affiche l'algorithme lorsqu'on le fait
fonctionner avec les valeurs m = 4 et n = 7.
Affichage
\boldsymbol{m}
4
\boldsymbol{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.
Afficher la correction
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
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é \varepsilon(\sigma), défini par :
Calculer la signature de chacune des permutations
précédentes.
Partie B : Déterminant d'une matrice \mathbf{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é \operatorname{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 :
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 :
\operatorname{det}(\mathrm{M})=a \times\left|\begin{array}{ll}
e & f \\
h & i
\end{array}\right|-b \times\left|\begin{array}{ll}
d & f \\
g & i
\end{array}\right|+c \times\left|\begin{array}{ll}
d & e \\
g & h
\end{array}\right|
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.
Afficher la correction
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
98
[Modéliser, Calculer.]
Soit f une fonction définie, pour tout réel x, par
f(x)=a x^{3}+b x^{2}+c x+d, où a, b, c et d désignent des
nombres réels avec a \neq 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}).
Le zoom est accessible dans la version Premium.
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)}.
Afficher la correction
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
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.
Si il y a exactement deux sommets de degré impair
Alors on construit une chaîne quelconque joignant ces deux sommets
Sinon on construit un cycle à partir de n'importe quel sommet
Fin Si Tant que toutes les arêtes n'ont pas été parcourues
Si toutes les arêtes ont été parcourues
Alors la chaîne (respectivement le cycle) est eulérienne(respectivement eulérien)
Sinon on insère dans cette chaîne (respectivement ce cycle) un cycle ayant pour origine l'un des sommets déjà utilisés et ne contenant pas d'arête déjà parcourue ni deux fois la même arête
Fin Si
Fin Tant que
Déterminer si chacun des graphes ci-dessous admet un
cycle eulérien et le déterminer.
a.
Le zoom est accessible dans la version Premium.
b.
Le zoom est accessible dans la version Premium.
c.
Le zoom est accessible dans la version Premium.
d.
Le zoom est accessible dans la version Premium.
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 suivant indique les liaisons entre ces différents sites.
Le zoom est accessible dans la version Premium.
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 ?
Afficher la correction
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
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 \leqslant \gamma \leqslant \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.
Cette fonctionnalité est accessible dans la version Premium.
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.
Cliquez pour accéder à une zone de dessin
Cette fonctionnalité est accessible dans la version Premium.
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 ?
Afficher la correction
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
Les matrices ont des applications en cryptographie, en
théorie des graphes mais aussi en géométrie.
Il existe également des liens entre les matrices et les
représentations paramétriques de droites, vues en
enseignement de spécialité mathématiques.
1. Soit (d) une droite de l'espace dirigée par le vecteur
\overrightarrow{u}(a\,; b\,; c), avec a, b et c des réels, et passant par
le point \mathrm{A}\left(x_{\mathrm{A}}\,; y_{\mathrm{A}}\,; z_{\mathrm{A}}\right). Donner une représentation
paramétrique de cette droite, puis justifier qu'on peut
écrire cette représentation paramétrique sous la forme
\left(\begin{array}{l}
x \\
y \\
z
\end{array}\right)=\mathrm{A} t+\left(\begin{array}{l}
x_{A} \\
y_{A} \\
z_{A}
\end{array}\right), où t est un nombre réel et \mathrm{A} est une
matrice colonne à déterminer.
2. On se place maintenant dans le plan et on s'intéresse
à la représentation paramétrique d'une droite de
vecteur directeur \overrightarrow{u}(a\,; b) et passant par l'origine du
repère.
Rappeler quelle transformation du plan représente la
matrice \left(\begin{array}{cc}
0 & -1 \\
1 & 0
\end{array}\right), puis calculer \left(\begin{array}{cc}
0 & -1 \\
1 & 0
\end{array}\right)\left(\begin{array}{l}
a \\
b
\end{array}\right).
Quel résultat du cours d'enseignement de spécialité
mathématiques retrouve‑t‑on ?