Chargement de l'audio en cours
Plus

Plus

3. Application du calcul matriciel aux graphes
P.184-185
Mode édition
Ajouter

Ajouter

Terminer

Terminer

COURS 3


3
Application du calcul matriciel aux graphes





Définition
Soit nn un entier naturel non nul. On considère un graphe d’ordre nn (orienté ou non) dont les sommets sont numérotés de 11 à nn, puis rangés dans l’ordre croissant.
La matrice d’adjacence de ce graphe est la matrice carrée de taille nn, dont le coefficient ai,ja_{i, j} est égal au nombre d’arêtes partant du sommet ii pour arriver au sommet jj.

Remarque

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

Exemple


En notant M\text{M} la matrice d’adjacence du graphe ci‑dessous obtenue en rangeant les sommets dans l’ordre alphabétique,
on a M=(0010101000011110010010010110110100101010001110100)\mathrm{M}=\left(\begin{array}{ccccccc} 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 & 0 & 0 \end{array}\right).
Graphe

Définition
Soient nn et kk deux entiers naturels non nuls et M\text{M} la matrice d’adjacence d’un graphe d’ordre nn, dont les sommets sont numérotés de 11 à nn et rangés dans l’ordre croissant.
Le terme de la ii-ème ligne et de la jj-ième colonne de la matrice Mk\mathrm{M}^{k} donne le nombre de chaînes (ou de chemins) de longueur kk reliant le sommet ii au sommet jj.

Remarque

M1=M\mathrm{M}^{1}=\mathrm{M} donne le nombre de chaînes (ou de chemins) de longueur 11 reliant deux sommets.

DÉMONSTRATION

Voir exercice
84
p. 198.

Exemple

En reprenant l’exemple précédent, on a M4=(23201320165232020121814418131222 6 2712172018621822016142783517245412217101123181720241131)\mathrm{M}^{4}=\left(\begin{array}{ccccccc} 23 & 20 & 13 & 20 & \colorbox{#fde2c4}{16} & 5 & 23 \\ 20 & 20 & 12 & 18 & \colorbox{#fde2c4}{14} & 4 & 18 \\ \colorbox{#fde2c4}{13} & \colorbox{#fde2c4}{12} & \colorbox{#fde2c4}{22} & \colorbox{#fde2c4}{ 6 } & \boldsymbol{\colorbox{#f7cc91}{\color{white}27}} & 12 & 17 \\ 20 & 18 & 6 & 21 & 8 & 2 & 20 \\ 16 & 14 & 27 & 8 & 35 & 17 & 24 \\ 5 & 4 & 12 & 2 & 17 & 10 & 11 \\ 23 & 18 & 17 & 20 & 24 & 11 & 31 \end{array}\right).
Il existe donc 27 chaînes de longueur 4 reliant le sommet C\text{C} au sommet E\text{E}.
On a M2=(3212102231210111303112203002113042200102212112214)\mathrm{M}^{2}=\left(\begin{array}{ccccccc} 3 & 2 & 1 & 2 & 1 &\colorbox{#fde2c4}{0} & 2 \\ \colorbox{#fde2c4}{2} & \colorbox{#fde2c4}{3} & \colorbox{#fde2c4}{1} & \colorbox{#fde2c4}{2} & \colorbox{#fde2c4}{1} & \boldsymbol{\colorbox{#f7cc91}{\color{white}0}} & 1 \\ 1 & 1 & 3 & 0 & 3 & 1 & 1 \\ 2 & 2 & 0 & 3 & 0 & 0 & 2 \\ 1 & 1 & 3 & 0 & 4 & 2 & 2 \\ 0 & 0 & 1 & 0 & 2 & 2 & 1 \\ 2 & 1 & 1 & 2 & 2 & 1 & 4 \end{array}\right) donc il n’existe aucune chaîne de longueur 2 reliant le sommet B\text{B} au sommet F\text{F}.

Application et méthode - 5

Énoncé

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

1. Déterminer la matrice d’adjacence M\text{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\text{A} à C\text{C}.
b. Déterminer le nombre de chemins de longueur 3 reliant C\text{C} à B\text{B}.

Graphe

Solution


1. On a M=(0101000000100000010101100)\mathrm{M}=\left(\begin{array}{lllll} 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 \end{array}\right).
2. a. On a M3=(1110000000001011101001010)\mathrm{M}^{3}=\left(\begin{array}{lllll} 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 \end{array}\right).
Il y a donc une unique chaîne de longueur 3 reliant A\text{A} à C\text{C}. On constate qu’il n’y a pas de chemin de longueur 3 reliant C\text{C} à A\text{A}.
b. D’après la matrice M3\mathrm{M}^{3}, il n’y a donc pas de chemin de longueur 3 reliant C\text{C} à B\text{B}.

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

Méthode

1. On détermine la matrice d’adjacence M\text{M} en prenant garde à l’orientation des arêtes.

2. ● On souhaite déterminer le nombre de chemins de longueur 3\color{lightseagreen}\text{3} : cela nécessite donc de connaître M3\mathrm{M}^{\color{lightseagreen}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.