Mathématiques Expertes Terminale

Rejoignez la communauté !

Co-construisez les ressources dont vous avez besoin et partagez votre expertise pédagogique.

Nombres complexes

Ch. 1

Nombres complexes, point de vue algébrique

Ch. 2

Nombres complexes, point de vue géométrique

Arithmétique

Ch. 3

Divisibilité dans Z

Ch. 4

PGCD et applications

Ch. 5

Nombres premiers

Graphes et matrices

Ch. 6

Calcul matriciel et applications aux graphes

Ch. 7

Suites et matrices

Annexes

Exercices transversaux

Exercicesp. 238-243

Se préparer au Grand Oral

Grand oral

Présentation du Grand Oral

Grand oral

Conseils pour le Grand Oral

Méthode

Cahier d'algorithmique et de programmation

Chapitre 6

Entraînement 3

Application du calcul matriciel aux graphes

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Différenciation

Parcours 1 : exercices

;

Parcours 2 : exercices

;

Parcours 3 : exercices

;

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Flash

Déterminer la valeur des entiers

a

b

c

d

pour que la matrice

M = ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ 011 a 0 1001 c 10021 a b d 01 00110 ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞

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.

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Flash

On considère un graphe dont la matrice d'adjacence

M = ⎝ ⎛ 012102220 ⎠ ⎞

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.

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

M

.
On donne

M^{2} = ⎝ ⎜ ⎜ ⎜ ⎛ 71318371311224921316142 ⎠ ⎟ ⎟ ⎟ ⎞

.

Déterminer le nombre de chemins de longueur 6 reliant le sommet 2 au sommet 3.

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

[Représenter.]

D'après bac ES, Métropole, juin 2018
Un parcours sportif est composé d'un banc pour abdominaux

(B)

, d'un mur d'escalade

(M)

, d'une poutre d'équilibre

(P)

, d'un tunnel

(T)

et d'une échelle suspendue

(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

M

de ce graphe où les sommets sont classés dans l'ordre alphabétique.

3. Déterminer

M^{3}

puis en déduire le nombre de chemins de longueur 3 reliant

B

E

4. Le responsable souhaite ajouter une barre de traction notée

Z

. De nouveaux sentiers sont construits et de nouveaux parcours sont alors possibles. La matrice d'adjacence

N

, associée au graphe représentant les nouveaux parcours, dans laquelle les sommets sont classés par ordre alphabétique est :

N = ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ 000000101010000111101001011001110000 ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞

Compléter le graphe précédent en ajoutant les arêtes nécessaires pour que le graphe obtenu corresponde à la matrice

N

Cette fonctionnalité est accessible dans la version Premium.

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.

B

: Le lagon bleu

H

: Rocher Hvitserkur

M

: Lac de Mývatn

D

: Chute d'eau de Dettifoss

G

: Geyser de Geysir

L

: Massif du Landmannalaugar

R

: Capitale Reykjavik

V

: Ville de Vik

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).

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

[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

G

signifie qu'un train effectue la liaison entre les gares

A

G

, en partant de

A

vers

G

ou en partant de

G

vers

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

M

la matrice d'adjacence du graphe ci‑dessus en classant les sommets par ordre alphabétique.
Déterminer

M

3. La compagnie souhaite qu'un train partant de la gare

F

effectue trois trajets avant d'arriver à la gare

B

.
Déterminer le nombre de trajets possibles.

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Démo

[Raisonner.]
Soit

M = (a_{i, j}) = ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ a_{1, 1} a_{2, 1} ⋮ a_{n, 1} a_{1, 2} ⋱ \dots \dots ⋱ \dots a_{1, n} ⋮ ⋮ a_{n, n} ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞

la matrice d'adjacence d'un graphe d'ordre

n

, dont les sommets sont numérotés de

1

n

et soit

k \in 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

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 ⩾ 1

tel que le coefficient situé à la

i

-ième ligne et à la

j

-ième colonne de

M^{p}

corresponde au nombre de chaînes de longueur

p

reliant le sommet

i

au sommet

j

.
Notons

M^{p} = (b_{i, j}) = ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ b_{1, 1} b_{2, 1} ⋮ b_{n, 1} b_{1, 2} ⋱ \dots \dots ⋱ \dots b_{1, n} ⋮ ⋮ b_{n, n} ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞

M^{p + 1} = (c_{i, j}) = ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ c_{1, 1} c_{2, 1} ⋮ c_{n, 1} c_{1, 2} ⋱ \dots \dots ⋱ \dots c_{1, n} ⋮ ⋮ c_{n, n} ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞

a. Pour tous entiers naturels

i

j

compris entre

1

n

, justifier que

c_{i, j} = ℓ = 1 \sum n b_{i, l} a_{ℓ, j}

b. Interpréter

b_{i, ℓ}

a_{ℓ, 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

j

3. Conclure.

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

A

B

C

D

E

F

G

H

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

M

de ce graphe (les sommets seront classés dans l'ordre alphabétique).

2. On donne

M^{4} = ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ 2036112051851231601938412116031714121119131911121920203792892091258111998961844122082061251211999617121211220126121218 ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞

a. Combien y‑a‑t‑il de chaînes qui, en quatre étapes, partent de

E

et reviennent à

E

b. Combien y‑a‑t‑il de chaînes qui, en quatre étapes, partent de

C

et arrivent à

I

? Les citer.

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

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

[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)

, Lyon

(L)

, Marseille

(M)

, Nantes

(N)

, Paris

(P)

et Toulouse

(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.

2. On nomme

G

la matrice d'adjacence du graphe (les villes étant classées dans l'ordre alphabétique).
On donne

G = ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ 0 \dots 0111 \dots 01111 01 \dots 0 \dots 1 110010 11 \dots 101 111010 ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞

G^{3} = ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ 101351011121312811131258255710115610711135101012121277128 ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞

.

a. Compléter la matrice d'adjacence

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.

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

A

D

Le zoom est accessible dans la version Premium.

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.

Application du calcul matriciel aux graphes

Une erreur sur la page ? Une idée à proposer ?

Nous préparons votre pageNous vous offrons 5 essais

Les manuels scolaires

La communauté

Aide et utilisation

À propos