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.

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.