Chargement de l'audio en cours

Plus

3. Application du calcul matriciel aux graphes

P.184-185

Mode édition

Ajouter

Terminer

COURS 3

3
Application du calcul matriciel aux graphes

Définition

Soit

n

un entier naturel non nul. On considère un graphe d’ordre

n

(orienté ou non) dont les sommets sont numérotés de

1

n

, puis rangés dans l’ordre croissant.
La matrice d’adjacence de ce graphe est la matrice carrée de taille

n

, dont le coefficient

a_{i, j}

est égal au nombre d’arêtes partant du sommet

i

pour arriver au sommet

j

Remarque

La matrice d’adjacence d’un graphe non orienté est symétrique.

Exemple

En notant

M

la matrice d’adjacence du graphe ci‑dessous obtenue en rangeant les sommets dans l’ordre alphabétique,
on a

M = ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ 0010101000011110010010010110110100101010001110100 ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞

Définition

Soient

n

k

deux entiers naturels non nuls et

M

la matrice d’adjacence d’un graphe d’ordre

n

, dont les sommets sont numérotés de

1

n

et rangés dans l’ordre croissant.
Le terme de la

i

-ème ligne et de la

j

-ième colonne de la matrice

M^{k}

donne le nombre de chaînes (ou de chemins) de longueur

k

reliant le sommet

i

au sommet

j

Remarque

M^{1} = M

donne le nombre de chaînes (ou de chemins) de longueur

1

reliant deux sommets.

DÉMONSTRATION

Voir exercice

p. 198.

Exemple

En reprenant l’exemple précédent, on a

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

.
Il existe donc 27 chaînes de longueur 4 reliant le sommet

C

au sommet

E

.
On a

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

donc il n’existe aucune chaîne de longueur 2 reliant le sommet

B

au sommet

F

Application et méthode - 5

Énoncé

On considère le graphe orienté ci‑contre.

1. Déterminer la matrice d’adjacence

M

de ce graphe en classant les sommets par ordre alphabétique.

2. a. Déterminer le nombre de chemins de longueur 3 reliant

A

C

.
b. Déterminer le nombre de chemins de longueur 3 reliant

C

B

Solution

1. On a

M = ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ 0010010001000111000000010 ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞

.
2. a. On a

M^{3} = ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ 1001010011101000001100100 ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞

.
Il y a donc une unique chaîne de longueur 3 reliant

A

C

. On constate qu’il n’y a pas de chemin de longueur 3 reliant

C

A

.
b. D’après la matrice

M^{3}

, il n’y a donc pas de chemin de longueur 3 reliant

C

B

Pour s'entraîner : exercices 38 et 39 p. 191

Méthode

1. On détermine la matrice d’adjacence

M

en prenant garde à l’orientation des arêtes.

2. ● On souhaite déterminer le nombre de chemins de longueur

3

: cela nécessite donc de connaître

M^{3}

.
● On repère ensuite le coefficient demandé dans cette matrice.

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.

3Application du calcul matriciel aux graphes

Remarque

Remarque

Application et méthode - 5

Énoncé

Solution

Méthode

3
Application du calcul matriciel aux graphes