关联矩阵表示结点与边之间的关联关系。一个图G的关联矩阵是n×m的矩阵，每个元素的值为：
　　　　　　　　　　　
　　图6.6.1矩阵的关联矩阵如下：
　　　　　　　　　　　

　　关联矩阵的特点是：
　　√ 每列只有两个非零元素：1或-1；
　　√ 第i行非零元素的数目恰好是结点vi的度；
　　√ 能够表示重边，但不能表示自环。

　　可以看到，关联矩阵是一个稀疏矩阵，压缩存储可望节省空间和减少计算量。