Les graphes non orientés
Les principes élémentaires
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.
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.
Les chaînes
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
Plus courte chaîne
On peut déterminer la plus courte chaîne à l'aide de l'algorithme de Dijkstra.
Les graphes orientés
Définition
Les graphes probabilistes
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.
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.
