Fiche de révision : Graphes et matrices

Graphes non orientés

Dans cette partie, nous considérons $G$, un graphe non orienté.

• On appelle graphe non orienté un ensemble fini d’éléments, reliés ou non par une propriété commune.
• Les éléments s’appellent les sommets du graphe.
• Le nombre de sommets s’appelle l’ordre du graphe.
• La relation entre deux éléments est appelée une arête. Les arêtes peuvent se parcourir dans les deux sens.
• S’ils sont reliés entre eux par une arête, deux sommets sont adjacents.
• Si un sommet n’est relié à aucun autre, on dit que c’est un sommet isolé.
• Un graphe complet est un graphe où deux sommets quelconques sont toujours adjacents.
• Dans un graphe complet, chaque sommet est relié à tous les autres.
• Le degré d’un sommet de $G$ est le nombre d’arêtes qui relient ce sommet aux autres sommets du graphe.
• Dans un graphe $G$ non orienté, la somme des degrés est égale au double du nombre d’arêtes et est paire.
• Il y a un nombre pair de sommets de degré impair.
• Une chaîne de $G$ est une suite d’arêtes consécutives.
• Si les deux extrémités de la chaîne sont le même sommet, la chaîne est fermée.
• La longueur d’une chaîne est le nombre d’arêtes qu’elle contient.
• Dans un graphe non orienté, un cycle est une chaîne fermée qui ne comporte que des arêtes distinctes.
• Si deux sommets quelconques peuvent toujours être reliés par une chaîne, alors $G$ est un graphe connexe.

Graphes orientés

Dans cette partie, nous considérons $G$, un graphe orienté.

• Un graphe orienté est constitué de sommets.
• Le nombre de sommets s’appelle l’ordre du graphe.
• Certains sommets sont reliés par des arêtes qui sont orientées : elles ne peuvent être parcourues que dans un seul sens.
• La lecture du sens des arêtes est importante, car elle va déterminer les parcours possibles sur un graphe.
• Dans un graphe orienté, une boucle est une arête orientée d’origine et d’extrémité identiques.
• Le vocabulaire est proche de celui pour les graphes non orientés :
• on parle de chaîne pour un parcours constitué d’arêtes consécutives ;
• nous trouverons dans certains exercices le mot chemin quand le parcours est orienté ;
• si la chaîne ou le chemin a une origine et une extrémité identiques, alors on dira que c’est une chaîne fermée, ou un chemin fermé ;
• s’il existe un chemin fermé qui n’emprunte qu’une seule fois une arête nous parlerons parfois de circuit pour un graphe orienté (le mot est équivalent à cycle) ;
• notons enfin que les arêtes, dans un graphe orienté, sont parfois appelées arcs.
• Le degré d’un sommet de $G$ est le nombre d’arêtes qui relient ce sommet aux autres sommets du graphe, quel que soit leur sens de parcours.
• Soit $S$ un des sommets de $G$.
• Une boucle sur un sommet $S$ est considérée comme deux arêtes : en effet, elle part de $S$ et elle arrive vers $S$. Elle sera comptée $2$ fois dans le calcul du degré d’un sommet.
• Dans un graphe orienté, la somme des degrés est égale au double du nombre d’arêtes.

Matrices d’adjacence d’un graphe

• Soit $m\in \mathbb N^*$, $G$ un graphe d’ordre $n$, de sommets $S_1$, $S_2$, …, $S_{n-1}$, $S_n$, et $A$ sa matrice d’adjacence.
• Pour tous entiers $i$ et $j$ : le nombre de chemins – ou chaînes – de longueur $m$ entre $S_i$ et $S_j$ est $(A^m )_{i,j}$.
  C’est-à dire le coefficient de la matrice $A^m$ situé à la $i\text{-ème}$ ligne et la $j\text{-ième}$ colonne.
• Méthodologie pour déterminer le nombre de chemins de longueur $m$ entre deux sommets $S_i$ et $S_j$ :
• trouver la matrice d’adjacence $A$ du graphe ;
• calculer à la main, ou à la calculatrice, la matrice $A^m$ ;
• trouver le coefficient situé à la ligne $i$ et la colonne $j$ de cette matrice.
• Ce sera le nombre de chemins cherché.