Matrice et listes d'adjacences

Matrice d'adjacences

On peut représenter un digraphe par une matrice d'adjacences. Une matrice (n x m) est un tableau de n lignes et m colonnes. (i,j) désigne l'intersection de la ligne i et de la colonne j.
Dans une matrice d'adjacences, les lignes et les colonnes représentent les sommets du graphe. Un 1 à la position (i,j) signifie qu'un arc part de i pour rejoindre j.

Exemple

Voici la matrice d'adjacences du digraphe G:

M = Cette matrice à plusieurs caractéristiques:
  1. Elle est carrée: il y a autant de lignes que de colonnes.
  2. Il n'y a que des zéros sur la diagonale. Un 1 sur la diagonale indiquerait une boucle.
  3. Contrairement au cas non orienté, elle n'est pas symétrique.

Les matrices d'adjacences ont des propriétés intéressantes. On a calculé ci-dessous les matrices M2 et M3. Pour chacune de ces matrices, à quoi correspondent les nombres obtenus?

M2 =          M3 =

Listes d'adjacences

On peut aussi représenter un digraphe en donnant pour chacun de ses sommets la liste des sommets qu'on peut atteindre directement en suivant un arc (dans le sens de la flèche).

Exemple

Voici les listes d'adjacences du digraphe G:

1 : 2, 4, 6
2 : 4, 5
3 : 4
4 : 5
5 : -
6 : 2

Exercice

Décrivez le digraphe G ci-contre par une matrice d'adjacences et des listes d'adjacences.

Téléchargez ensuite le fichier Mathematica ci-dessous:

digraphe1.nb

et apprenez à dessinez un digraphe avec Mathematica!

Le corrigé est disponible, mais seulement pour les visiteurs autorisés!
Mot de passe :

Didier Müller, 2.2.03