Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
78
Flash
Déterminer la valeur des entiers a, b, c et d pour que la matrice \mathrm{M}=\left(\begin{array}{lllll}
0 & 1 & 1 & a & 0 \\
1 & 0 & 0 & b & 0 \\
1 & 0 & 0 & d & 1 \\
a & 1 & 2 & 0 & 1 \\
0 & c & 1 & 1 & 0
\end{array}\right) corresponde
à la matrice d'adjacence du graphe ci‑dessous en
classant les sommets dans l'ordre alphabétique.
Le zoom est accessible dans la version Premium.
Afficher la correction
Ressource affichée de l'autre côt é. Faites défiler pour voir la suite.
79
Flash
On considère un graphe dont la matrice d'adjacence \mathrm{M}=\left(\begin{array}{lll}
0 & 1 & 2 \\
1 & 0 & 2 \\
2 & 2 & 0
\end{array}\right) est obtenue en classant
les sommets dans l'ordre croissant.
1. Déterminer le nombre de chaînes de longueur 2 reliant les sommets 2 et 3.
2. Déterminer le nombre de chaînes de longueur 3 reliant les sommets 2 et 3.
Afficher la correction
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
80
[Calculer.]
On considère un graphe dont la matrice d'adjacence,
obtenue en rangeant les sommets dans l'ordre croissant,
est notée \text{M}.
On donne \mathrm{M}^{2}=\left(\begin{array}{cccc}
7 & 7 & 2 & 13 \\
13 & 13 & 4 & 16 \\
18 & 11 & 9 & 14 \\
3 & 2 & 2 & 2
\end{array}\right).
Déterminer le nombre de chemins de longueur 6 reliant le sommet 2 au sommet 3.
Afficher la correction
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
81
[Représenter.]
D'après bac ES, Métropole, juin 2018
Un parcours sportif est
composé d'un banc pour
abdominaux \text{(B)}, d'un
mur d'escalade \text{(M)}, d'une
poutre d'équilibre \text{(P)},
d'un tunnel \text{(T)} et d'une
échelle suspendue \text{(E)}. Le
graphe ci‑dessous indique
les différents parcours
envisageables.
Le zoom est accessible dans la version Premium.
1. Est‑il possible de suivre un parcours en passant par toutes les étapes ?
2. Déterminer la matrice d'adjacence \text{M} de ce graphe où les sommets sont classés dans l'ordre alphabétique.
3. Déterminer \mathrm{M}^{3} puis en déduire le nombre de chemins de longueur 3 reliant \text{B} à \text{E}.
4. Le responsable souhaite ajouter une barre de traction
notée \text{Z}. De nouveaux sentiers sont construits et de
nouveaux parcours sont alors possibles.
La matrice d'adjacence \text{N}, associée au graphe
représentant les nouveaux parcours, dans laquelle les
sommets sont classés par ordre alphabétique est :
Compléter le graphe précédent en ajoutant les arêtes
nécessaires pour que le graphe obtenu corresponde à
la matrice \text{N}.
Cette fonctionnalité est accessible dans la version Premium.
Afficher la correction
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
82
[Représenter.]
D'après bac ES, Amérique du Nord, juin 2017
Le graphe ci-dessous représente les principaux sites
touristiques de l'Islande.
Le zoom est accessible dans la version Premium.
\text{B} : Le lagon bleu
\text{H} : Rocher Hvitserkur
\text{M} : Lac de Mývatn
\text{D} : Chute d'eau de Dettifoss
\text{G} : Geyser de Geysir
\text{L} : Massif du Landmannalaugar
\text{R} : Capitale Reykjavik
\text{V} : Ville de Vik
\text{J} : Lagune glacière de Jökulsárlón
1. Quel est l'ordre de ce graphe ? Justifier.
2. Ce graphe est‑il complet ? Justifier.
3. Ce graphe est‑il connexe ? Justifier.
4. Déterminer la matrice d'adjacence de ce graphe (les sommets seront classés dans l'ordre alphabétique).
Afficher la correction
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
83
[Chercher.]
D'après bac ES, Asie, juin 2019
Une compagnie ferroviaire
a représenté à l'aide d'un
graphe les différentes liaisons
assurées par ses trains.
Les sommets du graphe sont
les initiales des gares desservies
et les arêtes correspondent
aux trajets effectués
par un train de cette compagnie
entre deux gares.
Par exemple, l'arête entre \text{A} et \text{G} signifie qu'un train effectue la liaison entre les gares \text{A} et \text{G}, en partant de \text{A} vers \text{G} ou en partant de \text{G} vers \text{A}.
Le zoom est accessible dans la version Premium.
1. Le graphe est‑il complet ? Interpréter ce résultat dans le cadre de l'exercice.
2. On note \text{M} la matrice d'adjacence du graphe ci‑dessus en classant les sommets par ordre alphabétique.
Déterminer \text{M}.
3. La compagnie souhaite qu'un train partant de la gare \text{F} effectue trois trajets avant d'arriver à la gare \text{B}.
Déterminer le nombre de trajets possibles.
Afficher la correction
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
84
Démo
[Raisonner.]
Soit \mathrm{M}=\left(a_{i, j}\right)=\left(\begin{array}{cccc}
a_{1,1} & a_{1,2} & \dots & a_{1, n} \\
a_{2,1} & \ddots & & \vdots \\
\vdots & & \ddots & \vdots \\
a_{n, 1} & \dots & \dots & a_{n, n}
\end{array}\right) la matrice
d'adjacence d'un graphe d'ordre n, dont les sommets
sont numérotés de 1 à n et soit k \in \mathrm{N}^{*}.
On souhaite démontrer par récurrence sur k que le
terme de la i-ième ligne et de la j-ième colonne de la
matrice \mathrm{M}^{k} correspond au nombre de chaînes de
longueur k reliant le sommet i au sommet j.
1. Vérifier que la propriété est vraie au rang k = 1.
2. Soit un entier p \geqslant 1 tel que le coefficient situé à la
i-ième ligne et à la j-ième colonne de \mathrm{M}^p corresponde au nombre de chaînes de longueur p reliant le sommet i au sommet j.
Notons \mathrm{M}^{p}=\left(b_{i, j}\right)=\left(\begin{array}{cccc}
b_{1,1} & b_{1,2} & \dots & b_{1, n} \\
b_{2,1} & \ddots & & \vdots \\
\vdots & & \ddots & \vdots \\
b_{n, 1} & \dots & \dots & b_{n, n}
\end{array}\right)
a. Pour tous entiers naturels i et j compris entre 1 et n, justifier que c_{i, j}=\mathop{\sum}\limits_{\ell=1}\limits^{n} b_{i, l} a_{\ell, j}.
b. Interpréter b_{i, \ell} et a_{\ell, j} en termes de nombre de
chaînes.
c. En déduire que c_{i, j} est le nombre de chaînes de longueur p + 1 reliant les sommets i et j.
3. Conclure.
Afficher la correction
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
85
[Représenter.] Les différentes salles d'un
château ont été nommées
\text{A}, \text{B}, \text{C}, \text{D}, \text{E}, \text{F}, \text{G}, \text{H} et \text{I}
afin de permettre aux visiteurs de se repérer sur le plan.
Le zoom est accessible dans la version Premium.
1. Le graphe ci-dessus donne les parcours possibles d'un visiteur dans ce château.
Déterminer la matrice d'adjacence \text{M} de ce graphe (les
sommets seront classés dans l'ordre alphabétique).
a. Combien y‑a‑t‑il de chaînes qui, en quatre étapes, partent de \text{E} et reviennent à \text{E} ?
b. Combien y‑a‑t‑il de chaînes qui, en quatre étapes, partent de \text{C} et arrivent à \text{I} ? Les citer.
c. Est‑il toujours possible de joindre en quatre étapes deux salles quelconques ? Justifier.
Afficher la correction
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
86
[Chercher.] D'après bac ES, Polynésie, juin 2018
Un journaliste britannique d'une revue consacrée à
l'automobile doit tester les autoroutes françaises.
Pour remplir sa mission, il décide de louer une voiture
et de circuler entre six grandes villes françaises : Bordeaux
\text{(B)}, Lyon \text{(L)}, Marseille \text{(M)}, Nantes \text{(N)}, Paris \text{(P)}
et Toulouse \text{(T)}.
Le réseau autoroutier
reliant ces six villes est
modélisé par le graphe
ci‑dessous sur lequel les
sommets représentent les
villes et les arêtes les
liaisons autoroutières
entre ces villes.
Le zoom est accessible dans la version Premium.
1. a. Quel est l'ordre du graphe ?
b. Le graphe est‑il complet ? Justifier la réponse.
b. Alors qu'il se trouve à Paris, le rédacteur en chef
demande au journaliste d'être à Marseille exactement
trois jours plus tard pour assister à une course
automobile. Le journaliste décide chaque jour de
s'arrêter dans une ville différente.
Déterminer le nombre de trajets possibles respectant
ces conditions.
Afficher la correction
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
87
[Chercher.]
On considère le graphe ci‑après.
Déterminer le nombre de chaînes de longueur 4 reliant \text{A} à \text{D}.
Le zoom est accessible dans la version Premium.
Afficher la correction
Une erreur sur la page ? Une idée à proposer ?
Nos manuels sont collaboratifs, n'hésitez pas à nous en faire part.
Oups, une coquille
j'ai une idée !
Nous préparons votre pageNous vous offrons 5 essais
Yolène
Émilie
Jean-Paul
Fatima
Sarah
Utilisation des cookies
Lors de votre navigation sur ce site, des cookies nécessaires au bon fonctionnement et exemptés de consentement sont déposés.