next up previous
suivant: Expression des matrices monter: Matrices associées aux graphes précédent: Matrice d'incidence sommet-arc

Matrice d'adjacence sommet-sommet

C'est une matrice $ n\,\times\,n$ telle que $ a_{ij}=1$ pour tout arc $ (i,\,j)$ appartenant au graphe, tous les autres éléments étant nuls. Lorsqu'un graphe est dense, c'est à dire lorsque $ m$ est proche de $ n^2$, cette matrice constitue un moyen de stockage efficace au point de vue place mémoire mais elle s'avère délicate à utiliser algorithmiquement. Cette matrice s'adapte bien au cas des graphes non simples, il suffit de prendre $ a_{ij}$ égal au nombre d'acrs d'origine $ i$ et de destination $ j$. Dans le cas non orienté, la matrice d'adjacence est symétrique. Il suffit de poser $ a_{ij}$ égal au nombre d'arêtes entre $ i$ et $ j$.

Bruno Garcia 2000-12-17