f01110 00101 A=0101 0 0 0000 l 0.011 1.10 邻接矩阵A第；行非零元的数目恰是的正度，第j列非零元的数目是，的负度。 邻接矩阵可以表示自环，但无法表示重边。 无向图的邻接矩阵是一个对称矩阵，例如图1.1]的邻接矩阵是 011117 0 01 1 A= 1101 0 0101 1011J 图1.11 1.2.2权矩阵 赋权图常用权矩阵A进行表示。其元素 w,(,）∈E。 a,= 0. 其它。 例如图1.5的权矩阵是 [0 3 62 41 3 0 4.20 A= 64.2 0 3 2 0 3 0 7 4 5 0 70 1.2.3 关联矩阵 关联矩阵表示结点与边之间的关联关系。 有向图G的关联矩阵B是n×m的矩阵，当给定结点和边的编号之后，其元素 1, e,r(4)∈E。 b=一1， e,=(ts,)∈E。 0 其它， 例如图1.12的关联矩阵是 6·
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
类似地可以得到无向图的边列表，比如图1.15的边列表是 A:(111223) T B:(442434) Z:(534724) es 图1.1d 1.2.5正向表 正向表是对邻接矩阵的行进行压缩的结果。它的特点是将每个结点的直接后继集中 在起存放。有向图的正向表由一个(n+1)维向量A,一个m维向量B组成。当对G的 结点编号之后，A()表示结点，的第一个直接后继在B中的地址，B中存放这些后继结 点的编号，A(n+1)=m十1。如果G是赋权图，则再设晋一个m维向量Z,用以存放相应 的权值。例如图1.14的正向表是 A 12558 B2234311 z4627453 在正向表中存在下述关系： 1.d(u,)=A(i+1)-A(i) 2.A()= ) 1 3.从B(A())到B(A(i+1)-1)的任一个值，都是：的直接后继。· 由于无向图的边没有方向性，所以B中存放的是相应邻接点的编号，因而B和Z都 要扩充为2m维的向量。例如图1.15的正向表是 A147913 B442134241123 Z534427245374 1.2.6逆向表 与正向表相反，逆向表是对有向图邻接矩阵的列进行压缩的结果。它的特点是将每个 ·8
结点的直接前趋集在一起存放。例如图1.14的逆向表是、 A135?8 B 4412242 534624? 1.2.7邻接表 这是采用单链表结构表示一个图。对每个结点：用一个表结点表示。在这里表结点 的结构如下 。6c 它共分二：个域，邻接点域α中任放该结点的编号，数据域b中存放相应边的数值，链 域c中存放下一个表结点的地址指针，以图1.11为例.它的邻接表形式如下 24 -26白-3234T? 一34-15-13 其中Q()存放结点，的第一个直接后继表结点的地址指针。邻接表的特点是使用灵活， 比如要从图G中删去某杀边时，只要摘除对应的表结点就以实现；若要增加某条边，也 只需增加…个表结点，而不需要进行大的变动。 边列表、正向表和邻接表等都能表示重边，也能表示自环，也就是说，它们都能唯一表 示任意·个图。而且也都只占据较小的存储空何。邻接矩阵、关联矩阵、边列表、正向表、 逆向表之间都可以互相转换。为了直观起见，本书主要采用邻接矩阵和关联矩阵表示图 (,在描述某些算法时，有时也采用正向表等形式的数据结构。 习题 一 1.证明在9座丁厂之间，不可能每座工厂都只与其它3座工“有业务联系，也不可 能以有4座工与偶数个厂有业务联系。 2.简单图G中，如果m>号(a一1)(2)，证明G不有在孤立结点。 3.完全图的每边任给一个方向，称为有向完全图。证明在有向完全图中 d(,2=d（)2。 EV 4.三个量杯容量分别是8升、5升和3升，现8升的其杯装满了水，问怎样才能把水 分成2个4升，画出相应的图。 ·9·
5.6个人围成圆形就座，每个人恰好只与相邻者不认识，是否可以重新入座，使每个 人都与邻座认识？ 6.证明9个人中若非至少有4个人互相认识，则至少有3个人互相不认识。 7.判断1.7图是否同构？ (a) (b) 题图1.7 8.写出题1.7图(a)的邻接矩阵、关联矩阵，边列表及正向表。 9.试编写有向图G的邻接炬阵与关联矩阵，邻接矩阵与正向表，关联矩阵与边列表 之间互相转换的程序。 ·10·