5.房闻的花图题图.6，问间是否存在 一条路过各门“次：试说明理由。 7.设(；有11道路.证明对任邀(G). (S的连通支数S11。 8.设；是n3的简单图.北明：若 n≥2n-1n-2)-r2. 您图2.6 则G存托H回路。 9.设：是有向完全图，此明(；中存在有向的哈密顿道路。 10.在例2.4.5中.若4证明这1个人定可以围成一圈，使相邻者互相认识。 1.设G是行m个结点的简单图，其最小度G)≥”，证明G中存在包含任意g 条互不相邻边的哈密顿回路， 12.对··个3×3×3的立方体，能否从…个角上开始，通过所有2？个1X1×1的小立 方块各】次，最后达到中心？试说明理由。 3.已知(G的权矩阵，用分支与界法求其旅行商问题的解 「0423352297 42 0 2638 49 33 26 0 3427 52 38340 35 29492735 0 14.-…个装置从原点出发，要分别在坐标(2,5)，(9,3)，(8,9)，(6,6)停留，然后返回原 点，设该装背只能沿X轴和Y轴行进，求最短的行进路线。 .某设备今后五年的价格预测分别是(5,5,6,7,8)，若该设备连续使用，其第(i= 1,2,…,5)年的维修费分别是（」，2,3,5,6），某单位今年购进一台，问如何使用可使5年里 总开支最小？ 16.分别求图a,的围邮路 (a) (6) 题图2.16 ·36·
17.,·项工程，其各工序所需时间与约束关系如下表，试用(a):PT图与(b):PFRT 图求其关键路径。并求工序3,5,10的允许延误时间如表： 18.请对Warshall算法进行适当修改.以便在计 工序号时间前序工疗 算道路矩阵后，可以查知任意两结点间具体的路径。 2 8 1,3 19.编程并搜紫出图2.13的全部不同的H问路， 3 3 1 20.试编写尤负长回路图的最短路径程序。 6 3 21,编写求PERT图关键路径及工序允许延误时 5 10 2,3 6 2,3 间的程序。 1 7 8 3 22.编写用分支与界法求旅行商问题的程序。 8 6,7 23.用近似算法求权矩阵如下的旅行商问题，并与 9 5.8 程序运行结果比较。 10 6,7 X 423352 29 451 2 ×26 38 49 36 33 26× 34 27 43 52 38 34 x 35 30 29 49 27 35 41 L45 36 43 30 41 ·37
第三章 树 3.1树的有关定义 给定…个图G=(,E),如果它不含任何回路，我们就叫它是林，如果G又是连通 的，即这个林只有一个连通支，就称它是树，树是图论中最重要的概念之一，在自然科学和 社会科学的许多领域都有广泛的应用 例3.1、1网球单打比赛前，当抽签之后为说明各选手问的相遇情况，往往画·张 图，形如图3.1。它是-·棵树。 例3.【.2中子轰击原子核时产生的裂变过程，也可以形象地用图3.2示意，它也是 一棵树。 图3.1 图3.2 定义3.1.1一个不含任何回路的莲通图称为树，用T表示。T'中的边称为树枝，度 为1的结点称为树叶。 树的每条边都不会属于任何回路。这样的边叫割边， 定义3.1.2设e是G的一条边，若G心=G一e比G的连通支数增加，则称e是G的 一条割边。 显然、图G删去割边e二(u,)之后，结点和分属于不同的连通支。 定理3.1.1e=(u,v)是割边，当且仅当e不(；的任何回路。 证明：若e=(u,v)属于G的某个回路，则侧G=e中仍存在“到v的道路，故结点h 和v属于同-连通支，e不是割边。反之，若e不是割边.则（与G的连通支数一样。于是 u和v仍属于同一连通支。故G中存在道路P(u,),P(H,v)+e就是G的一个回路。 下面我们给出树的等价定义。 定理3.1.2设T是结点数为n≥2的树，则下列性质等价： 1.T连通且无回路。 2.T连通且每条边都是割边。 3.T'连通且有n-1条边。 4.T有n一1条边且无回路。 5.T的任意两结点间有唯一道路。 ·38·
6.T无回路，但在任两结点间加上一条边后恰有一个回路。 证明： 1→2T无回路，即T的任意边e都不属于回路，由定理3.1.1“是割边。 2+3对结点数n进行归纳。令n(T),m(T)分别表示树T的结点数与边数、当n= 2时命题成立，设n≤k时，m(T')=n(T)一】成立。则n=k十1时，由于任-…边e都是刷边， 故G=G一e有两个连通支1'：，T'。由于n(1:)≤k,i一1,2，故m(T,)=n(I)…1。所以 m(T)=n(T)-1也成立。 3→4假定T有回路，设C是其中-·条含有(<n)个结点的初级回路，因为”连 通，所以V(T)一V(C)中一定有结点4与C:上某点飞相邻，即存在边(u,)∈(1)，依此 类推，最终V(T)一V(C)中的n-个结点需要n·条边才可能保持T连通.代，上(f一 上(C)!一n-1一k<n一k。矛盾。 4-→5设，口是T'的任意两结点，先证道路P(u)的仟在性。如果个存在P(,x). 则，x属于不同连通支T、Tz。由m(T)=-1,则至少有·个支，比则T,使n(T:? m(T)成立。这样T,亦即T中有回路。反之，若T无回路，则因为各连通支药有m(1) ≤n(T,)-1,从而使m(T)<n一1。均产生矛盾，因此P(,v)一定存在。再证唯-一性。.若 存在两条不同的道路P(u,e),P(u,),则其对称差P(u,v)⊕P(“,)至少含有·个 路。故而得证。 ·5→6,6→1均显然。因此等价定理得证。 定理3.1.2对判断和构造树T将带来很大方便。 定理3.1.3树T中一定存在树叶结点。 证明：由于T是连通图，所以任一结点∈V(T'),都有()≥1.若无树叶，聊d(t,) ≥2。这样1-1=m=合∑d(,)≥n。矛盾. 定义3.1.3如果T是图G的支撑子图，而且又是… 棵树，则称T是G的一棵支撑树，或称生成树、义简称为G 的树。 比如图3.3的粗线边构成了(G的棵支撑树T。显然 G有支撑树的充要条件为G是连通图，附且如果连通图(： 本身不是树，那么它的树不唯一，例如图3.3中还有许多不 同的支撑树。给定图G的一棵树T,我们称(-T,即G啊 去T中各边后的子图为T的余树.用T表示。比如在图 3.3,E(T)=(e2es,ese3ec}。一般情况下，余树不是 利3. 棵树。 3.2基本关联矩阵及其性质 本节讨论的对象是有向连通图G 正 定义3、2.1在有向图连通G一(V,E)的关联矩阵B中划去任意结点w所对应 ·39·
的行，得到一个(n一1)Xm的矩阵B·B。称为(：的”·个某木关联矩阵。 例如图3.3中结点所对应的基本关联矩阵是 1「1】00 0】 0 0 0 2一10-1 1 0 1 0 0 0 B。=Ts 0-11)0 -1 1 0 0 0 0-1-】 0 0 0 0 0 0(0」--1 1 0 -1 e e. f: g 基本关联知阵与G的支撑树之间有密切联系，我们首先：分析关联：阵的性：质， 定理3.2.1有向图G=(V,E)关联阵B的孔ranB<n。 证明：由于B中每列都只有1和-】两个非零元素、枚B的任意一1行加到第n行 上后，第n行为全零。即B的n个行问章线性相关，放B<, 定理3.2.2设B。是有向图G关联矩阵B的任意·k阶子方阵，则dt(Bn)为 0,1或一1。 证明：因为B。是B的某一k阶子阵，显然B。每列最多只有2个非零元。若其中某 列全为零元，则dt(Bn)=0;若B。每列都有2个非零元，显然也有det(B,)=0:否 则B,中存在只有1个非零元的列、按该列展开得到det(,)一{士det(B),但B,的 阶为k一1。依次类推，可知最终det(B,)或为0，或为1，或为-1。 定理3.2.3设B是有向连通图G的关联矩阵，姆ranB=n一1。 证明：由定理3,2.1知ranB<n,现只需证rnb≥n一1。不失一般性，设B中 最少的线性相关的行数为1，显然≤n,而且这1行分别结点℃()，v(2),…, (）相对应，因此有 kb(i1）+kb(i2)+…+kb(:)世0k年0，j=1,2,…,l (1) 由于矩阵B每列只有2个非零元，所以在这1个行向这(i,)中，其第t(t=1,2,…,m)个 分量最多只有2个为非零。当然也可能全为0，但是可以：不可能只有1个为非零，否 则，由于，≠0，式(1)不会成立。这样可以对矩阵B分别进行行、列交换，使前（行是线性 相关的诸行；这在1行中每列都有2个非然元的换前，列，其余m一r列它们全都是零 元。这样矩阵B变换为 P B'= 011 R Q小n…l r 但ranB±ranB,而且B依然是(，的…个关联矩，与：相比只是结点与边的编号不同 而已。若”一>0，由B可见，C至少分为2个连通支：其中条边贝与1个结点相关，而其 余m一r条边只与另外n一1个结点相关。这与(，是连通矛盾，因此一定有n一1=0，即 I=n,也就是说B中最少需要行才能线性相关.而任·」行都将线性无关，因此ra B≥n-1, 由此，我们立刻得到 定理3.2.4连通图C基木关联期陈的和rnB.-!, ·40·