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

Merci !

Fiches
Classe(s) : Tle Générale | Thème(s) : Graphes et matrices


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.

06467_C17_01

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.

06467_C17_02

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.

Tableau de 2 lignes, 7 colonnes ;Corps du tableau de 2 lignes ;Ligne 1 : Sommet; A; B; C; D; E; F; Ligne 2 : Degré; 5; 1; 2; 2; 3; 1;

De plus, en numérotant les sommets par ordre alphabétique, la matrice d’adjacence du graphe est la matrice M définie ci-contre.

M= 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.

06467_C17_03

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 2718188-Eqn218.

Le nombre de chemins de longueur 4 entre les sommets A et B et le coefficient de M4 de la ligne 1 et de la colonne 2 : il y a 3 chemins.