图论第一章课后习题解答

1、 图论及其应用习题课教材图论及其应用习题课教材 杨春编杨春编 电子科技大学应用数学学院电子科技大学应用数学学院 内容提要内容提要 本书主要对张先迪等编的研究生图论及其应用教材的习题进行解答。 该书可作为研究生图论教学的参考教材。 前前 言言 现实生活中，许多问题都可归结为一个由点和线组成的图形的问题。例如，由点代表车 站， 线代表铁路线的铁路网络图； 点代表路口， 线代表街道的城市交通图； 点代表管道接头， 线代表管道的自来水供水系统；点代表电路的结点，线代表结点间的电气元件的电网络图； 点代表网络的结点，线代表通讯线的通讯网络、计算机网络等等。图论正是研究这些由点和 线组成的“图形”问题的一

2、门学科。 图论起源于 18 世纪，其第一篇论文是由欧拉（Euler，17071782）于 1736 年所完成。 这篇论文解决了一个当时还没有解决的著名问题哥尼斯堡（Knigsberg）七桥问题（见第 四章） 。这篇论文也使欧拉成为了图论和拓扑学的创始人。图论诞生后，特别是近三十年来 发展十分迅速，应用也十分广泛。其应用已涉及物理学、化学、运筹学、计算机科学、信息 论、控制论、网络理论、社会科学、以及管理科学等诸多领域。由于图论与计算机科学紧密 相联系，近若干年来，在计算机科学、计算机网络的迅猛发展下，更拓展了图论的应用发展 空间。在计算机的许多领域内，它都占有一席之地。图论在矩阵论、群论等其它

3、一些数学分 支中，也有其重要的应用。 张先迪等编的图论及其应用一书精选了内容广泛、难度各易的习题，其中的大多数 习题都是对图论的进一步学习是应当掌握的。 本书依序将该书的重要内容摘要列出， 并将全 部习题给出了详细解答。本书所涉及到的术语、符号与该书一致。 有些习题存在多种解法，在一般情况下，只给出一种解法供参考。 由于编者水平有限及编写时间的匆忙， 书中难免出现一些缺点和错误， 恳请同行专家及 读者提出宝贵意见和建议，以使本书得以不断改进和完善。 编 者 20047 目 录 第一章 图的基本概念 1.1 图和简单图 1.2 子图与图的运算 1.3 路与图的连通性 1.4 最短路及其算法 1.

4、5 图的代数表示及其特征 1.6 极图 1.7 交图与团图 习题 1 第二章 树 2.1 树的概念与性质 2.2 树的中心与形心 2.3 生成树 2.4 最小生成树 习题 2 第三章 图的连通度 3.1 割边、割点和块 3.2 连通度 3.3 应用 3.4 图的宽距离和宽直径 习题 3 第四章 欧拉图与哈密尔顿图 4.1 欧拉图 4.2 高效率计算机鼓轮的设计 4.3 中国邮路问题 4.4 哈密尔顿图 4.5 度极大非哈密尔顿图 4.6 旅行售货员问题 4.7 超哈密尔顿图 4.8 E 图和 H 图的联系 4.9 无限图中的欧拉,哈密尔顿问题 习题 4 第五章 匹配与因子分解 5.1 匹配 5

5、.2 偶图的匹配与覆盖 5.3 Tutte 定理与完美匹配 5.4 因子分解 5.5 最优匹配与匈牙利算法 5.6 匹配在矩阵理论中的应用 习题 5 第六章 平面图 6.1 平面图 6.2 一些特殊平面图及平面图的对偶图 6.3 平面图的判定及涉及平面性的不变量 6.4 平面性算法 习题 6 第七章 图的着色 7.1 图的边着色 7.2 顶点着色 7.3 与色数有关的几类图 7.4 完美图 7.5 着色的计数，色多项式习题 2 7.6 List 着色 7.7 全着色 7.8 着色的应用 习题 7 第八章 Ramsey 定理 8.1 独立集和覆盖 8.2 Ramsey 定理 8.3 广义 Ram

