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

icône de pdf
Signaler

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.

7cbd9bbb-85af-4198-82d1-6b59dd3c4ec6

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.

7dfef848-86e6-45b4-92ad-de09ee9c972c

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.

5b4916a1-5c53-4ed3-9f9e-28b8bb639f25

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.

a2b97a41-f6e0-4d36-9f7f-51e7febe77be

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 b445a9d2-9ee6-4242-9cad-27f395d4db0e.