Chapitre 14 (Spécialité)

Les graphes

Chapitre 14 (Spécialité)
Les graphes

ILes graphes non orientés

ALes principes élémentaires

On appelle graphe un ensemble de sommets, qui peuvent être reliés deux à deux par des arêtes.
L'ordre d'un graphe désigne le nombre de ses sommets.
Deux sommets d'un graphe reliés par une arête sont dits adjacents.
Deux sommets peuvent être reliés par plusieurs arêtes.
Le degré d'un sommet désigne le nombre d'arêtes connectées à ce sommet.
La somme des degrés d'un graphe non orienté est égale au double du nombre d'arêtes que comporte ce graphe.
TES01003-01.PNG

Le graphe ci-dessus est d'ordre \(\displaystyle{6}\). Le degré du sommet \(\displaystyle{1}\) est égal à \(\displaystyle{4}\). Les sommets \(\displaystyle{5}\) et \(\displaystyle{6}\) ne sont pas adjacents.

La matrice associée (ou matrice d'adjacence) à un graphe d'ordre \(\displaystyle{n}\) est une matrice à \(\displaystyle{n}\) lignes et \(\displaystyle{n}\) colonnes, où le terme \(\displaystyle{a_{i,j}}\) est égal au nombre d'arêtes reliant les sommets \(\displaystyle{i}\) et \(\displaystyle{j}\).
La matrice associée à un graphe non orienté est symétrique.
La matrice associée au graphe précédent est :

$$ M = \begin{pmatrix} 0 & 1 & 1 & 0 & 1 & 1 \cr 1 & 0 & 1 & 0 & 0 & 0 \cr 1 & 1 & 0 & 1 & 0 & 0 \cr 0 & 0 & 1 & 0 & 0 & 1 \cr 1 & 0 & 0 & 0 & 0 & 0 \cr 1 & 0 & 0 & 1 & 0 & 0 \end{pmatrix} $$
Un sous-graphe est une partie d'un graphe : il ne comporte que certains sommets du graphe initial ainsi que les arêtes reliant ces sommets.
Un graphe est dit complet si tous ses sommets sont deux à deux adjacents.

BLes chaînes

Une chaîne est une liste ordonnée de sommets où chaque sommet est adjacent au précédent et au suivant.
La longueur d'une chaîne désigne le nombre de ses arêtes.
La distance entre deux sommets est égale à la longueur de la chaîne la plus courte reliant ces deux sommets.
Le diamètre d'un graphe est la plus grande distance entre deux sommets.
Une chaîne fermée est une chaîne dont le premier sommet est identique au dernier sommet.
Un cycle est une chaîne fermée dont toutes les arêtes sont distinctes.
Une chaîne eulérienne est une chaîne formée de toutes les arêtes d'un graphe, chacune n'apparaissant qu'une seule fois.
Un cycle eulérien est un cycle formé de toutes les arêtes d'un graphe, chacune n'apparaissant qu'une seule fois.
Un graphe est dit connexe si pour tout couple de sommets, il existe une chaîne reliant ces deux sommets.

Le graphe ci-dessous n'est pas connexe : le sommet \(\displaystyle{5}\) est isolé.
\(\displaystyle{4-6-1-2}\) est une chaîne.
La distance entre les sommets \(\displaystyle{2}\) et \(\displaystyle{4}\) est égale à \(\displaystyle{2}\).
\(\displaystyle{1-2-3-1}\) est un cycle.
\(\displaystyle{1-6-4-3-2-1-3}\) est une chaîne eulérienne.

TES01003-02.PNG

D'après le théorème d'Euler :

  • un graphe connexe admet une chaîne eulérienne si et seulement s'il possède zéro ou deux sommets de degré impair ;
  • un graphe connexe admet un cycle eulérien si et seulement s'il ne possède que des sommets de degré pair.
On considère la matrice \(\displaystyle{M^p}\), puissance \(\displaystyle{p}\)-ième de la matrice \(\displaystyle{M}\) associée à un graphe d'ordre \(\displaystyle{n}\). Son terme \(\displaystyle{m_{i,j}}\) est égal au nombre de chaînes de longueur \(\displaystyle{p}\) partant du sommet \(\displaystyle{i}\) vers le sommet \(\displaystyle{j}\).

CLa coloration

La coloration d'un graphe a pour objectif d'attribuer une couleur à chaque sommet, de sorte que deux sommets adjacents ne soient pas de la même couleur.
On appelle nombre chromatique d'un graphe le plus petit nombre de couleurs permettant de colorer ce graphe.
Soit un graphe de degré \(\displaystyle{d}\).
Le nombre chromatique de ce graphe est inférieur ou égal à \(\displaystyle{d + 1}\).

IILes graphes étiquetés et les graphes pondérés

ALes graphes étiquetés

On appelle graphe étiqueté un graphe dont chacune des arêtes est associée à une étiquette. Une étiquette peut correspondre à un texte ou à un nombre.
TES01003-03.PNG

BLes graphes pondérés

On appelle graphe pondéré un graphe étiqueté dont les étiquettes sont toutes des nombres positifs.

CPlus courte chaîne

Le poids d'une chaîne d'un graphe pondéré est la somme des poids des arêtes qui forment cette chaîne.
On appelle plus courte chaîne entre deux sommets un chaîne de poids minimum reliant ces deux sommets.
On détermine la plus courte chaîne à l'aide de l'algorithme de Dijkstra.

IIILes graphes orientés

ADéfinition

Un graphe orienté est un graphe dont les arêtes ont un sens.
TES01003-04.PNG
Le terme \(\displaystyle{a_{i,j}}\) de la matrice associée à un graphe orienté est égal au nombre d'arêtes d'origine \(\displaystyle{i}\) et d'extrémité \(\displaystyle{j}\).

BLes graphes probabilistes

Un graphe probabiliste est un graphe orienté pondéré où, pour chaque sommet, la somme des poids des arêtes sortantes est égale à \(\displaystyle{1}\).
Dans un graphe probabiliste, chaque sommet correspond à un état.
L'état probabiliste d'un graphe probabiliste est la loi de probabilité sur l'ensemble des états. Cette loi est présentée sous la forme d'une matrice ligne, où chaque terme est égal à la probabilité de l'état correspondant.
La matrice de transition d'un graphe probabiliste d’ordre \(\displaystyle{n}\) est une matrice à \(\displaystyle{n}\) lignes et \(\displaystyle{n}\) colonnes, où le terme \(\displaystyle{a_{i,j}}\) est égal au poids de l'arête d'origine \(\displaystyle{i}\) et d'extrémité \(\displaystyle{j}\) ou à \(\displaystyle{0}\) si cette arête n'existe pas.
Soient \(\displaystyle{M}\) la matrice de transition d'un graphe probabiliste d'ordre \(\displaystyle{n}\), et \(\displaystyle{P_{0}}\) l'état initial.
La matrice ligne \(\displaystyle{P_{n}}\) de l'état probabiliste à l'instant \(\displaystyle{n}\) est égale à :
$$P_{n} = P_{0} \times M^{n}$$
Si l'état \(\displaystyle{P_{n}}\) devient constant à partir d'un certain rang \(\displaystyle{n}\), c'est-à-dire que la matrice ligne \(\displaystyle{P_{n}}\) reste identique à partir de ce rang, cet état est appelé état stable du graphe.
Se connecter
Ce compte existe mais n'est pas encore activé.

Activez votre compte puis connectez vous svp.

Recevoir le mail d'activation



Rester connecté

ou
S'inscrire







ou
Signaler une erreur