6、sey 数 8.4 应用 习题 8 第一章 图的基本概念第一章 图的基本概念 1.1 图和简单图 1.1 图和简单图 定义 1定义 1 一个图 G 定义为一个有序对(V, E)，记为 G = (V, E)，其中 （1）V 是一个非空集合，称为顶点集或边集，其元素称为顶点或点； （2）E 是由 V 中的点组成的无序点对构成的集合，称为边集，其元素称为边，且同一 点对在 E 中可出现多次。 图 G 的顶点集也记为 V(G), 边集也记为 E(G)。顶点集和边集都有限的图称为有限图有限图。 只有一个顶点而无边的图称为平凡图平凡图。 其他所有的图都称为非平凡图非平凡图。 边集为空的图称为空 图 空 图

7、。图 G 的顶点数顶点数（或阶数阶数）和边数边数可分别用符号 n(G) 和 m(G)表示。连接两个相同顶点 的边的条数，叫做边的重数重数。重数大于 1 的边称为重边重边。端点重合为一点的边称为环环。既没 有环也没有重边的图称为简单图简单图。其他所有的图都称为复合图复合图。 边记为 uv，也可记 uv 为 e，即 e = uv。此时称 u 和 v 是 e 的端点，并称 u 和 v 相邻相邻， u (或 v)与 e 相关联相关联。若两条边有一个共同的端点，则称这两条边相邻。若用小圆点代表点， 连线代表边，则可将一个图用“图形”来表示。 定义 2定义 2 设有两个图 G1 = (V1, E1)和 G

8、2 = (V2, E2)，若在其顶点集合之间存在双射，即存 在一一对应的关系，使得边之间有如下的关系：设 12 uu， 12 vv， 111 ,u vV， 222 ,u vV； 1 11 u vE，当且仅当 222 u vE，且 1 1 u v的重数与 22 u v的重数相同，则称两图同 构，记为 G1G2。 定义 3 定义 3 每两个不同的顶点之间都有一条边相连的简单图称为完全图完全图。在同构意义下， n 个顶点的完全图只有一个，记为 n K。所谓具有二分类（X, Y）的偶图偶图（或二部图）是指一 个图，它的点集可以分解为两个（非空）子集 X 和 Y， ，使得每条边的一个端点在 X 中，另

9、一个端点在 Y 中；完全偶图完全偶图是指具有二分类（X, Y）的简单偶图，其中 X 的每个顶点与 Y 的 每个顶点相连，若|X|=m，|Y|=n，则这样的偶图记为 ,m n K。对于一个简单图 G =（V, E） ，令 集合 1 , ,Euv uv u vV，则图 H =（V，E1E）称为 G 的补图补图，记为HG。 定理 1 定理 1 若 n 阶图 G 是自补的（即GG） ，则 n = 0, 1（mod 4） 。 定义 4定义 4 G 的顶点 v 的度 d(v)是指 G 中与 v 关联的边的数目， 每个环计算两次。 用 G 和 G分别表示 G 的顶点的最小度最小度和最大度最大度。为方便，奇数

