图论第二章和第四章的课后习题

1、图论第二章和第四章书后练习题2.2 给出满足下列条件的图或说明这样的图为什么不存在(a)没有奇点的图。(b)所有顶点的度为三的图。(c)阶至少为5的图,且对于中任意两个邻接的顶点均有。(d)阶至少为5的非完全图,且对于中任意两个不邻接的顶点均有。解：（a）（b）(c)(d)2.4 给出一个阶为6且边数为10的图,满足解：所求图如下所示：2.6 在一个阶为的图中，若度为和的顶点数个数均为，则必为偶数。证：n-1+n+n+1=3n;图中仅有度为n+1,n,n-1三种度的顶点deg(v)=(n-1)n+n*n+(n+1)n=3n2由图论第一定理知，3n2为偶数则n为偶数。2.8 设为阶图，若对中任意

2、三个互不邻接的顶点和，都有则一定是连通的吗？解：不一定，如下图：2.10 我们已经知道，若阶图的任意两个不邻接的顶点和都满足则可能不连通。 (a) 证明：存在阶的连通图，它满足：对中两个任意不邻接的顶点和，都有且有两个不邻接的顶点和，使得=。 (b) 证明：若阶图的任意两个不邻接的顶点和都满足则至多有两个连通分支。 (c) (b)中的界是紧的吗？（a）证：假设，则由定理4可知G不是联通的，这与已知矛盾。 原结论正确。（b）证：假设存在G1，G2,G3 三个连通分支，其阶数分别为n1,n2,n3,且n1+n2+n3n;取uG1 vG2 矛盾！至多有两个连通分支(c)是的2.12证明：若阶图满足，

3、则是连通的，且。并证明：界是紧的。证：(反证法)假设存在满足条件的阶不连通图。设分别为的两个子图，阶数分别为 则： 与条件矛盾。2.14 证明：若图的任意一条边都连接一个奇点和一个偶点，则是二部图且有偶数条边。证：以G中所有的奇点为元素作集合U；以G中所有的偶点为元素作集合WG中的每条边分别连一个奇点一个偶点G的每条边必连接U中的一个顶点和W中的一个顶点于是G是二部图，U和W为其的部集2.16 证明：对于阶为的图，若的每个顶点的度或为或为，则包含至少个度为的顶点或至少个度为的顶点。证：（反正法）假设G之多包含n个度为n+2的顶点，则其余n+1个点的度均为n+1那么2n2+4n+1为奇数这与图论

4、第一定理矛盾同理可证至少含有n+2个度为n+1的顶点2.18 设8阶图的顶点集为，若，试求，并给予解释。解：由已知则可以得到下图：由图上可看出=42.20证明若图是非正则的连通图，则包含两个邻接顶点使得。证: 假设G不含有两个邻接点u和v使得 则可得到这与已知G是非正则图矛盾！包含两个邻接顶点使得2.22对于图所示的图，构造一个含作为诱导子图的3正则图(a) 利用定理2.7的证明方法，的阶是多少？(b) 若要使有最小的阶，则阶是多少？(G)=3 , 图如下所示：图H 如下所示：H的阶数为202.24如图所示的图，是包含作为诱导子图的3正则图，那么的阶最少为多少？G ：解：H的阶最小是8，如下图

5、：2.26.证明：（a）图G是正则的当且仅当是正则的。 (b)若G与均是正则的，则G具有奇数阶。（a）证：必要性： 设G是n阶的r正则图 G与构成n阶的完全图 G是r正则的而n阶完全图的每个顶点的度为n-1 则每个顶点的度为n-1-r 是正则的。 充分性：同理可证。（b）证：设G是n阶的r正则图 为n阶r正则图 又G为r正则，则每个顶点的度为n-1-r 题知为r正则 n-1-r=r 则有n=2r+1 G为奇数阶2.28.考虑下面的问题：是否存在图G和整数r，其中 ,使得按定理2.7的证明所构造的r正则图H不仅含有G作为诱导子图，而且在所有满足条件的r正则图具有最小阶。解：不存在 2.30 从开

6、始，应用定理2.7中的构造方法，给出一个含G作为诱导子图的3正则图H,H是哪一个著名的图？解：H为立方体2.32.利用定理2.10判断下列序列是否可图的，对于可图的序列，用类似2.11的方法，构造出以该序列为度序列的图。(a) s1: 5,3,3,3,3,2,2,2,1(b) s2: 6,3,3,3,3,2,2,2,2,1,1(c) s3: 6,5,5,4,3,2,1(d) s4: 7,5,4,4,4,3,2,1(e) s5: 7,6,5,4,4,3,2,1解：（a）可图G1： G2： G3： G：（b）可图（c）删去6，将后面6项减1，的序列4,4,3,2,1,0 该序列为非增排列删去首项4

7、，将后面地4项减1的序列得序列：3,2,1,0,0 为非增序列易看出该序列不可图s3不可图（d）可图 （e）可图2.34存在哪些整数x()使得序列7,6,5,4,3,2,1,x是可图的？解：x=42.36令S=2,6,7，证明存在正整数k，使得通过对S中的每一项列出k次所得到的新序列是可图的，试求最小的k.证：由题可知有序列S1=776622其中每个数字都有k个，若k7则按定理2.7中的方法有: 66622其中6有2k-1个，2有k个则按此方法依次推下去则可得到一个可图序列。对k7,同理可证。k的最小值为4.2.38对于图2.19所示的图的邻接矩阵A，通过计算A或实施矩阵乘法，确定A2和A3G

8、2： 解：A= A2= A3=2.40.设，其中U=v1,v2,vr,W=vr+1.vr+2,v2r，不通过矩阵乘法，确定G的邻接矩阵A以及A的幂A2，A3和A4。解：A= A2= A3= A4=2.42.对于，给出两个图H1和H2，使得H1是F正则的而非正则的，H2是正则而非F正则的。解：H1： H2 2.44.对于FP3，列举一个阶至少为7的F不规则图。解：2.46.列举下列图作为基础图的不规则多重图（a）P3 (b)P4 (c)C4 (d)C5 (e)K4(a) （b） (c) (d) (e) 2.48.证明定理2.18证：G是阶至少为2的联通图，且G为一个不规则的多重基础图说明G 的各

9、个顶点的度不同， 且阶至少为并连通 一定可以作为一个不规则多重图的基础图4.2证明:所有顶点的度都是偶数的连通图不含割边证:假设连通图G含割边e其关联u,v两个顶点 删去e得到的G的两个连通分支G1和G2 令 删去e, 为奇数，矛盾！ 原结论正确4.4设G是连通图，和是G的两条割边，证明：有三个连通分支当且仅当和都是G中的割边。证：G是连通图且仅关联两个顶点 最多可以将G 分割成两个连通分支 则e2也一定为G的割边，均为G的割边 而可以将G分成2个连通分支，必属于某个连通分支中 则又将其所在的连通分支继续分割成2个连通分支 有三个连通分支4.6设G是阶为的连通图且不含割边，假设对于G的每条边e

10、，G-e的每条边都是割边，G 有什么结构？并给予证明。解：G为圈，证明如下：证：设 G为圈 e一定不是G的割边，而不含圈 均是割边4.8证明：若图G的每个顶点的度至少是2，则G含有一个圈证：（反证法）假设G不含圈则G中一定存在一个端点那么此端点的度为1，矛盾！G必含圈4.10对下面地三种情形，分别举出一个例子或者说明为什么不存在这样的例子。（a）一个图，它不是树，但它的每条边都是割边。（b）一个4阶树，它的补图不是树。（c）一个数T，T恰好包含3个非端点的顶点，但T不是毛毛虫。解：（a） （b） (c)不存在，因为要使T不是毛毛虫，则T一定要包含至少非端点的顶点，所以T是不存在的。4.12（a

