Chargement de l'audio en cours
Plus

Plus

3. Application du calcul matriciel aux graphes
P.197-199

Mode édition
Ajouter

Ajouter

Terminer

Terminer

Entraînement


3
Application du calcul matriciel aux graphes





DIFFÉRENCIATION

◉◉ Parcours 1 : exercices 44 ; 48 ; 51 ; 55 ; 71 ; 76 et 86
◉◉ Parcours 2 : exercices 47 ; 50 ; 54 ; 57 ; 75 ; 81 et 83
◉◉◉ Parcours 3 : exercices 53 ; 62 ; 63 ; 65 ; 73 et 84

78
FLASH

Déterminer la valeur des entiers aa, bb, cc et dd pour que la matrice M=(011a0100b0100d1a12010c110)\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.

Graphe - Exercice 78

Voir les réponses

79
FLASH

On considère un graphe dont la matrice d’adjacence M=(012102220)\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.
Voir les réponses

80
[Calculer.]
On considère un graphe dont la matrice d’adjacence, obtenue en rangeant les sommets dans l’ordre croissant, est notée M\text{M}.
On donne M2=(77213131341618119143222)\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.
Voir les réponses

81
[Représenter.] ◉◉
D’après bac ES, Métropole, juin 2018
Un parcours sportif est composé d’un banc pour abdominaux (B)\text{(B)}, d’un mur d’escalade (M)\text{(M)}, d’une poutre d’équilibre (P)\text{(P)}, d’un tunnel (T)\text{(T)} et d’une échelle suspendue (E)\text{(E)}. Le graphe ci‑dessous indique les différents parcours envisageables.

Graphe - Exercice 81

1. Est‑il possible de suivre un parcours en passant par toutes les étapes ?


2. Déterminer la matrice d’adjacence M\text{M} de ce graphe où les sommets sont classés dans l’ordre alphabétique.


3. Déterminer M3\mathrm{M}^{3} puis en déduire le nombre de chemins de longueur 3 reliant B\text{B} à E\text{E}.


4. Le responsable souhaite ajouter une barre de traction notée Z\text{Z}. De nouveaux sentiers sont construits et de nouveaux parcours sont alors possibles. La matrice d’adjacence N\text{N}, associée au graphe représentant les nouveaux parcours, dans laquelle les sommets sont classés par ordre alphabétique est :
N=(010101000011010110001000011000001110)\mathrm{N}=\left(\begin{array}{llllll} 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 \end{array}\right)

Compléter le graphe précédent en ajoutant les arêtes nécessaires pour que le graphe obtenu corresponde à la matrice N\text{N}.
Voir les réponses

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.

Graphe - Exercice 82

B\text{B} : Le lagon bleu
H\text{H} : Rocher Hvitserkur
M\text{M} : Lac de Mývatn
D\text{D} : Chute d’eau de Dettifoss
G\text{G} : Geyser de Geysir
L\text{L} : Massif du Landmannalaugar
R\text{R} : Capitale Reykjavik
V\text{V} : Ville de Vik
J\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).
Voir les réponses

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 A\text{A} et G\text{G} signifie qu’un train effectue la liaison entre les gares A\text{A} et G\text{G}, en partant de A\text{A} vers G\text{G} ou en partant de G\text{G} vers A\text{A}.

Graphe - Exercice 83

1. Le graphe est‑il complet ? Interpréter ce résultat dans le cadre de l’exercice.


2. On note M\text{M} la matrice d’adjacence du graphe ci‑dessus en classant les sommets par ordre alphabétique.
Déterminer M\text{M}.


3. La compagnie souhaite qu’un train partant de la gare F\text{F} effectue trois trajets avant d’arriver à la gare B\text{B}.
Déterminer le nombre de trajets possibles.
Voir les réponses

84
[Raisonner.] ◉◉◉
[DÉMO]

Soit M=(ai,j)=(a1,1a1,2a1,na2,1an,1an,n)\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 nn, dont les sommets sont numérotés de 11 à nn et soit kNk \in \mathrm{N}^{*}.
On souhaite démontrer par récurrence sur kk que le terme de la ii-ième ligne et de la jj-ième colonne de la matrice Mk\mathrm{M}^{k} correspond au nombre de chaînes de longueur kk reliant le sommet ii au sommet jj.

1. Vérifier que la propriété est vraie au rang k=1k = 1.


2. Soit un entier p1p \geqslant 1 tel que le coefficient situé à la ii-ième ligne et à la jj-ième colonne de Mp\mathrm{M}^p corresponde au nombre de chaînes de longueur pp reliant le sommet ii au sommet jj.
Notons Mp=(bi,j)=(b1,1b1,2b1,nb2,1bn,1bn,n)\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) et Mp+1=(ci,j)=(c1,1c1,2c1,nc2,1cn,1cn,n)\mathrm{M}^{p+1}=\left(c_{i, j}\right)=\left(\begin{array}{cccc} c_{1,1} & c_{1,2} & \dots & c_{1, n} \\ c_{2,1} & \ddots & & \vdots \\ \vdots & & \ddots & \vdots \\ c_{n, 1} & \dots & \dots & c_{n, n} \end{array}\right).