10、度的顶点称为奇点奇点，偶数度 的顶点称偶点偶点。 设 G = (V, E)为简单图， 如果对所有vV， 有 d(v) = k， 称图 G 为k k-正则图-正则图。 完全图和完全偶图 ,n n K均是正则图。 定理 2定理 2 图 G= (V, E)中所有顶点的度的和等于边数 m 的 2 倍，即 Vv vd)(=2m 推论 3 推论 3 在任何图中，奇点个数为偶数。 推论 4推论 4 正则图的阶数和度数不同时为奇数。 定义 5定义 5 一个图 G 的各个点的度 d1, d2, dn构成的非负整数组 (d1, d2, dn)称为 G 的 度序列。 若对一个非负整数组(d1, d2, dn)， n

11、 i i d 1 =2m， 存在一个简单图 G， 以它为度序列， 则称这个数组是可图可图的。 定理 5定理 5 设有非负整数组 = (d1, d2, dn)， 且 n i i d 1 =2m 是一个偶数， n-1d1d2 dn，它是可图的充要条件为 = (d2-1, d3-1, 21 11 , 1 dd dd, dn) 是可图的。 定理 6定理 6 一个简单图 G 的 n 个点的度不能互不相同。 定义 6 定义 6 设 n 阶图 G 的各点的度取 s 个不同的非负整数 d1,d2, ds。又设度为 di的点有 bi个 (i = 1,2,s)，则有 s i i b 1 = n。故非整数组(b1,

12、b2, bs)是 n 的一个划分，称为 G 的频序 列。 定理 7定理 7 一个 n 阶图 G 和它的补图G有相同的频序列。 1.2 子图与图的运算1.2 子图与图的运算 定义 1定义 1 如果 V HV G， E HE G， 且 H 中边的重数不超过 G 中对应边的 重数，则称 H 是 G 的子图，记为HG。有时又称 G 是 H 的母图。 当HG，但HG时，则记为HG，且称 H 为 G 的真子图真子图。G 的生成子图生成子图是 指满足 V(H) = V(G)的子图 H。 假设 V 是 V 的一个非空子集。以 V 为顶点集，以两端点均在 V 中的边的全体为边集 所组成的子图，称为 G 的由 V

13、 导出的子图，记为 G V ；简称为 G 的导出子图导出子图，导出子图 GV V 记为G V ； 它是 G 中删除 V 中的顶点以及与这些顶点相关联的边所得到的子图。 若 V = v, 则把 G-v简记为 Gv。 假设 E 是 E 的非空子集。以 E 为边集，以 E 中边的端点全体为顶点集所组成的子图 称为 G 的由 E 导出的子图，记为G E；简称为 G 的边导出子图边导出子图，边集为E E的 G 的 导出子图简记为G E 。若 Ee ，则用 Ge 来代替 G-e。 定理 8定理 8 简单图 G 中所有不同的生成子图（包括 G 和空图）的个数是 2m个。 定义 2 定义 2 设 G1，G2是

14、 G 的子图。若 G1和 G2无公共顶点，则称它们是不相交不相交的；若 G1 和 G2无公共边，则称它们是边不重边不重的。G1和 G2的并图并图 G1G2是指 G 的一个子图，其顶点 集为 V(G1)V(G2)，其边集为 E(G1)E(G2)；如果 G1和 G2是不相交的，有时就记其并图为 G1+G2。类似地可定义 G1和 G2的交图 G1G2，但此时 G1和 G2至少要有一个公共顶点。 G1和 G2的差差 G1-G2是由 G1中去掉 G2中的边组成的图。G1与 G2的对称差对称差 G1G2是 G1和 G2的并中去掉 G1与 G2的交所得到的图，即 G1G2 = (G1G2)-(G1G2) =

15、 (G1-G2)(G2-G1) 定义 3 定义 3 在不相交的 G1和 G2的并图 G1+G2中， 把 G1的每个顶点和 G2的每个顶点连接 起来所得到的图称为 G1和 G2的联图，记为 G1G2。 定义 4定义 4 设 G1= (V1, E1)，G2 = (V2, E2)，对点集 V = V1V2中的任意两个点 u = (u1,u2)和 v = (v1,v2)，当(u1 = v1和 u2 adj v2) 或 (u2 = v2和 u1 adj v1) 时就把 u 和 v 连接起来所得到的图 G 称为 G1和 G2积图，记为 G = G1G2。其中 ui adj vi表 ui 和 vi邻接。 1

16、.3 路和连通性 1.3 路和连通性 定义 1定义 1 G 的一条途径途径（或通道通道或通路通路）是指一个有限非空序列 w= v0 e1 v1 e2 v2ek vk， 它的项交替地为顶点和边，使得对1ik ， i e的端点是 1i v 和 i v。称 w 是从 v0到 vk的一 条途径，或一条（v0, vk）途径。顶点 v0和 vk分别称为 w 的起点起点和终点终点，而 v1, v2, vk-1称 为它的内部顶点。整数 k 称为 w 的长长。在简单图中，途径可简单地由其顶点序列来表示， 即 w= v0 v1 v2 vk。 若途径 w 的边 e1, e2, ek互不相同，则 w 称为迹迹；这时

17、w 的长恰好是 m(w)。又若途 径 w 的顶点 v0, v1, vk也互不相同，则 w 称为路路。 G 的两个顶点 u 和 v 称为连通的连通的，如果在 G 中存在（u, v）路。规定 u 和 u 是连通的。 如果对 G 中每一对顶点 u，v 都有一条（u, v）路，则称 G 为连通图连通图，否则称为非连通图非连通图。 连通是顶点集 V 上的一个等价关系，于是可将 V 划分为一些等价类。设 V 的所有不同的等 价类为 V1, V2, Vk, 这样， 两个顶点 u 和 v 是连通的当且仅当它们属于同一子集 Vi， 称子图 GV1, GV2, GVk为 G 的连通分支连通分支，简称分支分支或支支

18、。记 G 的分支个数为(G)。于是 G 是连通图当且仅当(G) =1。 定理 9定理 9 若图 G 是不连通的，则G是连通图。 定义 2定义 2 称一条途径是闭的闭的，如果它有正的长且起点和终点相同。闭迹也称为回路回路。 若一条闭迹的起点和内部顶点互不相同，则称它为圈圈。长为 k 的圈称为k k圈圈；按 k 是奇数还 是偶数，称 k 圈是奇圈奇圈和偶圈偶圈。3 圈常称为三角形。联结 u 和 v 中长度最短的途径之长度， 称为 u 与 v 的距离，记为 d(u, v)。称 d(G) = max d(u, v) | u, vV为 G 的直径直径。 定理 10定理 10 一个图是偶图当且当它不包含奇

19、圈。 1.4 最短路及其算法 1.4 最短路及其算法 定义 1定义 1 对 G 的每一条边 e，可赋以一个实数 w(e)，称为 e 的权权。G 连同它边上的权称 为赋权图赋权图。若 H 是赋权图的一个子图，则 H 的权 W(H) = )( )( HEe ew。赋权图中路 P 的长定 义为 W(P)，距离 d(u, v)仍定义为最短(u, v)路的长。在一个赋权图中找出某类具有最小（或 最大）权的子图，其中之一就是最短路问题最短路问题 最短通路算法最短通路算法 1. 记 a = a1，t(a1) = 0，A1 = a1，T1 = 。 2. 若已得到 Ai=a1, a2, ai，且对1ni，已知

20、t(an)，对每一个 anAi，求一点 ii nnin bN aAB 使 )(min)( )( )( valbal n Bv i nn i n 其中 N(an)是与 an邻接的所有的点的集合，又称为点 an的邻域邻域或邻集邻集。 3. 设有,1 ii mmi，而 i i m b使 iii i mmm t al a b取最小值，令 1 )( i i m ab i ，t(ai+1) = )( i m at+)( 1i i m aal，Ti+1 = Ti 1ima a i 4. 若 ai+1 = b，停止。否则，记 Ai+1 = Ai ai+1 回到第二步。 1.5 图的代数表示及特征 1.5 图的

21、代数表示及特征 定义 1 定义 1 有 n 个点的一个标定图 G 的邻接矩阵 ij Aa是一个 nn 矩阵， 其中， 如果 i v 邻接 j v则1 ij a ，否则0 ij a 。 定理 12定理 12 令 G 是一个有邻接矩阵 A 的 p 阶简单标定图，则 n A的 i 行 j 列元素 n ij a等于 由 i v到 j v的长度为 n 的通道的数目。 推论 13推论 13 设 A 为简单图 G 的邻接矩阵，则（1） 2 A的元素 )2( ii a是 i v的度数。 3 A的元 素 3 ij a是含 i v的三角形的数目的两倍。 （2） 若 G 是连通的， 对于ij， i v与 j v之间

22、的距离是使 n A的 0 n ij a的最小整数 n。 定义 2定义 2 无环图G的关联矩阵 ij Bb是一个nm矩阵， 当点 i v与边 j e关联时1 ij b ， 否则0 ij b 。 定义 3定义 3 图 G 的邻接矩阵的各个复系数的多项式在通常的矩阵运算法则下构成一个有 限维的线性空间，它也是一个代数，称为图 G 的邻接代数，记为(G)。 定理 14定理 14 n 阶连通图 G 的邻接代数的维数有 d(G)dim(G)n 定理 15定理 15 集合 M = G1, G2, GN, N =2m在对称差运算与数乘运算 0G i=, 1G i = G i , G i M 下构成数域0,1F

23、上的一个 m 维线性空间。 定理 16定理 16 设 G 为 n 阶连通图，则邻接矩阵 A(G)的不同特征值数目 s 满足不等式 d(G)+1sn 定理 17定理 17 设 A(G)的谱为 Spec A(G) = s s mmm 21 21 ，则 s i ii m 1 2 =2m 其中 mi是特征值i的重数，m 为 G 的边数。 定理 18定理 18 设是 A(G)的任一特征值，则 | n nm) 1(2 1.6 极图极图 定义 1定义 1 若简单图 G 的点集 V 有一个划分 V= l i i V 1 ，ViVj = ij 且所有 Vi非空，Vi内的点均不连通，则称 G 是一个l l部图部图

24、。 定义 2定义 2 如果在一个 l 部图 G 中， ii Vn，任何两点, ij uV vV ij, i,j=1,2, l 均邻接，则称 G 为完全 l 部图。 定义 3定义 3 如果在一个 n 个点的完全 l 部图 G 中， n = k n + r 0r3 个点的连通图， 则当且仅当 G 中没有三角形时，(G) = m。 定理 29定理 29 对于任何一个 n4 个点的图 G， (G)4 2 n 定义 3 定义 3 简单图 G 的一个团团是指 V 中的一个子集 1 V，使 1 G V是完全图。一个给定的 图 G 的团图团图是 G 的团的族的交图。 定理 30定理 30 一个图 G 是一个团

25、图当且仅当它含有完全子图的一个族 F，它们的并是 G， 且如果 F 的某个子族 F 中每一对完全子图的交非空，则 F 的所有元素的交就非空。 习习 题题 1 1. 证明在 n 阶连通图中 （1） 至少有 n-1 条边。 （2） 如果边数大于 n-1，则至少有一条闭通道。 （3） 如恰有 n-1 条边，则至少有一个奇度点。 证明证明 (1) 若对vV(G),有 d(v)2,则：2m=d(v)2n mnn-1,矛盾！ 若 G 中有 1 度顶点，对顶点数 n 作数学归纳。 当 n=2 时，G 显然至少有一条边，结论成立。 设当 n=k 时，结论成立， 当 n=k+1 时，设 d(v)=1，则 G-v

26、 是 k 阶连通图，因此至少有 k-1 条边，所以 G 至少有 k 条边。 (2) 考虑 v1v2vn的途径，若该途径是一条路，则长为 n-1,但图 G 的边数 大于 n-1,因此存在 vi,vj,使得 viadgvj,这样， vivi+1vj并上 vivj构成一条闭通道； 若 该途径是一条非路，易知，图 G 有闭通道。 (3) 若不然，对vV(G),有 d(v)2,则：2m=d(v)2n mnn-1,与已知矛盾！ 2. 设 G 是 n 阶完全图，试问 （1） 有多少条闭通道？ （2） 包含 G 中某边 e 的闭通道有多少？ （3） 任意两点间有多少条路？ 答答 (1) (n-2)! (2)

27、(n-1)!/2 (3) 1+(n-2)+(n-2)(n-3)+(n-2)(n-3)(n-4)+(n-2)1. 3. 证明图 1-27 中的两图不同构： 证明证明 容易观察出两图中的点与边的邻接关系各不相同，因此，两图不同构。 4. 证明图 1-28 中的两图是同构的 证明证明 将图 1-28 的两图顶点标号为如下的(a)与(b)图 图 1-27 图 1-28 作映射 f : f(vi)ui (1 i 10) 容易证明，对vivjE(a),有 f(vivj)uiujE(b) (1 i 10, 1j 10 ) 由图的同构定义知，图 1-27 的两个图是同构的。 5. 证明：四个顶点的非同构简单图

28、有 11 个。 证明证明 m=0 1 2 3 4 5 6 由于四个顶点的简单图至多 6 条边，因此上表已经穷举了所有情形，由上表知：四个顶 点的非同构简单图有 11 个。 6. 设 G 是具有 m 条边的 n 阶简单图。证明：m = 2 n 当且仅当 G 是完全图。 证明证明 必要性 若 G 为非完全图， 则 vV(G),有 d(v) n-1 d(v) n(n-1) 2mn(n-1) m n(n-1)/2= 2 n , 与已知矛盾！ 充分性 若 G 为完全图，则 2m= d(v) =n(n-1) m= 2 n 。 7. 证明： （1）m(Kl,n) = ln， （2）若 G 是具有 m 条边的

29、 n 阶简单偶图，则 m 4 2 n 。 证明证明 (1) Kl,n的总度数为 2ln,所以，m(Kl,n) = ln。 (a) v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 u1 u2 u3 u4 u5 u6 u7 u8 u9 u10 (b) (2) 设 G 的两个顶点子集所含顶点数分别为 n1与 n2,G 的边数为 m,可建立如下的二 次规划： m=n1n2 s.t n1+n2=n n11, n2 1 当 n 为偶数时，n1=n2=n/2 时，m 取最大值：m=n2/4 当 n 为奇数时，取 n1=(n+1)/2, n2=(n-1)/2 时，m 取最大值：m=(n2-1)/

30、4 所以，m 4 2 n 。 8. 设和是简单图 G 的最大度和最小度，则2m / n。 证明证明 n m n m nvdm n m nvdm Vv Vv 2 2 )(2 2 )(2 9. 证明：若 k 正则偶图具有二分类 V= V1V2，则 | V1| = |V2|。 证明证明 由于 G 为 k 正则偶图，所以，k V1 =m = k V2 V1= V2 。 10. 证明： 由两人或更多个人组成的人群中， 总有两人在该人群中恰好有相同的朋友数。 证明证明 将人用图的顶点表示，图的两顶点邻接当且仅当人群中的两人相认识，于是，问题 转化为：证明在任意一个简单图中必有一对度数相等的顶点。 若图 G

31、 为连通单图，则对vV(G),有 1d(v)n-1,因此，n 个顶点中必存在两个顶点，其 度数相同；若 G 为非连通图，设 G1为阶数 n1的连通分支，则vV(G1),有 1d(v)n1-1，于 是在 G1中必存在两个顶点，其度数相同。 11. 证明：序列 (7,6,5,4,3,3,2) 和 (6,6,5,4,3,3,1) 不是图序列。 证明证明 由于 7 个顶点的简单图的最大度不会超过 6，因此序列 (7,6,5,4,3,3,2) 不是图序 列； (6,6,5,4,3,3,1)是图序列 （5，4，3，2，2，0）是图序列，然（5，4，3，2，2，0）不是 图序列，所以(6,6,5,4,3,3

32、,1) 不是图序列。 12. 证明：若2，则 G 包含圈。 证明证明 只就连通图证明即可。设 V(G)=v1,v2,vn,对于 G 中的路 v1v2vk,若 vk与 v1 邻接，则构成一个圈。若 vi1vi2vin是一条路，由于 2，因此，对 vin，存在点 vik与之邻接， 则 vikvinvik构成一个圈 。 13. 证明：若 G 是简单图且2，则 G 包含长至少是+1 的圈。 证明证明 设 v0v1vk为 G 中一条最长路，则 v0的邻接顶点一定在该路上，否则，与假设矛 盾。现取与 v0相邻的脚标最大者，记为l，则l,于是得圈 v0v1v2vlv0,该圈长为l+1，显 然不小于+1。 1

33、4. G 的围长围长是指 G 中最短圈的长；若 G 没有圈，则定义 G 的围长为无穷大。证明： （1） 围长为 4 的 k 的正则图至少有 2k 个顶点，且恰有 2k 个顶点的这样的图（在同 构意义下）只有一个。 （2） 围长为 5 的 k 正则图至少有 k2+1 个顶点。 证明证明 (1) 设 u,v 是 G 中两相邻顶点，则 S(u)S(v)=,否则，可推出 G 中的围长为 3，与 已知矛盾。 因此， G 中至少有 2 （k-1） +2 个顶点， 即有 2k 个顶点。 把 S(u) v， S(v) u 连为完全偶图，则得到 2k 个顶点的围长为 4 的图，由作法知，这样的图是唯一的。 (2

34、) 对 uV(G),设 u 的邻接顶点为 u1,u2,uk,由于 G 的围长为 5，所以，u1,u2,uk互不 邻接。又设 ui的邻接顶点为 ui1,ui2,uik-1,(i=1,2,k),显然，S(ui)S(uj)= u (ij),否则，G 中有长为 4 的圈，所以，G 的顶点数至少有 k 2+1 个。 15. 对具有 m 条边的阶 n 图 G，证明： （1）若 mn，则 G 包含圈； （2）若 mn+4，则 G 包含两个边不重的圈。 证明证明 （1）若 G 含有环或平行边，则 G 有圈。假定 G 为 n 阶简单图。若 G 中顶点度大 于等于 2，则 G 中有圈。设 G 中有一度顶点，去掉该

35、顶点和其关联的边得图 G1,由条件，显 然有 m(G1) V(G1),若 G1中有一度顶点，去掉该顶点和其关联的边得图 G2,有 m(G2) V(G2),，如此进行下去，该过程不可能进行到 n=1 或 n=2 的情形，否则，不满足 mn 所以，过程进行到 Gm,Gm 是度数2 的图，它含有圈。 (2) 只就 m=n+4 证明就行了。 设 G 是满足 m=n+4，但不包含两个边不相交的圈的图族中顶点数最少的一个图。可以 证明 G 具有如下两个性质： 1) G 的围长 g5。事实上，若 G 的围长4，则在 G 中除去一个长度4 的圈 C1的一条 边，所得之图记为 G,显然，m(G) V(G)=V(

36、G),由(1),G中存在圈 C2, 使 C1,C2的边不 相交这与假定矛盾； 2） (G)3。事实上，若 d(v0)=2,设 v0v1,v0v2E(G),作 G1=G-v0+v1v2;若 d(v0)1,则 G1为在 G 中除去 v0及其关联的边(d(v0)=0,任去 G 中一条边)所得之图。显然， m(G1)=V(G1)+4,G1仍然不含两个边不重的圈之图。但V(G1)V(G)，与假定矛盾。 由 2),n+4=m3n/2 n 8. 但另一方面，由 1),在 G 中存在一个圈 Cg，其上的顶点之间 的边，除 Cg 之外，再无其它边，以 S0表示 Cg 上的顶点集，故由 2),S0上每个顶点均有伸

