Un graphe permet de représenter de manière très synthétique une expérience aléatoire ou encore un type de relation entre les objets d’une famille.
I. Définitions et vocabulaire
Définition : Un graphe (simple non orienté) est déterminé par la donnée, d’une part, d’un ensemble fini dont les éléments sont appelés sommets et, d’autre part, d’un ensemble de paires de sommets appelées arêtes.
Représentation
On représente les sommets d’un graphe par des points et les arêtes par des segments ou des arcs de courbes.
Vocabulaire
Deux sommets adjacents sont deux sommets d’une même arête. On dit qu’ils sont reliés par une arête.
Le degré d’un sommet est le nombre de sommets qui lui sont adjacents.
L’ordre d’un graphe est le nombre de ses sommets.
La matrice d’adjacence d’un graphe de sommets numérotés de 1 à n est la matrice carrée d’ordre n de coefficients aij qui valent 1 si les sommets numérotés i et j forment une arête et 0 sinon.
Théorème : La somme des degrés des sommets d’un graphe vaut le double du nombre de ses arêtes.
À noter
La somme des degrés des sommets d’un graphe est nécessairement paire.
II. Chaînes d’un graphe
Définitions
Une chaîne ou chemin d’un graphe est une liste ordonnée de sommets telle que chaque sommet de la liste est adjacent au suivant.
La longueur d’une chaîne est le nombre d’arêtes qui la compose.
Un graphe est connexe si toute paire de sommets fait partie d’une chaîne.
Un graphe est complet si toute paire de sommets forme une arête.
À noter
Tout graphe complet est connexe.
Théorème : Soit un graphe de matrice d’adjacence M. Le nombre de chemins de longueur nn∈ℕ∗, d’un sommet i à un sommet j est égal au coefficient de Mn de la ligne i et de la colonne j.
Méthodes
1) Déterminer le degré de chaque sommet d’un graphe
Donner le degré de chaque sommet du graphe représenté ci-contre.
Donner la matrice d’adjacence de ce graphe.
Conseils
Élaborez un tableau donnant le degré de chaque sommet et numéroter les sommets par ordre alphabétique pour déterminer la matrice d’adjacence.
Solution
Le degré de chaque sommet est résumé par le tableau ci-dessous.
011111100000100010100010101100100000
2) Déterminer le nombre de chemins entre deux sommets
On considère le graphe représenté ci-contre. Déterminer le nombre de chemins de longueur 4 entre les sommets A et B.
Conseils
Numérotez les sommets par ordre alphabétique et calculez la puissance quatrième de sa matrice d’adjacence.
Solution
En numérotant les sommets A, B, C, D et E : 1, 2, 3, 4 et 5, on obtient la matrice d’adjacence M=0110010011100100110101010, et 