a. Pour tous entiers naturels ii et jj compris entre 11 et nn, justifier que ci,j==1nbi,la,jc_{i, j}=\mathop{\sum}\limits_{\ell=1}\limits^{n} b_{i, l} a_{\ell, j}.


b. Interpréter bi,b_{i, \ell} et a,ja_{\ell, j} en termes de nombre de chaînes.


c. En déduire que ci,jc_{i, j} est le nombre de chaînes de longueur p+1p + 1 reliant les sommets ii et jj.


3. Conclure.
Voir les réponses

85
[Représenter.]
Les différentes salles d’un château ont été nommées A\text{A}, B\text{B}, C\text{C}, D\text{D}, E\text{E}, F\text{F}, G\text{G}, H\text{H} et I\text{I} afin de permettre aux visiteurs de se repérer sur le plan.

Graphe - Exercice 85

1. Le graphe ci-dessus donne les parcours possibles d’un visiteur dans ce château.
Déterminer la matrice d’adjacence M\text{M} de ce graphe (les sommets seront classés dans l’ordre alphabétique).


2. On donne M4=(2036112051851231601938412116031714121119131911121920203792892091258111998961844122082061251211999617121211220126121218)\mathrm{M}^{4}=\left(\begin{array}{ccccccccc} 20 & 3 & 6 & 11 & 20 & 5 & 18 & 5 & 12 \\ 3 & 16 & 0 & 19 & 3 & 8 & 4 & 12 & 11 \\ 6 & 0 & 3 & 1 & 7 & 1 & 4 & 1 & 2 \\ 11 & 19 & 1 & 31 & 9 & 11 & 12 & 19 & 20 \\ 20 & 3 & 7 & 9 & 28 & 9 & 20 & 9 & 12 \\ 5 & 8 & 1 & 11 & 9 & 9 & 8 & 9 & 6 \\ 18 & 4 & 4 & 12 & 20 & 8 & 20 & 6 & 12 \\ 5 & 12 & 1 & 19 & 9 & 9 & 6 & 17 & 12 \\ 12 & 11 & 2 & 20 & 12 & 6 & 12 & 12 & 18 \end{array}\right).

a. Combien y‑a‑t‑il de chaînes qui, en quatre étapes, partent de E\text{E} et reviennent à E\text{E} ?


b. Combien y‑a‑t‑il de chaînes qui, en quatre étapes, partent de C\text{C} et arrivent à I\text{I} ? Les citer.


c. Est‑il toujours possible de joindre en quatre étapes deux salles quelconques ? Justifier.
Voir les réponses

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 (B)\text{(B)}, Lyon (L)\text{(L)}, Marseille (M)\text{(M)}, Nantes (N)\text{(N)}, Paris (P)\text{(P)} et Toulouse (T)\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.

Graphe - Exercice 86

1. a. Quel est l’ordre du graphe ?


b. Le graphe est‑il complet ? Justifier la réponse.


2. On nomme G\text{G} la matrice d’adjacence du graphe (les villes étant classées dans l’ordre alphabétique).
On donne G=(0011101111010111001011101111010)\mathrm{G}=\left(\begin{array}{cccccc} 0 & \dots & 0 & 1 & 1 & 1 \\ \dots & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & \dots & 0 & \dots & 1 \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & \dots & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 1 & 0 \end{array}\right) et G3=(101351011121312811131258255710115610711135101012121277128)\mathrm{G}^{3}=\left(\begin{array}{cccccc} 10 & 13 & 5 & 10 & 11 & 12 \\ 13 & 12 & 8 & 11 & 13 & 12 \\ 5 & 8 & 2 & 5 & 5 & 7 \\ 10 & 11 & 5 & 6 & 10 & 7 \\ 11 & 13 & 5 & 10 & 10 & 12 \\ 12 & 12 & 7 & 7 & 12 & 8 \end{array}\right).

a. Compléter la matrice d’adjacence G\text{G}.


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.
Voir les réponses

87
[Chercher.]
On considère le graphe ci‑dessous.
Déterminer le nombre de chaînes de longueur 4 reliant A\text{A} à D\text{D}.

Graphe - Exercice 87

Voir les réponses
Utilisation des cookies
En poursuivant votre navigation sans modifier vos paramètres, vous acceptez l'utilisation des cookies permettant le bon fonctionnement du service.
Pour plus d’informations, cliquez ici.