Matrices : graphes

Graphes

Définition

Un graphe est un ensemble fini d’éléments (les points), appelé sommets, reliés entre eux par des arêtes (les segments).

Notions

Exemples

Graphe d’ordre 4. Le sommet A est de degré 2 et est adjacent aux sommets B et C.	Graphe complet d’ordre 5.
Graphe orienté	Graphe non orienté

Chaînes

Définition

Une suite d’arêtes consécutives forme une chaîne. Sa longueur est le nombre d’arêtes qui la composent. Si le sommet de départ est le même que celui d’arrivée, on dit que la chaîne est fermée.

S’il est possible de relier n’importe quelle paire de sommets du graphe par une chaîne, on dit que le graphe est connexe.

Exemples

Graphe connexe. On peut par exemple construire une chaîne fermée de longueur 3 en reliant A à B, puis B à C, puis de nouveau C à A.	Graphe non connexe. On peut par exemple construire une chaîne de longueur 2 de E à C.

Matrice d’adjacence

Chaque ligne et chaque colonne de la matrice d’adjacence représente un sommet du graphe. Pour un graphe d’ordre n, la matrice d’adjacence est une matrice carrée $$n\times n$$​.

Dans un graphe non orienté, la valeur du coefficient $$a_{i,j}$$​ de la matrice est 1 si le sommet $$I$$​ est adjacent au sommet $$j$$​. Sinon, le coefficient est 0.

Sommet A B C Ligne/colonne 1 2 3

​$$\left(\begin{matrix}0&1&0\\1&0&1\\0&1&0\\\end{matrix}\right)$$​​

Dans un graphe orienté, la valeur du coefficient $$a_{i,j}$$​ de la matrice est 1 si une arête part du sommet $$I$$​ (ligne) et va vers le sommet $$j$$​ (colonne). Sinon, le coefficient est 0.

Exemple

Sommet A B C Ligne/colonne 1 2 3

​$$\left(\begin{matrix}0&1&1\\0&1&0\\1&0&0\\\end{matrix}\right)$$​​

Note : Dans le cas d’un graphe non orienté, la matrice adjacente est symétrique, c’est-à-dire que le coefficient $$a_{i,j}$$ est toujours égal au coefficient $$a_{j,i}$$​. Cependant, dans un graphe orienté, il est possible que les deux coefficients ne soient pas égaux.