景1.4最短路及其算法 13 T2={a}: (4)②A2={a,},b2=0,b82=2; (5)③m2=1,a3=v,t(y)=t(a)+l(a)=2(最小)， Tg={a,a0}: (6)②Ag={a,},b》=2,b》=2,b}》=u4 (7)③m=3,a4=u4,(w4)=t()+l(u4)=3(最小)， T4={a,a,hu4}; (8)②A={a,h,h,w4},b=2,b0=2,b0=2,b0=5; (9)③m4=4,a5=5,t(5)=t(u4)+l(u5)=6(最小)， Ts=(avs,avn,vu,uvsi (10)②A5={,边，,w4,},b=，b=,b=,b=2, b=2; (11)③ms=4,t(h)=t(u)+l(u)=7(最小)， T6={a防，a功，h4,u5,u42}; (12)②A6={a,h功，西，5,2}，b=6,b=b,0=%,b=%； (13)③ms=6,a7=6,t(6)=t(2)+l(2%)=9(最小)， T,={a内，a,u,45,42,s}; (14)②A,={a,h,%},b”=b,b”=b,b97=b (15)③m=7,ag=b,t(6)=t(%)+l(%b)=11(最小)， T8={a,a,h4,w5,4h,26,sb} 于是知a与b的距离 d(a,b)=tb)=11. 由T导出的树中a到b路av1u次sb就是最短路 称一个图论算法是好的，如果在任何一个具有m条边的n阶图G上 施行这个算法所需要的计算步数都可由n和m的一个多项式（例如 3n2m)为其上界.一个算法的施行若需要指数步数（例如2"），则对某些大 的图而言，它将是十分无效的. 因为Dantjig算法总共需要作n(n一1)/2次加法和n(n一1)次比较， 故Dantjig算法是一个好算法， 动态规划是Bellman于20世纪50年代作为多阶段决策过程而研究 出来的.动态规划的关键，在于所谓的Bellman最优原理的应用，这个原 理归结为用一个基本的递推关系式使过程连续地转移.求这类问题的 解，要按倒过来的顺序进行，即从最终状态开始到起始状态为止.作为粗 浅介绍，我们来考虑一个特殊的序贯决策问题.规定的赛车方法是：选手 都从S站出发，到F站终止（如图1-14），比赛路分四段，虽然第四阶段
14 第一章图的基本概念 即最后一段选手们必到达F站. 但在第一、第二与第三段选手们可 以选择不同的站.比如，一开始选 手们可以过P站或Q站：其后可 选择P2站或Q2站，以此类推。选 手们的目的是，经过一系列检查 站，在最短的时间里跑完由S到F 图1-14 的路程.我们看到，司机对可能的 道路条件等因素的估计，要连续做出三个决策来，通过检查站P或Q的 决策分别用p,q表示.显然，由组合学知，从S到F有8个可能的路线 每条路线要相加3次，总共需要相加24次.一般说来，若是n段，对于我 们这类问题，就需要相加(n一1)2-1次.故这个策略是不可取的. 让我们来考察另一种发现从S到F的最优路程的方法.我们从最后 一段开始，在两个检查站P,与Q算出从该检查站到终点F的可能的最 小“代价”.代价用V来表示，其实就是行车时间.实际上，在这个例题 中，最后一段没有选择的余地；从P起始V,(4)=4,而V。(4)=3.其次 我们来考查在检查站P2的决策。有两个方案可供选择： 路径P2PF,V=1+V(4)=5, 路径P2QF,V=1+V,(4)=4. 后一条路径更快一些，因此我们记下：从P2到F的最短时间或称最小代 价为V,(3)=4.从而把P2处的决策q储存起来，对于以后的应用可能更 方便些.但是为了简单起见，我们只留下两个数据中的绝对极小值并记 在V,(3)上.用同样的方法我们算出V,(3)=5,以此类推.综合起来列 表如下： 表1-2赛车的代价及最短时间 V,(2)=10 V,(1)=13 V,(3)=4 V,(4)=4 V,(2)=8 V,(3)=5 V,(4)=3 最后一次计算对应第一段，司机有两个选择： 路径SP1F=4+V,(2)=14, 路径SQF=5+V,(2)=13. 司机选择路径q,整个问题的最小代价是V,(1)=13.其最优路径是 SQP2QF,如图1-14的箭头所示. 上述计算，除了作一些二取一的决策之外，需要相加10次，对于n段 来说，则需要相加4(n一2)十2次.在10段的情况下，用第一种方法需要
§1.5图的代数表示及其特征 5 相加4608次.而用第二种方法只须相加34次，因此这种方法对于处理 多段决策过程是很有前途的. §1.5图的代数表示及其特征 一个图由它的邻接性或关联性完全决定，这种信息可以用矩阵很方 便地来表达.反之，将一个图适当地标定以后可在其上定义多个矩阵，比 如邻接矩阵，关联矩阵等，常常可以利用这些矩阵，将一个图的某几种性 质统一考虑 一、邻接矩阵 有n个点的一个标定图G的邻接矩阵A=(a)是一个n×n矩阵，其中， 如果邻接巧则a,=1,否则a,=0.于是在有n个点的简单标定图与对角 线元素为零的n阶对称二元矩阵（其中元素取值为0和1）之间是一一对应的 关系（注：若α，取为连接贴与y的边数，则称A为推广的邻接矩阵）， (01101 10100 11010 00101 (10010 图1-15 图1-15中给出了一个标定图G,它对应的邻接矩阵为A.一个直接 结果是：A的各行元素之和是G的各个点的度.一般地，因为图与矩阵之 间的对应，所以图论中的多数概念都能被反映到邻接矩阵中来.例如，我 们说一个图是连通的当且仅当不存在G的点的一个划分V=V1UV2,使 得没有一条边联结V1的一个点与V,的一个点.用矩阵的语言，我们可 以说：G是连通的当且仅当没有G的点的一种标定法使它的邻接矩阵有 约化的形式 A- 0A22J 其中，A:是方阵.另外，若A1和A2是相应于同一个G的两种不同的标定 的邻接矩阵，则存在某一个置换矩阵P有 A=P-A2P
16 第一章图的基本概念 当然，也有与标定法无关的图的性质，例如在下列解释邻接矩阵的幂的元 素的结果中就是如此。 定理10令G是一个有推广的邻接矩阵A的p阶标定图，则A的i 行j列元素a等于由y:到v,的长度为n的通道的数目. 证明n=0时，A°=I(n阶单位矩阵)，从任一点v,到自身有一条 长度为零的通道，任何不同的两点间没有长度为零的通道，从而命题对 n=0时成立. 今设命题对n成立，由A+1=AA",故 由于a.是联结v,和v的长度为1的通道的数目，a是联结v和v,的 长度为n的通道的数目，所以右边每项表示由经过一条边到：再经过 一条长度为n的通道到v;的总长度为n十1的通道的数目，对所有的k 求和，即得a+”是所有联结v:与v,的长度为n十1的通道数目，于是命 题对n十1成立 ◇ 推论设A为简单图G的邻接矩阵，则 (I)A2的元素a是：的度数.A3的元素a是含v:的三角形的数 目的两倍； (2)若G是连通的，对于i≠j,与v;之间的距离是使A"的a≠0 的最小整数n. 二、关联矩阵 定义无环图G的关联矩阵B=(b)是一个n×m矩阵，当点与 边e,关联时bg=1,否则b,=0. 在同构意义下，与邻接矩阵一样，关联矩阵决定了图G.事实上，B的 任何n一1行就可决定G,因为它的每一行是其余行的以2为模的和.一 般说来，图的邻接矩阵比它的关联矩阵小得多，通常，图就以其邻接矩阵 的形式存贮于计算机中。 例1无环图1-16的关联矩阵为 es ez es es es es er (10001111 1100000 B=0110010. 00110014 图1-16 0001100%
81,5图的代数表示及其特征 三、邻接代数 图G的邻接矩阵的各个复系数的多项式在通常的矩阵运算法则 下构成一个有限维的线性空间，它也是一个代数，称为图G的邻接代 数，记为△(G),用图G的点数和直径可以给出邻接代数A(G)的维数 的界. 定理11n阶连通图G的邻接代数的维数有 d(G)+1≤dim△(G)≤n. 证明为证左边的不等式，只需证A°=I.,A'=A,A2,.,A⊙是线 性无关的即可.其中A是G的邻接矩阵. 记d(G)=d,不妨设d(,4+)=d(G),且2.va+1是G中联接 v1和a+1的一条最短路，d<n.于是有d(0,y)=j-1(G=1,2,., d十1).不难看到A中的元素a岁在k<一1时为零，而a”>0. 若存在一个线性组合 而b又不全为零.不妨设b-1是下标最大的非零系数，j一1≤d.考虑上 式左边的1行j列元，得 （2,=6g"≠0， 得到矛盾.故A°，A',.,A是线性无关的. 对于右边的不等式，可由Cayley定理得到.事实上，因A是n阶方 阵，故它的特征方程是 1M。-A=λ"+aoλ-1+.+am-1A十a°=0， 其中In为单位矩阵，由于系数不全为零（至少1”的系数为1），故A”, Am-1,.,A,A°=Ln是线性相关的，故得右边不等式. ▣ 由定理6知，具有m条边的简单图G有2个子图（包括G本身和空 图).设G,G2,.,G,N=2m是G的全部子图. 定理12集合M={G,G2,.,Gw},N=2m在对称差△运算与数乘 运算 0·G,=,1·G=G,G∈M 下构成数域F={0,1}上的一个m维线性空间. 证明首先M对对称差运算是封闭的.这是因为G:△G,是由除去 G,和G,中的所有公共边（连同它们关联的顶点）组成的一个子图，且对 称差运算满足交换律和结合律