邻接矩阵

邻接矩阵，有时也称为连接矩阵，是一个矩阵，其行和列由图顶点标记，位置 中的值为 1 或 0，取决于 和 是否相邻。对于没有自环的简单图，邻接矩阵的对角线上必须为 0。对于无向图，邻接矩阵是对称的。

上面的图示显示了爪形图、环图 和完全图 的特定标记的邻接矩阵。

由于图的标签可以在不改变所表示的底层图的情况下进行置换，因此通常存在与给定简单图对应的多个可能的邻接矩阵。特别是，对于具有顶点计数 和自同构群阶数 的简单未标记图 ，不同邻接矩阵的数量 由下式给出

其中 是顶点标签的排列数。上面的图示显示了环图 的 个可能的邻接矩阵。

标记的 -有向图 的邻接矩阵是 阶的二进制方阵，其第 个条目为 1 当且仅当 是 的一条边时。

图的邻接矩阵可以使用 Wolfram 语言 计算，使用AdjacencyMatrix[g]，结果以稀疏数组形式返回。

有时定义了邻接矩阵的不同版本，其中对角线元素为 ，如果 和 相邻，则 ，否则为 （例如，Goethals 和 Seidel 1970）。

简单图的加权邻接矩阵 也可以为实正对称函数 定义，该函数在图的顶点度 上（Das et al. 2018, Zheng et al. 2022）。