去找 http://www.7zhao.net 习题十
1. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。
证明：（1）先证结论：
因为G是简单图，所以G的结点度上限 max(d(v)) ≤ n-1, G图的总点度上限为 max(Σ(d(v)) ≤ n﹒max(d(v)) ≤ n(n-1) 。根据握手定理，G图边的上限为 max(m) ≤ n(n-1)/2,所以。 （2） =〉G是完全图 因为G具有上限边数，假设有结点的点度小于n-1,那么G的总度数就小于上限值，边数就小于上限值，与条件矛盾。所以，G的每个结点的点度都为n-1，G为完全图。 G是完全图 =〉 因为G是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G的边数 。■ 2. 设G是一个（n，n+1）的无向图，证明G中存在顶点u，d（u）≥3。 证明：反证法，假设,则G的总点度上限为max(Σ(d(u)) ≤2 n，根据握手定理，图边的上限为max(m) ≤ 2n/2=n。与题设m = n+1，矛盾。因此，G中存在顶点u，d（u）≥3。■ 3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）； （2）（6，3，3，2，2） （3）（4，4，2，2，4）； （4）（7，6，8，3，9，5） 解：除序列（1）不是图序列外，其余的都是图序列。因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。 可以按如下方法构造满足要求的图：序列中每个数字ai对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。最后，将奇数序列对应的点两两一组，添加连线即可。下面以（2）为例说明： (6 , 3, 3, 2, 2 ) 对应图G的点集合V= { v1,v2,v3,v4,v5} v1 v2 v3v5 v4
每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1)
1
去找 http://www.7zhao.net v1 v2 v3v5 v4 将奇数3，3 对应的结点v2,v3一组，画一条连线 v1 v2 v3v5 v4 其他序列可以类式作图，当然大家也可以画图其它不同的图形。■ 4．证明：在（n，m）图中。 证明：图的点度数是一组非负整数{d(v1),d(v2)…d(vn)}，那么这组数的算术平均值一定大于等于其中的最小值，同时小于等于其中的最大值。对应到图的术语及为：最大值为，最小值为δ，平均值 = (d(v1)+d(v2)…+d(vn))/n = 2m/n,所以。■ 5．证明定理10.2。 【定理10.2】 对于任何（n,m）有向图G =（V，E）， 证明：有向图中,每条有向边为图贡献一度出度，同时贡献一度出度，所以总出度和总入度相等，并和边数相等。因此，上述关系等式成立。■ 6．设G是（n，m）简单二部图，证明：。
证明：本题目，我们是需要说明n阶的简单二部图的边数的最大值 = 即可。
设n阶的简单二部图，其两部分结点集合分别为V1，V2,那么|V1| + |V2| = n。此种情况下，当G为完全二部图时，有最多的边数，即max(m) = |V1||V2|,变形为，max(m) =( n-|V2|)|V2|.此函数的最大值及为n阶二部图的边的上限值，其上限值为当|V2|=n/2 时取得。及max(max(m)) = ,所以n阶二部图(n,m), ■
2
去找 http://www.7zhao.net 7. 无向图G有21条边，12个3度数结点，其余结点的度数均为2，求G的阶数n。
解：根据握手定理有： 21 =( 3Χ12 + 2(n-12))/2, 解此方程得n = 15■
8．证明：完全图的点诱导子图也是完全图。
证明：方法1
为证明此结论，我们先证两个引论：
引论1：设G(V,E)为母图，,则G的任意子图G'(V’,E’)是G关于V’的点诱导子图G''(V’,E’’)的子图。 引论2：引论1中G’’(V’,E’’)的任意点诱导子图，也是G图的点诱导子图。 证明：略，请读者证明。 设有完全图Kn( n≥1),现根据其p阶点诱导子图作归纳证明。 Kn的1阶点诱导子图，显然是完全图，且都是K1图。当n≥2，Kn的2阶点诱导子图，显然是完全图，且都是K2图 假设Kn的p(n>p>2)阶点诱导子图，为Kp图，那么对任意的p+1阶点诱导子图G，根据引理2结论，G的任意p阶点诱导子图G’为Kn的p阶点诱导子图，且为Kp图。因此，G必为Kp+1图。 根据以上论证可得原命题成立■ 方法2 因为完全图的任意两个顶点均邻接，所以点导出子图任意两个顶点也邻接，为完全图。■ 9．若，称G是自补图。确定一个图为自补图的最低条件；画出一个自补图来。 解：设G为(n,m)图，为(n,m`)图， 根据补图的定义有，至少应该满足 m+m`=n(n-1)/2 (1) 根据同构的定义有，至少应该满足 m=m` (2) (1),(2)联立求解得：m=n(n-1)/4, 及一个图为自补图，最低条件为结点数为4的倍数或为4的倍数加1。 图示略■ 10．判断图10.29中的两个图是否同构，并说明理由。 ???????图10.29 9-1.15图????? 解：题中两个图不同构，因为左边图的唯一3度点有2个1度点为其邻接点，而右图唯一的3度点只有1个1度点为其邻接点。因此这两个图不可能同构■
11．证明： 图10.30中的两个图是同构的。
3
去找 http://www.7zhao.net 图10.30
解：略■
12. 求具有4个结点完全图K4的所有非同构的生成子图。
解：我们可以把生成子图按总度数不同进行分类，不同总度数的子图类决不同构。总度数相同的子图类中，再去找出不同购的子图。因此求解如下： Σd(v) = 0: (0,0,0,0) =2: (1,1,0,0)
=4: (2,1,1,0) (1,1,1,1)
=6: (3,1,1,1) (2,2,1,1)(2,2,2,0) =8: (2,2,2,2) (3,2,2,1) =10: (3,3,2,2) =12: (3,3,3,3)
总共10个不同构生成子图■
13. 设有向图D=
(1) 在图中找出所有长度分别为1，2，3，4的圈 (至少用一种表示法写出它们，并以子图形式画出它们)。
(2) 在图中找出所有长度分别为3，4，5，6的回路，并以子图形式画出它们。
解：(1)
4
去找 http://www.7zhao.net C=AA C=Ae4Be8Ce5A C=Ae4Be7Ce6De2A C=ADA C=Ae4Be7Ce5A C=Ae4Be8Ce6De2A (2)子图略 长度为三的回路：Ae1Ae1Ae1A,Ae1Ae3De2A,Ae4Be7Ce5A,Ae4Be8Ce5A 长度为四的回路：AAAAA，AAADA，AABe7CA,AABe8CA,ABe7CDA,ABe8CDA 长度为五的回路：AAAAAA,AAAADA,AAABe7CA,AAABe8CA,AABe7CDA,AABe8CDA, AADADA,AAAe4Be7Ce5A,AAAe4Be8Ce5A, ADAe4Be7Ce5A,ADAe4Be8Ce5A■ 14. 试证明在任意6个人的组里，存在3个人相互认识，或者存在3个人相互不认识。 证明：设A为6人中的任一人，那么A要么至少与3人认识，要么至少与3人不认识，二者必居其一。 假设A与B，C，D三人认识，如果B，C，D三人互不认识，结论成立 如果B，C，D三人中，至少有两人相互认识，则它们和A一起，构成相互认识的3人，结论成立。 同理，A至少与3人不认识，结论也成立。因此，题设结论成立■ 15. 若u和v是图G中仅有的两个奇数度结点,证明u和v必是连通的。 证明：反证法，假设u和v不连通，那么他们必然分布于此图的两个连通分支中。那么它们将分别是各连通分支中唯一的奇数度结点。根据握手定理，一个图中奇度点的个数为偶数。而两个连通分支中，奇度点的个数为奇数。矛盾。矛盾的产生，是由于假设不连通导致的，因此，题设结论成立■ 16. 证明:G是二部图当且仅当G的回路都是偶长回路。 证明：设二部图G，顶点分为两个集合V1 ，V2 充分性：
先证明在二部图中，奇长路的道路的两个端节点一定分别在两个顶点集合中，对道路长度使用归纳法，
（1） 当道路长度为1是，根据二部图的定义，每条边的两个顶点分别在两个点集合中，
结论成立
（2） 假设道路长度为2n-1 ( n≥2)时结论成立
（3） 当道路长度为2n+1时，设P=v1v2…v2n-1v2nv2n+1,在此路径上删除最后两个结点，那
5
去找 http://www.7zhao.net 么道路P将变为长度为2n-1的奇长道路，根据假设，v1,v2n-1分别在两个顶点集合中，那么v2n和v1在同一顶点集合中，而v2n+1和v1在不同顶点集合，结论成立
因为G中的任何回路，写成道路的形式，起点和终点时一个结点，当然在同一个顶点集合中，因此长度必为偶数； 必要性：（仅对连通分支证明） 在图中任意取一点着色为白色，将和此点最短距离为奇数的点着色为黑点，为偶数的着色为白点，那么将结点分为白色和黑色连个点集，任何同色点之间没有边相连。否则将形成奇数长度的回路，例如同色结点v1，v2 相邻，那么从初始着色点v开始通过最短路径可以形成如下回路v…v1v2…v,因为v…v1,v2…v长度和为偶数，那么回路v…v1v2…v长度为奇数，与题设矛盾。所以是二部图
17.设(n, m)简单图G满足,证明G必是连通图。构造一个的非连通简单图。
证明：假设G不连通，分支G1，G2．．Ｇｋ，那么他们的边数的最大值ｍａｘ（ｍ）＝Σ（ｎｉ－１）ｎｉ／２≤Σ（ｎｉ－１）（ｎ－１）／２＝（ｎ－１）／２Σ（ｎｉ－１）＝（ｎ－１）（ｎ－ｋ）／２，所以，只有当k=1时，才能满足题设要求，G是连通图。如果将顶点集合分成两个点集，|V1|=1，|V2|=n-1,构成如下的有两个分支的非连通简单图，G1=（1，0），G2=Kn-1,满足题设条件■
18. 设G是阶数不小于3的连通图。证明下面四条命题相互等价: (1）G无割边；
(2) G中任何两个结点位于同一回路中；
(3) G中任何一结点和任何一边都位于同一回路中； (4) G中任何两边都在同一回路中。
证明：（1）=〉（2）
6
去找 http://www.7zhao.net 因为G连通，且G无割边，所以任意两个结点u,v，都存在简单道路p=u…wv.又因为G无割边，所以，删除边wv后，子图依然连通，即w,v存在简单道路p’,以此类推，可以找到一条核p每条边都不相同的p’’=v…u,这样p和p’’就构成了一条回路。 （2）=〉（3）
因为G中任意两个结点都位于同一回路中，所以任意结点u,和任意边e的两个端点v1,v2都分别在两个回路C1，C2中，如果C1=C2=u…v1…v2…u,那么将回路中v1…v2,用v1v2=e替换，就得到新的新的回路，并满足要求。如果C1≠C2，C1=u…v1…u,C2=u…v2…u,那么构成新的道路P=u…v1…u…v2…u,在其中将重复边剔出掉，得到新的回路C3，其中包含v1,v2结点，可以将回路中v1…v2用v1v2=e替换，就得到新的新的回路，并满足要求. （3）=〉（4）
对任意两条边e1,e2其端点分别为u1,u2,v1,v2。根据（3）存在回路C1 = u1…v1v2…u1,C2=u2…v1v2…u2。那么可以形成新的闭道路P=u1…v1v2…u2…v1v2…u1,在其中将重复边剔出到，得到新的回路C3，其中包含e2和u1,u2结点，可以将回路中u1…u2用u1u2=e1替换，就得到新的新的回路，包含e1,e2,满足要求. (4)=>(1)
因为任意两条边都在同一回路中，所以不存在割边。假设边e是割边，那么删除此边，图不连通，分支中的任何一对不在同一分支中的边，不能构成回路，与条件矛盾。所以，G中无割边■
19. 设G=(V,E)是点度均为偶数的连通图。证明:对任何。
证明：G-v最多产生d(v)个奇数度点，又因为每个连通分支中奇数度点的个数是偶数，即G-v的连通分支最少有两条边和v相连，所以总连通分支数小于等于d(v)/2■
20. 证明:图中距离满足欧几里德距离的三条公理。
证明：（1）d(u,v)≥0,即任何两个结点之间的最短路长度大于等于0
显然，结点ｕ与自己之间的距离为０，而和其他结点之间的最短距离不为０。 （２）ｄ（ｕ，ｖ）＝ｄ（ｖ，ｕ），两个结点之间的最短距离相等
显然，如果长度为ｋ的最短道路p=u…v ，即使u到v的最短道路，也是v到u的最短道路。 （3） d(u,v)+d(v,w)≥d(u,w) 假设d(u,v)+d(v,w)≤d(u,w)，那么最短道路P=u…w ,就不是最短道路，因为另一条道路p’=u…v…w其长度小于Ｐ，与最短道路相矛盾，因此原结论存立■
21. 证明:在非平凡连通图G中,e为割边的充要条件是它不包含于G的任何圈中。
证明： 1） e为割边 =〉e不包含于G的任何圈中
假设e包含在某一圈Ci中，那么删除此边，但边关联的两个邻接点依然连通，所以没有破坏原图的连通性。因此不是割边，矛盾。所以假设不成立，既e不包含于G的任何圈中；
2）e不包含于G的任何圈中 =〉e为割边
假设e为割边，那么删除此边，生成子图依然连通。e关联的两个邻接点有基本道路存在，此基本道路连同e构成一个圈。与题设矛盾。所以假设不成立，既e为割边。 根据1），2)可知，题设结论成立■
7
去找 http://www.7zhao.net
22. 证明:若G是3度正则的简单图,则。（请冯老师帮助解答下）
证明：
23. 证明:在具有n（n≥2）个结点的简单无向图G中，至少有两个结点的度数相同。
证明：此题可用鸽笼原理，因为n个结点的简单无向图G中，结点的度数只可能是0，1，2…n-1这n个数，又因为如果有结点的度数为0，那么就不可能有结点的度为n-1，反之也然。所以n 个结点，最多有n-1种度数，其中必有至少两个结点的度数相同■ 24. 设G是的简单图。证明:G中必有长度至少为的圈。 证明：设ｐ＝ｕ．．．ｖ是满足题设要求图Ｇ中的最长基本道路，那么ｄ（ｕ），ｄ（ｖ）都应该大于等于δ。那么，u,v的邻接点都应该在道路p 上，否则此道路可以延长，与其是最长路假设矛盾。如果u，v是邻结点，那么可以构成一个圈c= u…vu，其长度≥δ＋１。如果ｕ，ｖ不是邻结点，那么从ｐ的终点开始删除点，直到其为ｕ的邻结点为止，得到道路ｐ＇,可知道路p’，依然保持ｕ的所有邻结点都在ｐ＇上的性质，所以可构成一个圈ｃ＇＝ｕ．．．ｕ＇ｕ，其长度≥δ＋１，证毕■ 25. 证明:G是单向连通图当且仅当存在一条包含G中全部结点的有向道路。 证明：假设不存在包含全部结点的有向道路，那么设ｐ＝ｖ１ｖ２．．．ｖｋ是Ｇ中最长的有向道路，且ｕ结点不包含在此有向道路中。ｕ和此道路中任何中间结点都不可能双向可达，且ｕ不能到达ｖ１，且ｖｋ也不能到达ｕ，否则，此最长路可扩充。那么由于道路上的每个结点和ｕ都单向可达，所以此最长路和ｕ之间的可达关系必然如下图所示： ｖｋ／２ ｕ ｖｋ／２＋１ ｖｋ＋１／２－１ ｕ ｖｋ＋１／２ ｖｋ＋１／２ ＋１ ｋ为偶数 ｋ为奇数
8
去找 http://www.7zhao.net 当ｋ为偶数时，道路可扩充为v1…vk/2…u…vk/2+1…vk,而当ｋ为奇数时，不管ｖｋ＋１／２与ｕ之间是如何单向可达的，都可以构造出更长的有向道路，矛盾，所以Ｇ中一定存在包含所有结点的有向道路■
26. 无向图G如图10.32所示，先将此图顶点和边标出，然后求图中的全部割点和割边。
图10.32 解：标注如下所示： ｕ３ ｕ５ ｕ７ ｕ１ ｕ４ ｕ２ ｕ６ ｕ８ ｕ９ 根据标记后的图，可求得割点分别为：ｕ４，ｕ７，ｕ８，割边分别为：ｕ４ｕ５，ｕ７ｕ８，ｕ８ｕ９■ 27. 求图10.33的全部强分图和单向分图。 图10.33
解：将图重新标记如下：
9
去找 http://www.7zhao.net ｖ１ ｖ４ ｖ２ ｖ５ ｖ９ ｖ６ ｖ３ ｖ７ 那么此图的邻接矩阵为，通过计算可求得其强分图矩阵为： 因此，此图有两个强分图，一个包含一个结点Ｖ９ ，一个包含其它的８个节点。由于两个强分图之间存在有向道路，因此全部９个结点，构成了单向分图■ 28. 证明：一个连同无向简单图中，任意两条最长路至少有一个公共顶点。 证明：假设两条最长路ｐ１＝ｖ１ｖ２．．．ｖｋ，ｐ２＝ｕ１ｕ２．．．ｕｋ没有公共点，那么两条道路上的点集之间就有道路相连，否则就不是连通图了。设此道路起点是ｐ１上ｍ点，终点是ｐ２上的ｗ点．可根据如下情况进行调论：（１）ｍ，ｗ是ｐ１，ｐ２的中间结点，那么可构成新道路 Ｐ＝ｖ１ｖ２．．．ｍ．．．ｗ．．．ｕｋ，此路至少比Ｐ１长1，矛盾。（2）假设m和w不能均分p1,p2,那么可以将两个长路段和m,w之间的道路进行拼接，那么可得到比p1长的道路，与ｐ１，ｐ２是最长路矛盾。因此任意两条最长路至少有一个公共顶点■ 29. 证明：若G是n阶无向简单图，G中每一对不相邻的顶点的度数之和至少是n-1，则G是连通图。 证明：假设G不是连通图，G1，G2 是G的两个连通分支，分别为n1,n2阶连通无向简单子图，则n1+n2≤n。对G1中任意结点v1,和G2中任意结点v2而言，v1的最大点度为n1-1,v2的最大结点度为n2-1;则v1,v2的点度之和，最大为n1+n2-2≤n-2 图10.34 10 去找 http://www.7zhao.net 解：对图的结点和边进行编号如下： ｖ１ ｅ２ ｖ３ ｅ７ ｅ５ ｖ５ ｅ１１ ｅ６ ｅ８ ｅ１０ ｅ９ ｖ６ ｅ１ ｅ３ ｅ１２ ｖ２ ｅ４ ｖ４ ｖ７ 邻接矩阵： 因此可达矩阵为： 强分图矩阵为： 关联矩阵为： ■ T31. 设P= (pij) n×n是可达性矩阵。证明:P错误！未找到引用源。P中第i行中非零元素所在列号给出了包含结点vi的强分图的全部结点编号。 证明：根据强分矩阵的计算过程可知，其包含的含义是结点间双向可达信息。根据有向图的双向可达关系是一个等价关系，因此P错误！未找到引用源。PT中第i行中非零元素所在列号既是一个等价类，所以包含了一个强分图的所有结点■ 已完成[1，2，3，4，5，6，7，8，9，10，11，12，13,14，15，16，17，18，19，２０,21，２３，２４，２５，２６，２７，２８，29，３０，31] 第２２题未证明 11 去找 http://www.7zhao.net 习题十一 1. 设一个树中度为k的结点数是nk（2≤k），求它的叶的数目。 解：设T的节点总数为n，叶节点数目为t ，根据题意及握手定理有： t + n2 + n3 + …+ nk = n (1) t + 2n2 + 3n3 + …k(nk) = 2(n-1) (2) 握手定理 (1),(2)联立求解得： t = n3 + 2n4 + … (k-2)nk + 2■ 2. 证明：树T中最长道路的起点和终点必都是T的叶。 证明：假设T中最长道路P=vi1vi2…vik的起点或终点不是T的叶结点，设d(vi1)>1,则vi1的 12l 所有邻接点(v‘,v’…,v’)都在P中，那么在T中可以找到一个回路,那么截取道路P, 得到 l 回路C= vi1 …v’ vi1 .与T中无回路矛盾。对于d(vik)>1时同理。因此，假设不成立，即最长道路P的起点和终点都是T的叶节点■ 3. n（n≥3）阶无向树T的最大度Δ至少为几？最多为几？ 解：当T中只有一个枝点时，Δ = n-1,为最大值。 当T构成一条链时，只有两个叶结点，其余结点都为2度点，此时Δ = 2，为最小值，因此Δ至少为2 ，最大为n-1■ 4. n（n≥3）阶无向树T的最大度Δ=2，则T中最长的简单道路为几？ 解：根据第3题结论，当无向树T的最大度Δ=2时 ，T构成一条链，以此最长的简单道路包含所有的节点，道路长度L=n-1■ 5. 证明：任何无向树都是二部图。 证明：以树Ｔ中任意结点ｕ为起点，将与ｕ最短距离为偶数的结点放入ｖ１结点集合，将与ｕ最短距离为奇数的结点放入ｖ２结点集合，那么这两个结点集合中，显然不存在公共点，同时两个结点集合组成了树的全部结点，因此是数Ｔ的结点集合的一个分化。假设在Ｖｉ集合中存在两个结点ｕ１，ｕ２是邻结点，那么就存在如下道路：ｐ＝ｕ．．．ｕ１ｕ２．．．．ｕ， 12 去找 http://www.7zhao.net 其中ｐ１＝ｕ．．．ｕ１代表ｕ到ｕ１的最短路径，ｐ２＝ｕ２．．．ｕ代表ｕ到ｕ２的最短路径，且ｕ１ｕ２边不在最短路径上，否则他们的最短路径不是同奇偶的；因此，Ｐ中包含圈，这与树中无圈相矛盾，所以Ｔ中的边，只能存在于两个点集合之间，所以是二部图■ 6. 证明：如果T是树且Δ≥k，则T中至少有k个叶结点。 证明：当T为非平凡树时，根据T的定义，T中每个枝点都是割点，当删除d(v)= Δ 的节点时，ω（T-v）=Δ ，每个分支都是数，如果分支都是平凡树，则这些节点都是T的叶，叶节点数为Δ。如果分支有非平凡数，那么至少有两个叶节点，其中至少一个是删除v时就存在的，因此总的叶节点个数≥Δ≥k。因此Ｔ中至少有ｋ个叶结点■ 7. 设G为n（n≥3）阶简单图，证明G或中必含圈。（有误，>4,p223） 证明：反证法，假设G和中都不含圈，那么G和的所有分支都是树。则G所包含的最大边数|E(G)|=n-1, 则所包含的最大边数|E()|=n-1. 因为G及的边数总和|E(G)|+ |E()| = n(n-1)/2, 但根据假设条件，max|E(G)|+max |E()|=2(n-1) < n(n-1)/2, 矛盾.因此，G或中必含圈■ 8．证明：恰好有两个顶点的度为1的树必为一道路P。 证明：因为此树仅有2个叶结点，因此Δ<3。那么枝点的度只能为2。所以此树为一条链，及一条道路■ 9. 设T是一个n+1阶树，G是最小点度的简单图。证明：Ｇ必含有与Ｔ同构的子图。 证明：采用归纳法证明，对ｎ进行归纳 （１） 当ｎ＝１时，Ｔ为２阶树，因为Ｇ是最小点度的简单图，所以任意意个结点与其邻结点都构成一颗２阶树，成立 （２） 假设ｎ＝ｋ，ｋ≥２时，结论成立，即T是一个ｋ+1阶树，G是最小点度的简单图。 Ｇ必含有与Ｔ同构的子图 （３） 当ｎ＝ｋ＋１时，G是最小点度的简单图，Ｔ是任意一棵ｋ＋２阶树，在Ｔ中删除 一个叶结点ｔ，那么Ｔ－｛ｔ｝是一棵ｋ＋１ 阶树，利用归纳假设，G中必存在与Ｔ－｛ｔ｝同构的子图T’，T’中最大的点度不超过k，所以每个T’中的结点都有邻结点不包含在T’中，所以T’可在某个结点上增加一个额外的结点u，使T’+{u} 与T 同构 综上所述，结论成立■ 10.设e是连通图G的一条边。证明：e是G的割边当且仅当e含于G的每个生成树中。 证明： 1）充分性：e是G的割边则e含于G的每个生成树中 假设e不包含在某棵生成树T中，那么e 一定在T的树补边集中，那么G-{e }中依然包含树T,因此G-{e }连通，与e是割边矛盾，因此e含于G的每个生成树中； 2) 必要性：e含于G的每个生成树中则e是G的割边 假设ｅ不是Ｇ的割边，那么Ｇ－｛ｅ｝依然连通，具有生成树，这些生成树也是Ｇ的生成树， 13 去找 http://www.7zhao.net 且不包含ｅ，与e含于G的每个生成树中前提矛盾，因此e是G的割边。 综上所述，题设结论：e是G的割边当且仅当e含于G的每个生成树中成立■ 11.设T1和T2是连通图G的两个不同的生成树，a是在T1中但不在T2中的一条边。证明：T2中存在一条边b，使得（T1-a）+b和（T2-b）+a也是G的两个不同的生成树。 证明：从T1中删除边ａ，得树T1－１和T1－２ ，分别用Ｖ１，Ｖ２ 表示这两棵子树的结点集合，设Ea＝｛ｅ｜ｅ的两个端点分别属于Ｖ１，Ｖ２｝，显然，ａ∈Ea．因为ａ不在T2中，所以ａ是T2的树补边。设C（a）为在中T2增加边a后所得到的圈，则C(a)中必然存在T2 的树边b不在T1中但在Ea中。否则，C(a)上的T2的所有树边均在T1中或均不在Ea中。如果C(a)上的T2的所有树边均在T1中，则C(a)上的所有边都在T1中，与T1是树矛盾。如果C(a)上的T2的所有树边均不在Ea中，则C(a)中除ａ外所有的边的端点均在Ｖ１或Ｖ２中，与C(a)是基本回路矛盾。所以C(a)中必然存在不在T1中但在T2中的的树边，设ｂ是其中的一条。则（T1-a）+b连通且无回路是Ｇ的生成子图，它是Ｇ的生成树。同理（T2-b）+a也是Ｇ的生成树■ 12.用Kruskal算法求图11.13的一个最小生成树。 解：略，请参考书中算法计算■ 13. 设简单连通图G=（V，E）的边集E恰好可以划分为G的两个生成树的边集。证明：如果G中恰有两个4度以下结点u和v，则uv?E。（请冯老师帮助证明下） 14. 已知n阶m条边的无向简单图是由k（k≥2）棵树组成的森林，证明：m = n – k。 证明：设ｋ棵树分别为ｎ１，ｎ２，．．．ｎｋ，根据树的性质有如下公式成立： n 1+n2…nk = n (1) (n 1-1)+(n2-1)…(nk-1) = m (2) (1)-(2) 得：n – m = k => m = n-k■ 15. 证明: 简单连通无向图G的任何一条边，都是G的某一棵生成树的边。 证明：简单连通无向图G的任何一条边，要么是割边，要么是非割边。如果是割边，那么此边是所有生成树的树边；如果不是割边，设边为ｅ，那么G-{e}连通，可以求出生存树Ｔ，此Ｔ也是Ｇ的生存数，且不包含ｅ ，那么ｅ 是Ｔ的树补边。则Ｔ+{e},有唯一一个圈Ｃ，删除圈上任意一条非ｅ边，便得到一颗包含ｅ边的树■ 16. 证明:在完全二又树中,边的数目等于2(t -1)，式中t是叶的数目。 证明：设Ｔ中的结点数为ｎ，枝点数为ｉ；根据完全二叉树的定义，有下面的等式成立。n=i+t,m=2i,m=n-1.解方程组，得到m=2(t-1) ■ 17. 决定一个m叉树中内部道路长度之和与外部道路长度之和的关系。 14 去找 http://www.7zhao.net 解：根据完全二叉树的内部道路长度之和与外部道路长度之和的关系猜测m叉树中内部道路长度之和与外部道路长度之和的关系为：Ｊ＝（ｍ－１）Ｉ＋ｍｉ．其中Ｊ表示各叶结点的道路长度之和，Ｉ表示各分支点道路长度之和，ｉ表示分支结点数。下面对分支结点数ｉ进行归纳： ｉ＝１时，Ｉ＝０，Ｊ＝ｍ，故Ｊ＝（ｍ－１）Ｉ＋ｍｉ成立． 假设ｉ＝ｋ是结论成立． 当ｉ＝ｋ＋１是，设在完全ｍ叉树Ｔ中，ｖ是一个道路长度为ｌ的分支点且其ｍ个儿子ｖ１，ｖ２．．．ｖｋ都为叶结点，那么Ｔ－｛ｖ１，ｖ２．．．ｖｋ｝是含ｋ个分支点的完全ｍ叉树。由归纳假设有Ｊ｀＝（ｍ－１）Ｉ｀＋ｍｋ，比较Ｔ和 Ｔ－｛ｖ１，ｖ２．．．ｖｋ｝，Ｊ＝Ｊ｀＋ｍ（ｌ＋１）－ｌ＝Ｊ｀＋（ｍ－１）ｌ ＋ｍ ，Ｉ＝Ｉ｀＋ｌ，所以Ｊ＝（ｍ－１）Ｉ｀＋ｍｋ＋（ｍ－１）ｌ ＋ ｍ ＝（ｍ－１）Ｉ＋ｍ（ｋ＋１）■ 18. 给出公式的根树表示。 解：将标示符号看成叶结点，逻辑连接词作为分支结点，按公式的先后顺序构造根树如下： ■Λ ? Λ P ? ` P Q P Q ? R ? Λ ? ■ 19. 给定权1,4,9,1,2,6,4,6,8,10,构造一个最优二叉树。 解：根据带权最优二叉树定理构造过程如下： 15 去找 http://www.7zhao.net 1 4 9 1 2 6 4 6 8 10 1 1 2 4 4 6 6 8 9 10 重新排序 ==== 2 2 4 4 6 6 8 9 10 ==== 4 4 4 6 6 8 9 10 ====== 8 4 6 6 8 9 10 ==== 8 10 6 8 9 10 ==== 8 10 14 9 10 8 9 14 10 10 交换10，9 ======== 17 14 10 10 ==== 17 14 20 ============= 31 20 ============= 51 10 9 6 8 4 6 4 2 1 1 ■ 20. 把图11.14的有序林变换成一个二叉树。 解：STEP1: 将每棵有序树采用中间格式表达出来 SETP2： 再用一条有向道路把各分支的根从左到右连接起来 16 去找 http://www.7zhao.net SETP3： 转换为二叉树。 具体过程略■ 21. 证明:正则二叉树必有奇数个结点，且树叶数t与结点数n之间有：t=（n-1）/2。 证明：因为正则二叉树的边数ｍ与分支点数ｉ的关系为：ｍ＝２ｉ，又因为是树，因此结点数ｎ满足：ｎ＝ｍ－１＝２ｉ－１，必为奇数。叶结点数ｔ和枝点数之和为ｎ，即：ｔ＋ｉ＝ｎ，因此t=（n-1）/2■ 22. 遍历一棵树是指访问这个树的每个结点一次且仅一次。遍历二叉树有如下三种方式: (1)前序遍历:访问根, 遍历左子树,然后遍历右子树。 （2)中序遍历: 遍历左子树,访问根,然后遍历左子树。 （3)后序遍历: 遍历左子树, 遍历右子树,然后访问根。 根据三种不同遍历形式,分别写出图11.15中各结点被访问的顺序。 图11.15 解： （１） 前序遍历结果：abdfjglmcehi （２） 中序遍历结果：jfdlgmbachei （３） 后序遍历结果：jflmgdbhieca■ 23. 设英文字母b，d，g，o，y，e出现的频率分别是0.014，0.038，0.02，0.08，0.131,构造一个与它们对应的前缀码,并写出符号串dogbybed对应的编码。 解：构造最优树如下： 17 去找 http://www.7zhao.net 0.014，0.038，0.02，0.08，0.02，0.131 0.014，0.02， 0.02，0.038，0.08，0.131 ＝＝＝＝＝＝ 0.034 0.02，0.038，0.08，0.131 ＝＝＝＝＝＝＝＝ 0.0５2 0.038，0.08，0.131 ＝＝＝＝＝＝＝＝ 0.０９ 0.08，0.131 ＝＝＝＝＝＝＝＝ 0.283 0.131 ＝＝＝＝＝＝＝＝＝ ０．４１４ 0 0 1 1 1 0 0 1 0.08 (o) 0.038 (d) 0.131 (e) 0 1 0.0２ (y) 0.014 (b) 0.02 (g) 因此获得相应的前缀码：b=00000,g=00001,y=0001,d=001,o=01,e=1 所以dogbybed的编码为：0010100001000000001000001001■ 完成题目 [1，2，3,4，５，6，7，8，１０，１１，１２,14，１５,16，１７,18，19，20，２１，22,23] 勘误： １．２３题，［频率分别是0.014，0.038，0.02，0.08，0.131］改为［频率分别是0.014，0.038，0.02，0.08，0.02，0.131］ｐ２２３ ２．7题，［ 设G为n（n≥3）阶简单图，证明G或中必含圈］改为［设G为n（n≥５）阶简单图，证明G或中必含圈］p223 第十三题未证明 18 去找 http://www.7zhao.net 习题十二 1．证明下面3个图都是平面图。 证明：因为所给图都可以平面图的方式画出来，如下： ■ 2．下面3个图都是平面图，先给图中各边标定顺序，然后求出图中各面的边界和面度。 解：略■ 3. 设G是阶数不小于11的图。证明：G或中至少有一个是非平面图。 证明：假设G和都是平面图，因为，所以至少有一个图的边数，设，有因为是平面图，所以有，求解得ｎ≤１０．与题设G是阶数不小于11的图矛盾，因此G或中至少有一个是非平面图■ 4. 证明：具有6个结点、12条边的简单连通平面图，它的面的度数都是3。 证明：因为是简单连通平面图，因此根据欧拉公式有 ６－１２＋ｆ＝２，所以有８个面。根据面度和与边的关系有，Σｄ（ｆｉ）＝２ｍ＝２４；因为要在平面上围成一个面，至少需要３边，所以８个面，Σｄ（ｆｉ）≥２４。因此，不存在面度大于３的面，所有面的度数都是３■ 5. 证明：少于30条边的简单平面图至少有一个顶点的度不大于4。 19 去找 http://www.7zhao.net 证明：假设图Ｇ（ｎ，ｍ）的每个结点的点度都大于等于５，根据握手定理及平面图的判定定理有： ５ｎ≤２ｍ＜６０ （１） 握手定理 ｍ≤３ｎ－６ （２） 根据（１）得到：ｎ<１２ 结合（１）（２）得到：５ｎ／２≤３ｎ－６，所以ｎ≥１２，矛盾。因此假设不成立，题设结论成立■ 6. 设G是具有k（k≥2）个连通分支的平面图，则 n–m+f=k+1。 证明：针对每个连通分支而言，满足欧拉公式及：ni-mi+fi = 2,因此Σni – Σmi + Σfi = 2k.因为对G图而言只有一个外部面，但在针对每个连通分支引用欧拉欧式的时候都计算了一次外部面，因此外部面多计数k-1次，所以总面数比求和公式少k-1个面，因此有Σni – Σmi + Σfi-(k-1) = 2k-(k-1) 得 n–m+f=k+1■ 7. 证明：对K3.3的任何一边e，K3,3-e是平面图。同样，对K5的任何边e，K5-e也是平面图。 证明：因为K3,3-e，K5-e 可以画成平面图的形式，如下： ■ 8. 当m和n取什么值时Km,n是平面图？证明你的结论。 解：当m≤2，n≥1, 或n≤2，m≥1时，Km,n是平面图。因为： 当m≤2，n≥1时，如果m = 1 , 那么此图是一颗树，因此是平面图 如果ｍ＝２，那么可以将此图案如下方式图示： 20 去找 http://www.7zhao.net ｍ１ ｎ１ ｎ２ ｎｋ ｎｎ ｍ２ 当n≤2，m≥1时，同理是平面图 当m≥３同时n≥３时，Km,n是包含Ｋ３３的子图，因此不是平面图■ 9. 若一平面图与其对偶图同构，则称这个平面图为自对偶图。推导自对偶图必须满足的结点数n与边数m的关系，并找出一些自对偶图。 解：根据题意有，Ｇ与Ｇ同构，同时又是平面图，因此有如下关系式成立： ｎ－ｍ＋ｆ＝２ （１） 针对Ｇ图 ＊＊＊＊ ｎ－ｍ＋ｆ＝２ （２） 正对Ｇ图 ＊因为Ｇ与Ｇ同构，所以 ＊ ｎ＝ｎ＝ｆ，因此有：２ｎ－ｍ＝２，这就是自对偶平面图点和边需要满足的关系。下面是举例，请自己构造其对偶图并判别： ＊图例１ ■ 10.举例说明同构的平面图，其对偶图不一定同构。 解：举例如下： 图例２ 21 去找 http://www.7zhao.net 原图同构 ■ 对偶图不同构 11. 设某校某专业的学生在某学期共选修了n门选修课，期末考试前必须提前将这n门选修课程先考完，要求每天每人在下午考一门课，问至少需要几天考完这n门课？ 解：此类题可转化为求图的点色数的问题，可将课程集合作为图的点集合Ｖ＝｛ｖ１，ｖ２．．．ｖ．构造每门课程的学生选修集合Ｓ（ｖｉ），如果有同学同时选修了ｖｉ，和ｖｊ课程，ｎ｝则添加边（ｖｉ，ｖｊ）到图中。生成图Ｇ后，求Ｇ的点色数χ（Ｇ）即可■ 12. 在11题中，设n = 9，并且课程1和2，1和6，1和4，1和7，2和3，2和6，3和7，3和9，4和7，4和8，5和6，5和8，5和9都有人同时选，问至少几天能将9门课考完。 解：按１１题的要求，作出如下课程图： ｖ１ ｖ９ ｖ３ ｖ８ ｖ４ ｖ７ ｖ２ ｖ６ ｖ５ 所以至少需要３天才能考完■ 完成题目［１，２，３，４，５，6，7，８，９，１０，１１，１２］ 勘误：５题 － 简单平面（简单平面图） 22 去找 http://www.7zhao.net 习题十三 1. 构造(n, m)欧拉图使满足条件：(1) m和n奇偶性相同；(2) m和n奇偶性相反。 解： m和n奇偶性相同 m和n奇偶性相反 ■ 2. 设G = (V,E)是一个具有2k（k>0)个奇数度结点的连通图。证明:G中必存在k条边不相重的简单道路P1,P2,…,Pk,使得E = E(P1)∪E(P2)∪ …∪E(Pk)。 证明：只要将这2k个奇度点分成两个集合V1 ={v1,v2…vk}，V2={u1,u2…uk},然后添加k条边（vi，ui），将G图变换成欧拉图G`。求出G` 的欧拉回路C，将C中的添加的k 条边删除，得到k条简单道路，这k 段简单道路包含了G中的全部边，结论得证■ 3. 设G = (V,E)是不含奇度结点的非平凡图。证明:G中必有k个边不相重的回路C1,C2,…,Ck,使得E = E ( C1) ∪ E ( C2 ) ∪ …∪E( Ck)。 证明：由题设可知，图G的每个分支是欧拉图，因此可求出每个分支欧拉回路Ci，且这些欧拉回路没有重复边，结论得证■ 4. 设计一个由9个a,9个b,9个C组成的环形排列,使得由{a,b,c}组成的字长为3的27字中的每一个在排列中恰好出现一次。 解：由{a,b,c}组成的字长为3的串，一共有27个，分别为： 23 去找 http://www.7zhao.net {aaa,aab,aac,aba,abb,abc,aca,acb,acc,baa,bab,bac,bba,bbb,bbc,caa,cab,cac,cba,cbb,cbc,cca,ccb,cccc},题意为，将9个a,9个b,9个c组成环形排列，在这个环形排列中，任意不同的排列在一起的三个字母按相同的顺序写出来，都不相同。我们可以将{a,b,c}组成的字长为2的串{aa,ab,ac,ba,bb,bc,ca,cb,cc}作为有向图的节点，每个节点将有三条出边，出边分别表示在2字串上添加上{a,b,c}之母，并形成3字串。三条出边的汇入节点，分别是3字串的后两个字母所代表的2字节点，画出此图如下： a aa c b a ab b a ba a a a a b ca c a b a cc c c c b bb b c b cb c b c b bc c ac 由图可知，这是一个欧拉图，因为每个节点有3条出边，3条入边。找出一条欧拉回路，并将边上的字母写出及得到合乎要求的环排列：aaababcccaacbcabbcbbacaccb ■ 5. 在图13.10中求中国邮递员问题的解。 解：略，请参考书中解法■ 6. 设G是有两个奇度点的连通图,设计一个构造G的欧拉道路的算法。 解：step1: 添加连接两个奇度点的边 Step2: 调用一般的欧拉回路的算法 Step3: 在回路中删除添加的边■ 7. n为何值时，无向完全图Kn是欧拉图？n为何值时，无向完全图Kn仅存在欧拉道路而不存在欧拉回路？ 24 去找 http://www.7zhao.net 解：当n为大于2的奇数时，无向完全图Kn是欧拉图，因为每个节点的度数为偶数。当n为2时，K2，是唯一存在两个奇度点的完全图，因此此图只存在欧拉道路■ 8. n（n≥2）个结点的有向完全图中，哪些是欧拉图？ 解：n（n≥2）个结点的有向完全图中，每个都是欧拉图，因为每个节点都有相同的入度和出度，可以找到有向欧拉回路■ 9. 证明:凡有割点的图都不是哈密顿图。 证明：反证法，假设存在有割点v的图是哈密顿图，那么此图存在哈密顿圈。在此圈中删除割点v，那么剩下的节点依然连通。这和割点的定义相矛盾，所以题设命题成立■ 10. 证明: 4k+l阶的所有2k正则简单图都是哈密顿图。 证明：因为图是的正则简单图，因此对任意的u，v∈V, 有d(u) + d(v) = 4k. 根据定理13.4，存在哈密顿道路P= v1v2…v4k+1. 1）如果 v1v4k+1∈E, 则v1v2…v4k+1v1构成一个H圈； 2）如果v1v4k+1E，则是v1的邻接点，那么必为v4k+1的邻接点。否则，v4k+1点度为4k-1-2k=2k-1,与题设矛盾。假设vit-1v4k+1∈E，那么可构造H圈如下：v1…vit-1v4k+1 v4k…vitv1 因此，此图为哈密顿图■ 11．在无向完全图Kn中有多少条没有公共边的哈密尔顿回路？ 解：1) 设n=2k+1,将节点编号为0,1,2…2k,并作如下图示， 1 2k 2k-1 2k-2 0 2 3 4 K+3 K+2 K+1 k 在上图中先取一条哈密顿回路为0,1,2,2k,3,2k-1,4,…k+3,k,k+2,k+1,0,然后将圆周上的结点按逆时针方向依次转动一个位置，然后可以得到另一条回路为：0,2,3,1,4,2k,5,…k+4,k+1,k+3,k+2,0;显然，这两条回路是没有公共边。继续这样做下去，共可产生条无公共边的哈密顿回路。 25 去找 http://www.7zhao.net 若n=2k+2,那么只要在中间增加一个结点ｕ，就可以同样地得到条无公共边的哈密顿回路■ 12. 11个学生打算几天都在一张圆桌上共进午餐，并且希望每次午餐时每个学生两旁所坐的人都不相同，问11人共进午餐最多能有多少天？ 解：将１１个学生分别用结点表示，由于每个同学都可能邻座，因此每两个结点之间都有一条边，因此得到无向完全图Ｋ１１，每次午餐时学生都按照一条哈密顿回路落座，如果两条哈密顿回路有公共边，则公共边端点所代表的学生就是相邻的。因此上述问题转化为求Ｋ１１有多少条无公共边的哈密顿回路问题，利用１１题的结论，共有(11-1)/2=5条无公共边的哈密顿回路，因此这１１个学生共进午餐最多能有５天■ 13. 假定在n个人的团体中,任何2人合起来认识其余的n-2个人。证明: (1)这n个人可以排成一排,使得站在中间的每个人的两旁都是自己认识的人,站在两端的人旁边各有1个认识的人； (2)当月时,这n个人可以围成一个圆圈,使得每个人两旁都是自己所认识的人。 证明：因为任意两个人加起来认识其余的ｎ－２个人，那么每个人至少认识n-2个人。否则，设ｖ不认识ｕ，ｔ两人，那么ｕ和ｔ两个人将不能认识完剩下的ｎ－２个人，矛盾。当ｎ≥3时，将n个人看成图的结点，相互认识则在相关两个结点间有一条边，构成一个简单无向图G。此图中，任何两个结点的点度之和 d(u)+d(v)≥2(n-2)≥n-1,因此存在哈密顿道路，即这n个人可以排成一排,使得站在中间的每个人的两旁都是自己认识的人,站在两端的人旁边各有1个认识的人； 当n≥4, 任何两个结点的点度之和 d(u)+d(v)≥2(n-2)≥n,因此图中存在哈密顿回路，即这n个人可以围成一个圆圈,使得每个人两旁都是自己所认识的人■ 14. 设G是(n, m)简单图。若 ,证明G必是哈密顿图。 证明：假设此图中存在两个点v,u 其点度之和d(v)+d(u)≤n-1,那么剩余n-2个结点的点度之和最大值为(n-2)(n-3) + n-1,那么整个图的最大点度之和为(n-2)(n-3)+n-1+n-1=n2-3n+4,但根据题设条件，点度之和Σd(u) = 2m ≥n2-3n+6.矛盾，因此任意两结点点度之和d(v)+d(u)≥n，因此图G必是哈密顿图■ 15. 用两种以上的办法判别图13.11不是哈密顿图。 解： 方法1 ：删点法，如下 26 去找 http://www.7zhao.net 删除任何结点之前的原图 删除黑色结点之后 由上图可知，删除7个黑色点后，此图变成为具有9个分支的子图，根据哈密顿图的必要性判定定理ω(G-S)≤|S|可知，此图不是哈密顿图。 方法2：根据平面哈密顿图的面度公式：此图只有4度面，因此如果是哈图，则必须满足其中，代表内部面数，代表外部面数。但是，面的总数是13，无论如何不能成立，因此不是哈密顿图■ 16. 证明:图13.12中不存在同时包含边e1和e2的哈密顿图。（请冯老师帮忙证明下） 17. 对于下面给出的权阵,试用分枝定界法求对应的最优哈密顿圈。 解：略，请参考教材的算法实例■ 27