1 -1 1 0 0 0 0 0 0 ”…1 0 0 1 1 -1 0 0 0 1 0 -1 1 -1 0 B 0 0 0 0 0 0 1 0 0 -10 0 0 0 e P2 关联矩阵具有以下性质： 1.e 1.每列只有两个非零元：1和-1。 2.第i行非零元的数目恰是结点的度，其中1元的数门是d*(,)、一1元的数凡是 d(,)。 3.能够表示重边，但不能表示自环。 类似地，尤向图也有其关联矩阵B,但其中不含一1元素。 例如图1.13的关联矩阵是 V: 111100000 100011100 01000111 0 B= 001000011 000110001J e」e:e3e4 es eo e ea eg 当邻接矩阵和关联矩阵能够表示某个图G时，这种表示 图1.1 是唯一的，而且十分直规。但由于它们不能表示重边或自环，因此这种表示有其局限性。特 别在使用计算机对某个图G进行运算时，采用邻接矩阵或关联矩阵作为输入形式将占据 较大的存储空间并可能增加计算复杂度。因此，为克服这些缺陷，再介绍图的另外儿种常 用表示方法。 1.2.4边列表 边列表是对关联矩阵的列进行压缩的结果。它由两个维向量A和B组成，当对G 的结点和边分别编号之后，若=(，v,),则A()=i,B()=j,即A(k)存放第是条边 始点编号，B()存放其终点编号。如果G是赋权图，则再增加-个m维向量Z,若：的权 是U,则令Z(k)二w。例如图1.14的边列表示形式是 A:(4412224) B:(1]22433) 2 C: 4 Z:(5346724) 图1.11 ·7