1.2 Définitions

Un graphe $G=(V,E)$ est composé d’un ensemble $V=\{1,\dots,n\}$ de noeuds (vertices en anglais) et d’un ensemble $E$ d’arêtes (edges en anglais) avec $\{i,j\}\in E$ s’il y a une arête entre les noeuds $i$ et $j$ dans le graphe. On dit que l’arête $e=\{i,j\}\in E$ est issue de $i$ (ou de $j$).

Le nombre de noeuds $n$ est l’ordre du graphe tandis que son nombre d’arêtes $|E|$ est appelé taille du graphe.

Différents types de graphes.

Un graphe est dirigé ou orienté lorsque ses arêtes le sont i.e. lorsque l’arête $(i,j)$ est différente de l’arête $(j,i)$. Il est non dirigé sinon.

Les graphes simples n’ont pas de boucles (i.e. $(i,i)$ n’est jamais une arête). Ils peuvent être binaires: une arête est présente (1) ou absente (0), ou valués: les arêtes présentes sont alors munies d’une valeur (poids). Noter qu’un graphe binaire est un cas particulier de graphe valué où toutes les arêtes présentes ont le poids 1.

Un graphe simple sur $n$ noeuds possède au plus ${n\choose 2}=n(n-1)/2$ arêtes s’il est non dirigé et $2{n\choose 2}=n(n-1)$ arêtes s’il est dirigé.

Les graphes biparties sont tels que $V=V_1\cup V_2$ avec $V_1\cap V_2 = \emptyset$ et les arêtes $e=\{u,v\}\in E$ sont telles que $u\in V_1, v\in V_2$. P. ex. le réseau acheteur-produit d’une plateforme commerciale en ligne. Tout ce qui suit se généralise facilement à ce cas.

Matrice d’adjacence.

Une représentation alternative d’un graphe $G=(V,E)$ est la matrice d’adjacence.

Definition 1.1 Un graphe $G=(V,E)$ binaire sur un ensemble $V=\{1,\dots,n\}$ de noeuds peut-être représenté par sa matrice d’adjacence (binaire) $A=(A_{ij})_{1\le i , j \le n }$ où \[ A_{ij} = \left\{ \begin{array}{ll} 1 & \text{ si } \{i,j\}\in E, \\ 0 & \text{sinon.} \end{array} \right. \] Lorsque le graphe est non dirigé, la matrice $A$ est symétrique. Si le graphe est simple on pose $A_{ii}=0$ pour tout $i$. Si le graphe est valué, on peut considérer une matrice d’adjacence valuée \[ A_{ij} = \left\{ \begin{array}{ll} w_{ij} &\text{si l'arête est présente entre $i$ et $j$ et de poids } w_{ij}, \\ 0 & \text{sinon.} \end{array} \right. \]

Exercice. Reconstruire le graphe $G=(V,E)$ encodé par la matrice d’adjacence suivante. \[ A= \begin{pmatrix} 0 &1& 1&0 & 0 \\ 1 & 0 & 1 & 1 & 0\\ 1 & 1 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 & 0\\ 0 & 0 &0&0&0 \end{pmatrix} . \]

Stockage informatique.

Dans le cas d’un graphe non dirigé la matrice d’adjacence est symétrique. Donc il y a redondance de l’information. Pour le stockage informatique ce n’est alors pas le format recommandé. Mais même pour un graphe dirigé, la matrice d’adjacence n’est pas optimal, car les graphes observées sont généralement sparse, i.e. peu d’arêtes sont présentes parmi toutes les arêtes possible. La matrice d’adjacence est alors une matrice creuse. Si en plus l’ordre du graphe est élévé, stocker une matrice de taille $|V|\times |V|$ pose vite des problèmes.

.	matrice d’adjacence $A$	liste d’arêtes $E$
graphe non dirigé	information redondante	pas de redondance
mémoire	$O(\|V\|^2)$	$O(\|E\|)$
graphe sparse	matrice creuse	la liste est courte

En terme de mémoire la solution la plus efficace consiste à stocker la liste d’arêtes $E$, et éventuellement l’ensemble des noeuds $V$ si le graphe contient des noeuds isolés. Pourtant, pour faire des calculs sur un graphe, il est souvent plus beaucoup simple d’utiliser la matrice d’adjacence. Pour le développement de code, il faut parfois jongler entre ses deux représentations de graphe.

Quant à l’analyse mathématique des propriétés d’un modèle de graphes, la matrice d’adjacence est beaucoup plus commode à manipuler que la liste d’arêtes et permet l’application des résultats mathématiques classiques, notamment de l’algèbre de la théorie des matrices aléatoires.