Matrice et listes d'adjacences

Matrice d'adjacences

On peut représenter un graphe 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 que le sommet i est adjacent au sommet j.

Exemple

Voici la matrice d'adjacences du graphe G:

M = Cette matrice a 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. Elle est symétrique: mij = mji.

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 graphe en donnant pour chacun de ses sommets la liste des sommets auxquels il est adjacent.

Exemple

Voici les listes d'adjacences du graphe G:

1 : 3, 4, 5
2 : 3
3 : 1, 2, 4, 5
4 : 1, 3, 5
5 : 1, 3, 4

Exercices

Exercice 1

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

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

graphes.nb

Ce fichier vous montre comment dessiner le graphe ci-contre avec Mathematica. Lisez attentivement ce fichier et plongez-vous dans l'aide de Mathematica pour comprendre les fonctions prédéfinies utilisées.

Exercice 2

Inspirez-vous du fichier donné à l'exercice 1 pour dessiner les graphes suivants avec Mathematica:

a. b. c. d.

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

Didier Müller, 2.2.03