Chapitre 29 — sommets, arêtes et chaînes : modéliser des réseaux, puis les calculer grâce à la matrice d'adjacence.
Naviguez avec les flèches ← → du clavier, ou via le Sommaire.
Un graphe se code par une matrice : la géométrie du réseau devient du calcul matriciel.
Un graphe est fait de sommets reliés par des arêtes. L'ordre est le nombre de sommets ; le degré d'un sommet est le nombre d'arêtes qui en partent (une boucle compte double).
Ordre $5$ ; ici $\deg(B)=5$ (la boucle compte double), $\deg(E)=1$.
Le graphe complet à $5$ sommets ($K_5$) : $10$ arêtes.
La somme des degrés des sommets vaut le double du nombre d'arêtes :
Cette somme est donc paire, et le nombre de sommets de degré impair est lui aussi pair. Pratique pour compter les arêtes sans erreur.
Une chaîne est une suite de sommets adjacents ; sa longueur est le nombre d'arêtes parcourues.
En vert, la chaîne $A-B-C-D-E$ : longueur $4$.
Un graphe est connexe s'il existe une chaîne entre deux sommets distincts quelconques. Un graphe complet est toujours connexe.
On peut repasser par un même sommet, mais jamais par une même arête.
Si $2$ sommets sont de degré impair, ils sont nécessairement les extrémités de la chaîne.
Les quatre quartiers sont reliés par sept ponts. Peut-on tous les traverser une seule fois et revenir au départ ?
Les quatre sommets sont de degré impair : aucune chaîne eulérienne. C'est impossible.
Pour un graphe d'ordre $n$ (sommets numérotés), $M=(m_{ij})$ où $m_{ij}$ est le nombre d'arêtes entre $i$ et $j$.
Graphe non orienté $\Rightarrow$ matrice symétrique. Graphe simple $\Rightarrow$ coefficients $0$ ou $1$.
Un graphe est orienté quand chaque arête (alors appelée arc) porte un sens. Chaque sommet a un degré entrant et un degré sortant.
Un graphe orienté $G_{11}$ d'ordre $5$ : chaque arc a un sens de parcours.
$m_{ij}=1$ s'il existe un arc de $i$ vers $j$. La matrice du graphe $G_{11}$ ci-avant est :
Pour un graphe orienté, $M$ n'est pas symétrique en général.
Toute matrice à coefficients positifs définit un graphe. Si elle est symétrique, le graphe est non orienté :
On numérote $4$ sommets, puis on relie $i$ et $j$ dès que $m_{ij}=1$.
Pour tout entier $p\geqslant 1$, le coefficient $(i,j)$ de $M^p$ donne le nombre de chaînes de longueur $p$ reliant $i$ à $j$ :
Le produit matriciel additionne, sur tous les sommets intermédiaires $k$, les façons d'aller de $i$ à $k$ puis de $k$ à $j$.
Le terme vaut $2$ : il y a deux chaînes de longueur $2$ du sommet $1$ au sommet $3$, à savoir :