Matrices ou listes d’adjacence

Soit {G=(S,A)} un graphe (orienté ou non), avec {S=[\![ 0,n-1]\!] .}

On appelle matrice d’adjacence de {G} la matrice {M(}carrée d’ordre {n)} définie par {m_{i,j}=1} si {\left\{i,j\right\}} est une arête de {G} dans le cas non orienté (respectivement : si {(i,j)} est une arête de {G} le cas orienté) et 0 sinon.

Dans le cas non orienté, la matrice {M} est bien sûr symétrique.

Puisqu’aucun sommet ne boucle sur lui-même, les coefficients diagonaux de la matrice d’adjacence sont nuls.

Il est tout à fait possible de définir {M} comme une matrice de booléens (true pour 1, et false pour 0).

Voici un exemple de matrice d’adjacence pour un graphe orienté :

Formule du chapitre 13, page 2
Figure du chapitre 13, page 2

[|[| 0; 0; 0; 0; 1; 1; 0; 0 |]; [| 0; 0; 0; 1; 1; 0; 0; 0 |]; [| 1; 0; 0; 0; 0; 0; 0; 0 |]; [| 0; 0; 0; 0; 0; 1; 0; 0 |]; [| 0; 1; 0; 0; 0; 0; 0; 0 |]; [| 1; 0; 1; 1; 0; 0; 0; 0 |]; [| 0; 0; 0; 1; 0; 1; 0; 0 |]; 0 1 0 1 1 1 0 0 [| 0; 1; 0; 1; 1; 1; 0; 0 |]|]

{G_{1}:}graphe orienté à 8 sommets la matrice d’adjacence de {G_{1}} en OCaml, la matrice d’adjacence de {G_{1}}

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :