Les graphes non orientés
Les principes élémentaires
Graphe
On appelle graphe un ensemble de points et de lignes reliant certains de ces points. Les points sont appelés sommets du graphe, les lignes arêtes du graphe.
Ordre d'un graphe
L'ordre d'un graphe désigne le nombre de ses sommets.
L'ordre de ce graphe est 6.
Sommets adjacents
Deux sommets d'un graphe reliés par une arête sont dits adjacents.
Les sommets 2 et 3 sont adjacents.
Les sommets 2 et 4 ne sont pas adjacents.
Degré d'un sommet
Le degré d'un sommet désigne le nombre d'arêtes dont ce sommet est l'origine.
- Le degré du sommet 1 est 4.
- Le degré du sommet 6 est 2.
Somme des degrés et nombre d'arêtes
La somme des degrés des sommets d'un graphe non orienté est égale au double du nombre d'arêtes que comporte ce graphe.
| Sommet | 1 | 2 | 3 | 4 | 5 | 6 | Somme des degrés |
|---|---|---|---|---|---|---|---|
| Degré | 4 | 2 | 3 | 2 | 1 | 2 | 14 |
Le nombre d'arêtes de ce graphe est 14\div 2=7.
Matrice associée
La matrice associée (ou matrice d'adjacence) à un graphe d'ordre n est une matrice à n lignes et n colonnes, où le terme a_{i,j} est égal au nombre d'arêtes partant du sommet i pour aller jusqu'au sommet j.
La matrice associée à ce graphe 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}
Sous-graphe
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.
Graphe complet
Un graphe est dit complet si tous ses sommets sont deux à deux adjacents.
Le graphe ci-dessus est complet.
Les chaînes
Chaîne
Une chaîne est une liste ordonnée de sommets où chaque sommet est adjacent au précédent et au suivant.
Le chemin 1 - 2 - 3 - 4 est une chaîne reliant le sommet 1 à 4.
Par contre, 1 - 5 - 6 - 4 n'est pas une chaîne.
Longueur d'une chaîne
La longueur d'une chaîne désigne le nombre de ses arêtes.
La chaîne 1 - 2 - 3 - 4 est une chaîne de longueur 3.
Distance entre deux sommets
La distance entre deux sommets est égale à la longueur de la chaîne la plus courte reliant ces deux sommets.
La distance entre les sommets 1 et 4 est 2.
Diamètre d'un graphe
Le diamètre d'un graphe est la plus grande distance entre deux sommets.
Le diamètre du graphe est la distance entre les sommets 5 et 4, c'est-à-dire 4.
Chaîne fermée
Une chaîne fermée est une chaîne dont le premier sommet est identique au dernier sommet.
La chaîne 1 - 2 - 3 - 1 est fermée.
Cycle
Un cycle est une chaîne fermée dont toutes les arêtes sont distinctes.
La chaîne 1 - 2 - 3 - 4 - 6 - 1 est un cycle.
Chaîne eulérienne
Une chaîne eulérienne est une chaîne formée de toutes les arêtes d'un graphe, chacune des arêtes n'apparaissant qu'une seule fois.
5 - 1 - 6 - 4 - 3 - 2 - 1 - 3 est une chaîne eulérienne.
Cycle eulérien
Un cycle eulérien est un cycle formé de toutes les arêtes d'un graphe, chacune des arêtes n'apparaissant qu'une seule fois.
1 - 3 - 2 - 7 - 3 - 5 - 4 - 6 - 2 - 1 est un cycle eulérien.
Graphe connexe
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 5 est isolé.
Théorème d'Euler
- Un graphe connexe admet une chaîne eulérienne si et seulement s'il possède aucun, ou exactement 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.
Si un graphe connexe possède exactement deux sommets de degré impair notés A et B, alors toute chaîne eulérienne de ce graphe part de A et termine en B ou part de B et termine en A.
Il existe des algorithmes permettant de déterminer une chaîne eulérienne (ou un cycle eulérien selon les cas).
Nombre de chaînes de longueur p
On considère la matrice M^p, puissance p -ième de la matrice M associée à un graphe d'ordre n. Son terme m_{i,j} est égal au nombre de chaînes de longueur p partant du sommet i vers le sommet j.
La matrice associée à ce graphe 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}
On trouve :
M^3 =\begin{pmatrix}2 & 5 & 7 & 1 & 4 & 6 \cr 5 & \textcolor{red}{2} & 4 & 2 & 1 & 2 \cr 7 & 4 & 2 & 5 & 1 & 1 \cr 1 & 2 & 5 & 0 & 2 & 4 \cr 4 & 1 & \textcolor{Red}{1} & 2 & 0 & 0 \cr 6 & 2 & 1 & 4 & 0 & 0\end{pmatrix}
Il existe donc une unique chaîne de longueur 3 reliant le sommet 5 à 3 (5 - 1 - 2 - 3).
De même, il existe deux chaînes de longueur 3 reliant le sommet 2 à lui même (2 - 1 - 3 - 2 et 2 - 3 - 1 - 2).
Les graphes étiquetés et les graphes pondérés
Les graphes étiquetés
Graphe étiqueté
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.
Les graphes pondérés
Graphe pondéré
On appelle graphe pondéré un graphe étiqueté dont les étiquettes sont toutes des nombres positifs.
L'étiquette d'une arête est alors appelée poids de l'arête.
Plus courte chaîne
Poids d'une 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.
Le poids de la chaîne 7 - 6 - 1 - 2 est : 20+8+10=38.
Plus courte chaîne
On appelle plus courte chaîne entre deux sommets une chaîne de poids minimum reliant ces deux sommets.
La plus courte chaîne reliant le sommet 7 à 3 est 7 - 6 - 5 - 3 de poids 28.
On peut déterminer la plus courte chaîne à l'aide de l'algorithme de Dijkstra.
Les graphes orientés
Définition
Graphe orienté
Un graphe orienté est un graphe dont les arêtes ont un sens.
La matrice associée à ce graphe est : M =\begin{pmatrix}0 & 1 & 1 & 0 & 0 \cr 1 & 0 & 0 & 0 & 0 \cr 0 & 1 & 0 & 0 & 0 \cr 0 & 0 & 1 & 1 & 1 \cr 0 & 0 & 0 & 1 & 0 \end{pmatrix}.
Les graphes probabilistes
Graphe probabiliste
Un graphe probabiliste est un graphe orienté pondéré où, pour chaque sommet, la somme des poids des arêtes sortantes est égale à 1.
Etat
Dans un graphe probabiliste, chaque sommet correspond à un état.
Etat probabiliste
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.
Dans une population on étudie une épidémie de grippe.
On note a_n (respectivement b_n) la probabilité, en choisissant une personne au hasard dans la population, de tomber sur une personne malade (respectivement non malade).
Si au premier jour de l'étude 5% des personnes constituant cette population sont malades, l'état initial (au premier jour) est donc :
P_1=\begin{pmatrix}a_1 & b_1\end{pmatrix}=\begin{pmatrix}0{,}05 & 0{,}95\end{pmatrix}
Matrice de transition
La matrice de transition d'un graphe probabiliste d'ordre n est une matrice à n lignes et n colonnes, où le terme a_{i,j} est égal au poids de l'arête d'origine i et d'extrémité j ou à 0 si cette arête n'existe pas.
La matrice de transition de ce graphe est : \begin{pmatrix} 0{,}7 & 0{,}3 \cr\cr 0{,}15 & 0{,}85 \end{pmatrix}.
Etat probabiliste à l'instant n
Soit M la matrice de transition d'un graphe probabiliste d'ordre n, et soit P_{0} l'état initial.
La matrice ligne P_{k} de l'état probabiliste à l'instant k est égale à :
P_{k} = P_{0} \times M^{k}
L'état stable du graphe, s'il existe, est la matrice ligne P_k où k est le plus petit entier naturel tel que P_k=P_{k+1}.
Quand il existe, l'état stable vérifie l'équation X=XM d'inconnue X où M est la matrice de transition.
Cet état stable est indépendant de l'état initial.
Si M est la matrice de transition d'un graphe probabiliste d'ordre 2 ou 3 et si aucun coefficient de M n'est nul, le graphe probabiliste admet un état stable.
La matrice de transition de ce graphe est : \begin{pmatrix} 0{,}7 & 0{,}3 \cr\cr 0{,}15 & 0{,}85 \end{pmatrix}.
C'est donc une matrice d'ordre 2 dont aucun coefficient n'est nul.
Ce graphe admet donc un état stable.