GRAPHES

Définitions

Définitions : Élèments d'un graphe

• Un graphe d'ordre \(n\) est un ensemble de \(n\) points, appelés sommets, reliés entre eux par des liens.

• Dans un graphe non orienté, les liens reliant deux sommets se schématisent par un trait, appelé arête, et dans un graphe orienté par une flèche, appelée arc.

• Deux sommets sont adjacents s'ils sont reliés par une arête ou un arc.

• Un sommet est isolé si aucune arête ou arc ne le relie aux autres sommets.

• Le degré d'un sommet est le nombre d'arêtes ou d'arcs dont ce sommet est une extrémité (une boucle comptant pour 2).

• Un graphe est complet si tous les sommets sont adjacents entre eux.

• Un graphe simple est un graphe sans boucle ni arête multiple. Il n'y a alors d'arêtes qu'entre des sommets distincts, et entre deux sommets il y a au plus une arête.

Définitions : Parcours d'un graphe

• Une chaîne est une liste de sommets telle que chaque sommet de la liste soit adjacent au suivant.

• Un graphe est connexe s'il existe une chaîne entre deux sommets quelconques de ce graphe.

• Une chaîne fermée est une chaîne dont l'origine et l'extrémité sont confondues.

• Une chaîne fermée composée d'arêtes toutes distinctes forme un cycle.

• Une chaîne eulérienne est une chaine qui parcourt toutes les arêtes d'un graphe connexe une et une seule fois.

Remarque

• Dans un graphe orienté, on parle de chemin pour une chaîne et de circuit pour un cycle.

• Lorsque la chaîne eulérienne est fermée, on l'appellera cycle eulérien. C'est donc une chaine qui passe par toutes les arêtes et qui revient à son point de départ.

Théorème

Dans un graphe, la somme des degrés de chaque sommet est égale au double du nombre d'arêtes.

Preuve

En effet, une arête relie nécessairement deux sommets, par définition.

Théorème

Pour qu'un graphe comporte une chaine eulérienne, il faut qu'il possède 0 ou deux 2 sommets de degré impair. Dans le cas de 2 sommets de degré impair, ils seront situés au début et à la fin de la chaine.

Matrice d'adjacence

Définitions

À tout graphe \(𝐺\) d'ordre \(𝑛\), on peut associer une matrice carrée \(𝑚 = (𝑎_{𝑖𝑗})\) d'ordre \(n\) telle que \(𝑎_{𝑖𝑗}\) est le nombre d'arcs ou d'arêtes reliant le sommet \(𝑖\) au sommet \(𝑗\). Cette matrice est appelée matrice d'adjacence du graphe \(𝐺\).

Remarque

La matrice d'adjacence d'un graphe non orienté est symétrique.

Théorème : Nombre de chemins de longueur \(p\)

Soit \(G\) un graphe d'ordre \(n\) et \(M = (m_{ij})\) sa matrice d'adjacence. Si on note \(M^p = (m_{ij}^{(p)})\), alors \(m_{ij}^{(p)}\) est le nombre de chemins de longueur \(p\) reliant le sommet \(i\) au sommet \(j\).

Preuve

Montrons par récurrence que :

\(\forall p \in \mathbb{N}^*\), \(m_{ij}^{(p)}\) est le nombre de chemins de longueur \(p\) reliant \(i\) à \(j\).

Initialisation :

Pour \(p=1\), \(M^1=(m_{ij}^{(1)})\) est le nombre de chemins de longueur 1 reliant \(i\) à \(j\) par définition de la matrice d'adjacence.

La proposition est donc initialisée pour \(p=1\)

Hérédité :

Soit \(p \in \mathbb{N}^*\), supposons que \(m_{ij}^{(p)}\) est le nombre de chemins de longueur \(p\) reliant \(i\) à \(j\).

\((m_{ij}^{(p+1)})=M^{p+1}=M \times M^{p}= (m_{ij}^{(1)})(m_{ij}^{(p)})\) = \(\sum_{k=1}^{n} m_{ik}^{(1)}m_{kj}^{(p)}\)

• \(m_{ik}^{(1)}\) est le nombre de chemins de longueur 1 reliant \(i\) à \(k\).

• \(m_{kj}^{(p)}\) nombre de chemins de longueur \(p\) reliant \(k\) à \(j\).

Donc \(m_{ik}^{(1)}m_{kj}^{(p)}\) est le nombre de chemins de longueur \(p+1\) reliant \(i\) à \(j\) passant par \(k\).

Par somme, \(\sum_{k=1}^{n} m_{ik}^{(1)}m_{kj}^{(p)}\) est le nombre total de chemins de longueur \(p+1\) reliant \(i\) à \(j\).

Alors la proposition est héréditaire.

Conclusion :

Par initialisation et hérédité : \(\forall p \in \mathbb{N}^*\), \(m_{ij}^{(p)}\) est le nombre de chemins de longueur \(p\) reliant \(i\) à \(p\).