Représentation des graphes

Nous aimons bien communiquer par des dessins, mais les machines n'en sont pas encore là : il faut donc trouver d'autres façons de représenter les graphes.

La solution consiste à utiliser des matrices, et il y a différentes méthodes. Dans ce qui suit, on considère des graphes non pondérés, mais ces représentations s'adaptent sans problème aux graphes pondérés.

Matrice d'incidence

Présentation

La matrice d'incidence d'un graphe non orienté est une matrice $J$ à coefficients entiers dont les lignes sont repérées par les sommets d'un graphe et les colonnes par ses arêtes :

Définition (Matrice d'incidence)

Par définition, $J_{s,\varepsilon}$ vaut :

• 1 quand $s$ est une extrémité de l'arête $\varepsilon$ si celle-ci n'est pas une boucle,
• 2 quand $s$ est une extrémité de la boucle $\varepsilon$,
• 0 si $s$ n'est pas une extrémité de $\varepsilon$.

On peut reconstituer un graphe non orienté à partir de sa matrice d'incidence, car elle donne le nombre de sommets, le nombre d'arêtes et elle dit comment chaque arête est liée à chaque sommet.

Exercice : Représentez le graphe non orienté dont la matrice d'incidence est :

$\left(\begin{array}{ccccccccc}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\0 & 0 & 0 & 1 & 0 & 0 & 2 & 0 & 1 \\0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\end{array}\right)$

Exercice : Représentez les matrices d'incidences des graphes de ce chapitre.

Exercice : Réfléchir à la possibilité d'extension des matrices d'incidences aux graphes :

• orientés,
• pondérés.

Résultat

Théorème

Si $s_1,, s_n$ sont les sommets d'un graphe non orienté, alors : $\left( \begin{array}{c} d(s_1) \\ d(s_2) \\ \vdots \\ d(s_n) \end{array} \right) = J \left( \begin{array}{c} 1 \\ 1 \\ \vdots \\ 1 \end{array} \right)$

Exercice : Trouvez pourquoi.

Matrice d'adjacence

Présentation

On peut représenter un graphe non orienté par une matrice d'adjacence.

Définition (Matrice d'adjacence)

Dans une matrice d'adjacences, les lignes et les colonnes représentent les sommets du graphe.

• Un 1 à la position (i,j) signifie que le sommet i est adjacent au sommet j.
• Sinon, on place un 0.

En cas de boucle (pour le sommet $i$, par exemple), on place un 1 sur la diagonale (en position $(i,i)$.

Remarque : On aurait pu convenir de placer un 2 en cas de boucle. L'avantage serait de continuer à obtenir le degré des sommets en faisant les sommes par lignes. Par contre, on perdrait la possibilités, évoquée ci-dessous, de déterminer les chemins de longueur $k$.

Exemple

Considérons le graphe $G$ :

Attach:graphe1bx.jpg Δ

Voici la matrice d'adjacences du graphe G :

$M = \left(\begin{array}{ccccc}0 & 0 & 1 & 1 & 1\\0 & 0 & 1 & 0 & 0\\1 & 1 & 0 & 1 & 1\\1 & 0 & 1 & 0 & 1\\1 & 0 & 1 & 1 & 0\\\end{array}\right)$

Exercice : Décrivez le graphe G ci-dessous par une matrice d'adjacences. Attach:graphe2.jpg Δ

Exercice : Représentez les matrices d'adjacences des graphes de ce chapitre.

Exercice : Réfléchir à la possibilité d'extension des matrices d'adjacences aux graphes :

• orientés,
• pondérés.

Propriétés de la matrice d'adjacence

Cette matrice a plusieurs caractéristiques :

Théorème

1. Elle est carrée : il y a autant de lignes que de colonnes.
2. Un 1 sur la diagonale indique une boucle. Si le graphe n'a pas de boucle, alors la diagonale de sa matrice d'adjacence est nulle.
3. La matrice d'adjacence d'un graphe non orienté est symétrique : $m_{ij} = m_{ji}$.

Exercice : Calculez $M^2$ et $M^3$ pour la matrice d'adjacence $M$ ci-dessus. Comparer ces matrices aux chaînes de longueur 2 et 3 reliant deux sommets quelconques.

Théorème

Soit $A$ la matrice d'adjacence d'un graphe $G$. Le coefficient $(s,t)$ de $A^k$ est le nombre de chaînes de longueur $k$ qui mènent du sommet $s$ au sommet $t$.

Exercice : Démontrez ce résultat, par récurrence.

Exercice : On pose : $J=\left( \begin{array}{cccc} 2 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ \end{array}\right)$

1. Dessinez le graphe non orienté ayant $J$ pour matrice d'incidence.
2. Déterminez sa matrice d'adjacence B.
3. Vérifiez les formules précédentes :
4. le lien entre matrice d'incidence et degré des sommets,
5. le lien entre $B^k$ et les chaînes de longueur $k$.

Avantages et inconvénients de cette représentation

Avantages

• Représentation intéressante si beaucoup d'arêtes la cardinalité de l'ensemble des arcs est proche de celle de l'ensemble des sommets au carré.
• Accès facile à la relation d'adjacence.
• Possibilité d'obtenir les chaînes de longueur $k$.

Inconvénient

• Nécessite une grande quantité de mémoire.

Listes d'adjacence

Présentation

Définition (Liste d'adjacence)

On peut encore représenter un graphe en donnant pour chacun de ses sommets la liste des sommets auxquels il est adjacent. On parle alors de liste d'adjacence.

Exemple : On considère le graphe $G$ suivant : Attach:graphe1b.jpg Δ

Voici les listes d'adjacences de $G$ :

1 : 3, 4, 5

2 : 3

3 : 1, 2, 4, 5

4 : 1, 3, 5

5 : 1, 3, 4

Exercice : Représentez les listes d'adjacences des graphes de ce chapitre.

Exercice : Réfléchir à la possibilité d'extension des listes d'adjacences aux graphes :

• orientés,
• pondérés.

Avantages et inconvénients de cette représentation

Avantages

• Représentation adaptée aux graphes peu denses.
• Facile d'étendre cette représentation aux graphes orientés.
• Faible occupation mémoire.

Inconvénients

• Difficulté de savoir si deux sommets sont effectivement connectés (par une chaîne de longueur plus grande que 1).
• Mise en œuvre légèrement plus compliquée.

Travaux pratiques

1. Réaliser une classe Graphe, pour les graphes non orientés, non pondérés.
   -> On stockera cette classe dans un module graphe.py.
2. Offrir la possibilité de pondérer ses graphes : voir ici.
3. Réaliser une classe Arbre, qui hérite de la classe Graphe.
   -> Elle constituera le module arbre.py.
4. Réfléchir à une classe pour les graphes orientés, sur le même modèle que la classe Graphe.
5. Réfléchir de même aux classes Foret et Arborescence.
   -> On créera autant de nouveaux modules...

On constituera alors un package graphes, c'est-à-dire un répertoire de ce nom, contenant :

• un fichier __init__.py vide,
• chacune des classes ci-dessus.

On pourra alors importer chacune des classes de ce paquage, suivant ses besoins :

  from graphes.arbre import Arbre
  from graphes.graphe import Graphe