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 un entier naturel non nul. On considère un graphe d’ordre (orienté ou non) dont les sommets sont numérotés de à , puis rangés dans l’ordre croissant.
La matrice d’adjacence de ce graphe est la matrice carrée de taille , dont le coefficient est égal au nombre d’arêtes partant du sommet pour arriver au sommet .

Remarque

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

Exemple


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

Définition

Soient et deux entiers naturels non nuls et la matrice d’adjacence d’un graphe d’ordre , dont les sommets sont numérotés de à et rangés dans l’ordre croissant.
Le terme de la -ème ligne et de la -ième colonne de la matrice donne le nombre de chaînes (ou de chemins) de longueur reliant le sommet au sommet .

Remarque

donne le nombre de chaînes (ou de chemins) de longueur reliant deux sommets.

DÉMONSTRATION

Voir exercice
84
p. 198
.

Exemple

En reprenant l’exemple précédent, on a .
Il existe donc 27 chaînes de longueur 4 reliant le sommet au sommet .
On a donc il n’existe aucune chaîne de longueur 2 reliant le sommet au sommet .

Application et méthode - 5

Énoncé

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

1. Déterminer la matrice d’adjacence de ce graphe en classant les sommets par ordre alphabétique.

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

Graphe

Solution


1. On a .
2. a. On a .
Il y a donc une unique chaîne de longueur 3 reliant à . On constate qu’il n’y a pas de chemin de longueur 3 reliant à .
b. D’après la matrice , il n’y a donc pas de chemin de longueur 3 reliant à .

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

Méthode

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

2. ● On souhaite déterminer le nombre de chemins de longueur : cela nécessite donc de connaître .
  ● 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.