1.4 邻接矩阵

完全描述一个网络需要记录下它的所有链接。实现这一目标的最简单方式是使用列表列出所有的链接。例如，图1-2中的网络可以通过列出其全部4个链接来进行唯一刻画：{(1,2),(1,3),(2,3),(2,4)}。从数学角度考虑，我们经常使用邻接矩阵来表示网络。一个拥有N个节点的有向网络，其邻接矩阵有N行N列，邻接矩阵的元素定义如下：如果存在一个链接从节点j指向节点i，则Aij=1；如果节点i和节点j彼此不相连，则Aij=0。

对于无向网络，每个链接对应邻接矩阵中的两个元素。例如，链接（1,2）对应着A12=1和A21=1。因此，无向网络的邻接矩阵是对称的，即Aij=Aji（图1-5b）。

节点i的度ki可以从邻接矩阵的元素中直接得到。对于无向网络，一个节点的度是邻接矩阵中相应行或列中所有元素之和，即：

对于有向网络，邻接矩阵中一行元素之和及一列元素之和分别对应着节点的入度和出度，即：

对于无向网络，节点的入度和节点的出度相等，我们有：

无向网络的邻接矩阵中非零元素个数为2L，即链接个数的2倍。实际上，连接节点i和节点j的一个无向链接对应着邻接矩阵中的两项：表示从节点j指向节点i的Aij=1和表示从节点i指向节点j的Aji=1（图1-5b）。

图1-5 邻接矩阵

（a）邻接矩阵元素的标记方式。

（b）无向网络的邻接矩阵。如图所示，一个节点（例如节点2）的度可以表示为邻接矩阵中相应行或列的元素之和。图中还展示了一些可以从邻接矩阵中得到的网络性质，例如链接总数L和平均度。

（c）有向网络的邻接矩阵。