Graphes et matrices
Cours
1. Vocabulaire des graphes
Un graphe est constitué de sommets reliés (ou non) par des arêtes (graphe non orienté) ou des arcs (graphe orienté).
Le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes. Une chaîne est une suite de sommets consécutivement reliés par des arêtes. Un cycle est une chaîne qui revient à son sommet de départ sans répéter d'arête. Un graphe est connexe si l'on peut relier deux sommets quelconques par une chaîne.
2. Matrice d'adjacence
La matrice d'adjacence $M$ d'un graphe à $n$ sommets est une matrice $n \times n$ où $m_{ij} = 1$ s'il existe une arête entre les sommets $i$ et $j$, et $m_{ij} = 0$ sinon.
Pour un graphe non orienté, la matrice d'adjacence est toujours symétrique. Pour un graphe orienté, elle ne l'est pas en général.
3. Puissances de la matrice d'adjacence
Propriété : le coefficient $(i,j)$ de $M^k$ donne le nombre de chaînes de longueur $k$ reliant le sommet $i$ au sommet $j$.
4. Graphe complet
Un graphe complet à $n$ sommets (où tous les sommets sont reliés deux à deux) possède $\dfrac{n(n-1)}{2}$ arêtes.
5. Applications
Les graphes et leurs matrices d'adjacence permettent de modéliser des réseaux (routes, réseaux sociaux, réseaux informatiques) et de répondre à des questions comme : « existe-t-il un trajet direct ou en $k$ étapes entre deux sommets ? »