11、）列举一个树T及其一条边e，要求T-e的两个连通分支是同构的 （b）说民为什么不存在这样的树T，包含两个不同的边和使得的两个连通分支是同构的，且的两个连通分支也是同构的。解：（a）T:(b)若的两个连通分支和是同构的 又，令 与不可能同构 的两个连通分支不可能是同构的4.14已知某个35阶树T含有25个度为1的顶点，2个度为2的顶点，3个度为4的顶点，1个度为5的顶点，和2个度为6的顶点，它还含有2个具有相同（未知的）度为x的顶点，x是多少？解： 4.16（a）列举一个6阶树，概述含有4个度为1顶点，2个度为3的顶点（只有一个数具有这个性质） （b）找出满徐下述条件的所有树T，要求T的2/3的

12、顶点的度为1，其余的1/3顶点 的度为3。解：（a） (b) 4.18.某个n阶树T仅含有度为1,3的顶点，证明T有（n-2）/2个度为3的顶点。证：设T含有x个度为3的顶点，则有（n-2）个度为1的顶点。该图为n阶树其含有（n-1）条边则x满足方程，则x=(n-2)/2 .4.20证明或反驳： （a）若G是阶为n且边数为m 的图，且G 含3个圈，则 （b）恰含两个正则树解：（a）对下图，则有m=n;(b)树至少含有两个端点，则对时，其不可能时正则的。4.22设T是一个n阶树，证明：T的补图的变数与的边树相同证：T为n阶树，则T有n-1条边有n(n-1)/2-(n-1)条边即有(n2-3n+2

13、)/2条边而有(n-1)(n-2)/2=(n2-3n+2)/2边T的补图的变数与的边树相同4.24（a）找出阶为的所有图G，要求由G的任意3个顶点所诱导的子图都是树，若不存在这样的的树，说明理由。 （b）提出（a）中问题的一个推广，并解决之。解：（a）只要该图中含有4圈而不含3圈均可满足条件（b）任意k个顶点的诱导子图都是树 解答：含有k+1个圈且不含有k圈4.26证明：连通图G 的一条边e是割边当且仅当e属于G的任意一个生成树。证： e是连通图G的割边 e不再G的任意一个圈上 e一定在G的任一生成树上4.28 分别应用Kruskal算法与Prim算法寻找图4.12中赋权图的一个最小生成树，在

14、每种情形下都要说明该书是如何构造的。解：Kruskal算法得图如下：Prim算法得图如下：4.32证明：存在唯一的正整数k,使得任一图都不会恰好含有k个生成树。证：k=21）G不连通生成树个数为02）G连通含圈时，生成树个数大于等于3G是树时，生成树个数为1所以，存在k=2个使得任一图都不会恰好有k生成树。4.34（a）确定图4.18中的图G的生成树的个数（b）对于，确定图4.18中的图的生成树个数（注意到（a）是k=4的情况）G： 解：（a）不含e1,e2,e3的树，删去余下边地任一条即可，共有9种 恰含e1,e2,e3中一条的树，设含有e1,共有18种，则该情况共有 种 恰含e1,e2,e3中两条的树，设含有e1,e2,e3共有18种，则该情况共有种 共有54+54+9=117种 （b）不含有三角形三条边的有3(k-1)种 恰含有三角形三边中的有种 恰含有三角形三条边的有种 则共有种4.36确定图4.20中途G的生成数个数解：（a）不含有中间五边形的共有15种 （b）恰含中间五边形的一条边的有种 （c）恰含有中间五边形的两条边的有种 （d）恰含有中间五边形的三条边的有种 （e）恰含有中间五边形的四条边的有种 生成树的个数共有3945种4.38用矩阵定理来证实具有顶点集的不同树的个数。证：