Sommets, arêtes et chaînes d’un graphe

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.

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.

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 $a_{ij}$ 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.

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.

Théorème : Soit un graphe de matrice d’adjacence $M$. Le nombre de chemins de longueur $n$ ($n \in \mathbb{N}^*$), d’un sommet $i$ à un sommet $j$, est égal au coefficient de $M^n$ 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.

On considère le graphe représenté ci-contre. Déterminer le nombre de chemins de longueur 4 entre les sommets A et B.

ConseilsNumé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 = \begin{pmatrix} 0 \quad 1 \quad 1 \quad 0 \quad 0 \\ 1 \quad 1 \quad 0 \quad 0 \quad 1 \\ 1 \quad 0 \quad 0 \quad 1 \quad 1 \\ 1 \quad 0 \quad 1 \quad 0 \quad 1 \\ 0 \quad 1 \quad 1 \quad 1 \quad 0 \end{pmatrix}$ , et .