37、向 Cg 外的的边。记与 S0距离为 1 的顶点集为 S1，则 S0的每一个顶点有伸向 S1的边，反过来， S1中的每个顶点仅有唯一的一边与 S0相连，不然在 G 中则含有长不大于 g/2+2 的圈，这与 G 的围长为 g 相矛盾，故S0 S1,于是有：nS0+ S1g+g10,但这与 n8 矛盾。所以， 假定条件下的 G 不存在。 16. 在图 1-13 的赋权图中，找出 a 到所有其它顶点的距离。 解解 1. A1= a，t(a) = 0，T1 = 2. 1 13 bv 3. m1 = 1, a2 = v3 , t(v3) = t(a) + l(av3) = 1 (最小)， T2 =av3

38、 2. A2 =a, v3, 2 )2( 21 )2( 1 ,vbvb 3. m2 = 1, a3 = v1 , t(v1) = t(a) + l(av1) = 2 (最小)， T3 =av3, av1 2. A3 =a, v3, v1, 4 )3( 32 )3( 22 )3( 1 ,vbvbvb 3. m3 = 3, a4 = v4 , t(v4) = t(v1) + l(v1v4) = 3 (最小)， T4 =av3, av1, v1v4 2. A4 = a, v3, v1, v4，b1(4) = v2，b2(4) = v2，b3(4) = v2, b4(4) = v5 3. m4 = 4

39、, a5 = v5 , t(v5) = t(v4) + l(v4v5) = 6 (最小)， T5 =av3, av1, v1v4, v4v5 2. A5 = a, v3, v1, v4, v5，b1(5) = v2，b2(5) = v2，b3(5) = v2 , b4(5) = v2, b5(5) = v2 3. m5 = 4, t(v2) = t(v4) + l(v4v2) = 7 (最小)， T6 =av3, av1, v1v4, v4v5, v4v2 2. A6 = a, v3, v1, v4, v5, v2, b2(6) = v6, b4(6) = b，b5(6) = v6，b6(6) = v6 3. m6 = 6, a7 = v6 , t(v6) = t(v2) + l(v2v6) = 9 (最小)， T7 =av3, av1, v1v4, v4v5, v4v2, v2v6 2. A7 = a, v3, v1, v4, v5, v2, v6, b