Matrices d'adjacence

I-B. Représentation des graphes

Matrices d'adjacence

La représentation par matrice d'adjacence consiste en l'utilisation d'une matrice carré ayant pour taille le nombre de sommets du graphe. Sur les lignes et les colonnes on trouve les nom des sommets. En général, on donne des numéros aux sommets, ce qui facilite la lecture.

Considérons la matrice M[n,n], le coefficient M(i,j) qui est le coefficient à l'intersection de la ligne i et de la colonne 1 peut prendre deux valeurs : soit 1 soit 0. Elle vaut 1 si l'arc (i,j) existe c'est à dire qu'il existe un arc reliant le sommet i au sommet j. Elle vaut alors 0 s'il n'y a pas d'arc.

Voici donc un exemple de graphe et de sa matrice d'incidence associée :

On remarque aisément qu'un graphe non orienté sera représenté par une matrice symétrique.

Si jamais on est en présence d'un graphe valué, la représentation change quelque peut.

Dans ce type de graphe, il suffit tout simplement de mettre dans le coefficient M(i,j) la valeur de l'arc (i,j). En revanche, il faudra faire attention puisque la valeur 0 peut être utilisée pour valuer le graphe. On utilisera alors une valeur spéciale pour indiquer qu'il n'y a pas de chemin. Quelque fois, il s'agit d'une valeur négative si les valuations sont toutes positives. D'une manière algorithmique, on pourrait utiliser la valeur infinie pour définir la non-existence entre deux sommets. La valeur sera donc choisie en fonction de l'application.

Voici un exemple de graphe valué et de sa matrice associée :

Listes d'adjacences

Une autre idée pour représenter les matrices en mémoire : les listes d'adjacences. Dans ce type de structure, on a un tableau de liste de sommet. Le tableau comporte autant de cases qu'il y a de sommets. Chacune des cases pointe vers une liste de sommet. Cette liste n'est rien d'autre que les successeurs du sommet considéré.

Voici un exemple de graphe et sa liste d'adjacence associée :

Pour un graphe valué, il faut mémoriser dans les noeuds de la liste la valeur du noeud. On peut donc avoir le graphe valué précédent et sa liste d'adjacence associée :

On peut se demander pourquoi il y a deux représentations pour les matrices. Cette explication est due principalement à un problème lié à l'informatique : l'espace de stockage. En effet, cet espace bien que de plus en plus important est toujours limité.

Pour une matrice d'adjacence, on constate que l'on stocke des informations dont on n'a pas besoin. En effet, on stocke toutes les liaisons possibles entre les sommets : les arêtes qui existent et même les arêtes qui n'existent pas. De plus, l'espace de stockage nécessaire est directement proportionnel

...