Fiche de révision : Graphes

Graphes non-orientés

• Un graphe est composé de sommets et d’arêtes reliant certains de ces sommets.

• L’ordre d’un graphe est le nombre de ses sommets.

• Une boucle est une arête reliant un sommet à lui-même.

• Deux sommets reliés par une arête sont dits adjacents.

• Le degré d’un sommet est le nombre d’arêtes dont ce sommet est une extrémité.

• Un graphe est complet lorsque tous ses sommets sont adjacents.

• La somme des degrés des sommets d’un graphe non orienté est égale au double du nombre total d’arêtes.

• La matrice d’adjacence associée à un graphe non orienté d’ordre $n$ dont les sommets sont numérotés de $1$ à $n$ est la matrice carrée d’ordre $n$, où le terme situé en ligne $i$ et colonne $j$ est égal au nombre d’arêtes reliant $i$ et $j$. La matrice d’adjacence d’un graphe non orienté sera toujours symétrique par rapport à sa première diagonale.

• Une chaîne est une liste ordonnée de sommets reliés deux à deux par une arête.

• La longueur d’une chaîne est le nombre d’arêtes qui la composent.

• Une chaîne est fermée lorsque l’origine et l’extrémité sont confondues.

• Un cycle est une chaîne fermée dont toutes les arêtes sont distinctes.

• Propriété : trouver dans un graphe un nombre de chaînes de longueur donnée

Soit $p$ un entier naturel et $M$ la matrice d’adjacence associée à un graphe non orienté dont les sommets sont numérotés. Le terme $a_{ij}$ (ligne $i$ colonne $j$) de la matrice $M^p$ donne le nombre de chaînes de longueur $p$ reliant $i$ et $j$.

• Un graphe est connexe s’il existe toujours une chaîne entre deux sommets distincts, c’est-à-dire si le graphe est « d’un seul tenant ».
• Une chaîne est eulérienne lorsqu’elle contient chaque arête du graphe une et une seule fois. Si cette chaîne est un cycle, on dit qu’il s’agit d’un cycle eulérien.

Le théorème d’Euler permet de savoir rapidement si un graphe connexe comporte une chaîne eulérienne ou un cycle eulérien.

• Théorème d’Euler :

Un graphe connexe admet une chaîne eulérienne si, et seulement si, le nombre de sommets de degré impair vaut $0$ ou $2$. Un graphe connexe admet un cycle eulérien si, et seulement si, tous ses sommets sont de degré pair.

Graphes orientés

• Un graphe orienté est un graphe dont les arêtes sont orientées. Chaque arête ne peut être parcourue que dans le sens de la flèche. Une boucle est une arête orientée dont l’origine et l’extrémité sont les mêmes.
• La matrice d’adjacence associée à un graphe orienté d’ordre $n$, dont les sommets sont numérotés de $1$ à $n$, est une matrice carrée d’ordre $n$ où le terme figurant en ligne $i$ et colonne $j$ est égal à $1$ s’il existe une arête menant de $i$ à $j$, et à $0$ sinon. Contrairement à la matrice d’adjacence d’un graphe non orienté, celle d’un graphe orienté n’est pas forcément symétrique par rapport à sa première diagonale.
• Propriété : trouver dans un graphe un nombre de chaîne d’une longueur donnée
• Soit $p$ un entier naturel et $M$ est la matrice d’adjacence associée à un graphe orienté dont les sommets sont numérotés. Le terme $a_{ij}$ (ligne $i$ colonne $j$) de la matrice $M^p$ donne le nombre de chaînes de longueur $p$ reliant $i$ et $j$.
• Cette propriété est exactement la même que pour les graphes non orientés.
• Graphe étiqueté :

Un graphe étiqueté est un graphe orienté où chacune des arêtes est affectée d’une lettre ou d’un mot ou de tout autre symbole. Ces symboles sont appelés des étiquettes.

• Graphe pondéré :

Un graphe pondéré est un graphe étiqueté dont toutes les étiquettes sont des nombres positifs.

• Poids d’une chaîne :

Le poids d’une chaîne est la somme du poids des arêtes qui la composent.

• Plus courte chaîne :

Une plus courte chaîne entre deux sommets est, parmi les chaînes qui relient ces deux sommets, une chaîne de poids minimal.

Algorithme de Dijkstra-Moore

L’algorithme de Dijkstra-Moore permet de trouver la plus courte chaîne reliant un sommet à un autre dans un graphe.

• Placer tous les sommets du graphe dans la 1^re ligne d’un tableau.
  Sur la 2^e ligne du tableau, écrire le coefficient $0$ sous le sommet de départ et le coefficient $\infty$ sous les autres sommets.
• Sur la dernière ligne écrite, repérer le sommet $X$ de coefficient minimal.
  Commencer une nouvelle ligne et rayer toutes les cases vides sous $X$.
• Pour chaque sommet $Y$ adjacent à $X$, calculer la somme $P$ du coefficient de $X$ et du poids de l’arête reliant $Y$ à $X$. Si $P$ est strictement inférieur au coefficient de $Y$, inscrire $P_X$ dans la case correspondante de la colonne $Y$.
  Sinon, inscrire le coefficient de $Y$ et compléter la ligne par des coefficients de la ligne précédente.
• S’il reste des sommets non sélectionnés, recommencer à l’étape $2$.
  Sinon, passer à l’étape $5$.
• La longueur minimale est le nombre lu sur la dernière ligne du tableau.