第10章习题答案

1、习题10 1.(1)图G的度数列为2、2、3、3、4，则G的边数是多少？(2)3、3、2、3和5、2、3、1、4能成为图的度数列吗？为什么？(3)图G有12条边，度数为3的结点有6个，其余结点的度数均小于3，问图G中至多有几个结点？为什么？解 (1)设G有m条边，由握手定理得2m2233414，所以G的边数7条。(2)由于这两个序列中有奇数个是奇数，由握手定理的推论知，它们都不能成为图的度数列。(3) 由握手定理得2m24，度数为3的结点有6个占去18度，还有6度由其它结点占有，其余结点的度数可为0、1、2，当均为2时所用结点数最少，所以应由3个结点占有这6度，即图G中至多有9个结点。2.若有

2、n个人，每个人恰有3个朋友，则n必为偶数。证明 设、表示任给的n个人，以、为结点，当且仅当两人为朋友时其对应的结点之间连一条边，这样得到一个简单图G。由握手定理知3n必为偶数，从而n必为偶数。3.判断下列各非负整数列哪些是可图化的？哪些是可简单图化的？(1)(1，1，1，2，3)。(2)(2，2，2，2，2)。(3)(3，3，3，3)。(4)(1，2，3，4，5)。(5)(1，3，3，3)。解 由于非负整数列d(d1，d2，dn)是可图化的当且仅当0(mod 2)，所以(1)、(2)、(3)、(5)能构成无向图的度数列。(1)、(2)、(3)是可简单图化的。其对应的无向简单图如图所示。(5)是

3、不可简单图化的。若不然，存在无向图G以为1，3，3，3度数列，不妨设G中结点为、，且d()1，d()d()d()3。而只能与、之一相邻，设与相邻，于是d()d()3不成立，矛盾。4.试证明图10-48中的两个无向图是不同构的。证明 因为两图中都有4个3度结点，左图中每个3度结点均与2个2度结点邻接，而右图中每个3度结点均只与1个2度结点邻接，所以这两个无向图是不同构的。5.在图同构意义下，试画出具有三个结点的所有简单有向图。解 具有三个结点的所有非同构的简单有向图共16个，如图所示，其中(8)(16)为其生成子图。6.给定无向完全图G，且|V|4。在图同构意义下，试求：(1)G的所有子图。(2

4、)G的所有生成子图。解 (1)G的所有子图如图所示。(2)图(8)(18)是G的所有生成子图。7.(1)试给出一个五个结点的自补图。(2)是否有三个结点或六个结点的自补图。(3)一个图是自补图，则其对应的完全图的边数必是偶数。(4)一个自补图的结点数必是4k或4k1。解 (1)五个结点的图G与它的补图如图所示。对G与建立双射：，。显然这两个图保持相应点边之间的对应的关联关系，故G。因此，G是五个结点的自补图。(3)设图G是自补图，有m条边，G对应的完全图的边数为s，则G对应的补图的边数为sm。因为G，故边数相等，即有msm，s2m，因此G对应的完全图的边数s为偶数。(2)由(3)知，自补图对应

5、的完全图的边数为偶数。n个结点的完全图的边数为n(n1)，当n3或n6时，的边数为奇数，因此不存在三个结点或六个结点的自补图。(4)设G为n阶自补图，则需n(n1)能被2整除，因此n必为4k或4k1形式。8.一个n(n2)阶无向简单图G中，n为奇数，已知G中有r个奇数度结点，问G的补图中有几个奇数度结点？解 由G的补图的定义可知，G为，由于n为奇数，所以中各顶点的度数n1为偶数。对于图G的任意结点，应有也是的顶点，且n1，由于n1为偶数，所以和奇偶性相同，因此若G中有r个奇数度结点，则中也有r个奇数度结点。9.画出4阶无向完全图K4的所有非同构的生成子图，并指出自补图来。解 下图中的11个图是

6、K4的全部的非同构的生成子图，其中(7)为自补图。10.设图G中有9个结点，每个结点的度不是5就是6。试证明G中至少有5个6度结点或至少有6个5度结点。证明 由握手定理的推论可知，G中5度结点数只能是0、2、4、6、8五种情况（此时6度结点数分别为9、7、5、3、1）。以上五种情况都满足至少5个6度结点或至少6个5度结点的情况。11.证明3度正则图必有偶数个结点。证明 设G为任一3度正则图，有n个结点、，则所有结点度数之和3n。若n为奇数，则3n也为奇数，与握手定理矛盾。故n为偶数。12.设G为至少有两个结点的简单图，证明：G中至少有两个结点度数相同。证明 若G中孤立结点的个数大于2，结论显然

7、成立。若G中有1个孤立结点，则G中至少有3个结点，因而不考虑孤立结点，就是说G中每个结点的度数都大于等于1。又因为G为简单图，所以每个结点的度数都小于等于n-1。因而G中结点的度的取值只能是1，2，n-1这n个数。由抽屉原理可知，取n-1个值的n个结点的度至少有两个是相同的。13.给定无向图G如图10-49所示，试求：(1)从a到d的所有基本路。(2)从a到d的所有简单路。(3)长度分别是最小和最大的基本回路。(4)长度分别是最小和最大的简单回路。(5)从a到d的距离。(6)g(G)、l(G)、d(G)、D(G)分别是多少？解 (1)从a到d的所有基本路共有10条：abd，abcd，abed，

8、abced，abecd，afed，afecd，afebd，afebcd，afecbd。(2)从a到d的所有简单路共有14条：除（1）中的10条外还有abcebd，abecbd，afebced，afecbed。(3)长度最小的基本回路共4个：bceb，bdeb，cdec，bcdb。长度最大的基本回路共1个：abdcefa。(4)长度最小的简单回路共4个：bceb，bdeb，cdec，bcdb。长度最大的简单回路2个：abcebdefa，afebcedba。(5)从a到d的距离为2。(6)g(G)2，l(G)2，d(G)2，D(G)4。14.给定有向图G如图10-50所示，试求：(1)各结点的出度

9、、入度和度。(2)从a到d的所有基本路和简单路。(3)所有基本回路和简单回路。解 (1)d+(a)2，d-(a)1，d+(b)1，d-(b)2，d+(c)1，d-(c)1，d+(d)2，d-(d)2，d+(e)1，d-(e)1。(2)从a到d的基本路2条：ad，abd。从a到d的简单路5条：ad，abd，adcbd，adead，adeabd。(3)基本回路共3个abdea，adea，bdcb.简单回路共4个：abdea，adea，bdcb，adcbdea。15.(1)若无向图G中只有两个奇数度结点，则这两个结点一定是连通的。(2)若有向图G中只有两个奇数度结点，它们一个可达另一个结点或互相可达

10、吗？证明 (1)设无向图G中只有两个奇数度结点和。从开始构造一条回路，即从出发经关联结点的边到达结点，若为偶数，则必可由再经关联的边到达结点，如此继续下去，每条边只取一次，直到另一个奇数度结点为止，由于图G中只有两个奇数度结点，故该结点或是或是。如果是，那么从到的一条路就构造好了。如果仍是，该回路上每个结点都关联偶数条边，而是奇数，所以至少还有一条边关联结点的边不在该回路上。继续从出发，沿着该边到达另一个结点，依次下去直到另一个奇数度结点停下。这样经过有限次后必可到达结点，这就是一条从到的路。(2)若有向图G中只有两个奇数度结点，它们一个可达另一个结点或互相可达不一定成立。下面有向图中，只有两

11、个奇数度结点和，和之间都不可达。16.若无向图G是不连通的，证明G的补图是连通的。证明 设无向图G是不连通的，其k个连通分支为、。任取结点、G，若和不在图G的同一个连通分支中，则，不是图G的边，因而，是图的边；若和在图G的同一个连通分支中，不妨设其在连通分支（1）中，在不同于的另一连通分支上取一结点，则，和，都不是图G的边，因而，和，都是的边。综上可知，不管那种情况，和都是可达的。由和的任意性可知，是连通的。17.完成定理10.11的证明。证明 充分性：若连通图G中存在结点u和w，使得连接u和w的每条路都经过，则在子图G中u和w必不可达，故是G的割边。必要性：若是G的割边，则G至少有两个连通分

12、支G1和G2。任取uV1，wV2，因为G连通，故在G中必有连接u和w的路G，但u、w在G中不可达，因此G必通过，即u和w之间的任意路必经过。18.完成定理10.16的证明。证明 先证任一结点至少位于一个单向分图中。任给一结点，若是孤立结点，则含的平凡图即为单向分图。若不是孤立结点，则必有一个结点，使得与有一弧与它们联结。此时若有单向分图，|3，使，且，那么结论成立；若不存在这样的，则由，和就构成一个单向分图。因此，任何结点至少位于一个单向分图中。其次证明，任何一条弧至少位于一个单向分图中。任给一弧，其关联的结点和。若存在一单向分图，|3，使，且，那么结论成立。否则，和就构成一个单向分图。综上可

13、知，任一弧至少位于一个单向分图中。19.完成定理10.17的证明。证明 显然任一结点和任一弧都位于一个弱分图中。假设有一结点位于两个不同的弱分图和中，即。由于略去弧的方向后，中所有结点与可达，中所有结点也与可达，故与中所有结点可达，这与和为弱分图矛盾，故任一结点不可能包含于不同的弱分图中，即任一结点能且只能位于一个弱分图中。假设一弧位于两个不同的弱分图中，该弧所关联的两个结点也位于两个不同的弱分图中，这是不可能的，因此任一弧也只能位于一个弱分图中。20.给出3个4阶有向简单图D1、D2、D3，使得D1为强连通图；D2为单向连通图但不是强连通图；D3是弱连通图但不是单向连通图，当然更不是强连通图

14、。解 图中得（a）为强连通图；（b）为单向连通图但不是强连通图；（c）是弱连通图但不是单向连通图，当然更不是强连通图。21.一个有向图D是单向连通图，当且仅当它有一条经过每一个结点的路。证明 充分性。给定有向图D，如果D有一条经过每一个结点的路为，这时V，E，E，边（11）以为起点，以为终点。任给两个结点、V，不妨设，则就是从结点到的路，故D是单向连通的。必要性。对结点数进行归纳。当1或2时，单向连通图显然有一条经过每一个结点的路。设时，有一条经过每一个结点的路，其中结点可能有重复，这条路的下标只表示该路所经过结点的次序，显然。当1时，取一结点，在图中删去结点，使D还是单向连通图。根据归纳假设

15、，D有一条经过每一个结点的路。令max|到有路，min|到有路。假如1，则必有满足。由于图D是单向连通的，与之间必有路。如果该路是从到，则与max|到有路矛盾。如果该路是从到，则与min|到有路矛盾。故而1不可能，只能是1。当1时，有经过每个结点的路。当时，有经过每个结点的路。22.设e为图G中的一条边，w(G)为G的连通分支数，证明w(G)w(Ge)w(G)1。证明 设e为图G的第个连通分支的一条边。若e不是的割边，则e仍然连通，因而G的连通分支数不变，即w(G)w(Ge) （1）若e是的割边，则e有且仅有两个连通分支，因而Ge比G多一个支连通分支，即w(G)1w(Ge) （2）由（1）和（

16、2）可得w(G)w(Ge)w(G)1。23.设G是n阶无向简单图，有m条边，p个连通分支，证明npm(np)(np1)/2。证明 （1）首先证明npm。对边数m做归纳法。m0时，G为零图，pn，np0，此时结论显然成立。设mk（k1）时结论成立，要证m3时结论成立。在G中找一个边割集，不妨设这个边割集中的边为，（1），设G1G，则G1的连通分支数为p1，边数为m1m（1），由归纳假设得n（p1）mm1，于是npm。（2）再证m(np)(np1)/2。为证明此不等式，不妨设G的各连通分支都是完全图，因为在这种情况下边数最多。而在1个连通分支都是完全图的情况下，又以p1个为（平面图），一个np1阶

17、完全图时边数最多，此时的边数为(np)(np1)/2。为此只需证明下面事实：设和是G的两个连通分支（1）。用和分别代替和，所得图的结点数和连通分支数没变，但边数增加了。证明如下：(1)(1)(2)(1)(1)10综上所述就证明了结论。24.设G为非平凡有向图，若对V的任一非空子集S，G中起始结点在S中，终止结点在VS中的有向边都至少有k条，则称G是k条边连通的。证明：非平凡有向图G是强连通它是1边连通的。证明 必要性。设G是强连通的，此时若从S到VS没有有向边，则S中的任一结点u到VS中的任一结点v均没有有向路，从而与G是强连通的矛盾。所以从S到VS至少有一条有向边。故G是1边连通的。充分性。

18、设G是1边连通的。任意u、vV，u到Vu至少有一条边，设为uu1，而u，u1到Vu，u1至少有一条边uu2或u1u2。无论那种情况都有从u到u2的有向路。因G中结点有限，所以通过如上递归地求解，一定有u到v的有向路。故G是强连通的。25.证明在n个结点的连通图G中，至少有n1条边。证明 不妨设G是无向连通图（若G为有向图，可略去边的方向讨论对应的无向图）。设G中结点为、。由连通性，必存在与相邻的结点，不妨设它为（否则可重新编号），连接和，得边，还是由连通性，在、中必存在与或相邻的结点，不妨设为，将其连接得边，续行此法，必与、中的某个结点相邻，得新边，由此可见G中至少有n1条边。26.试给出|V

19、|n，|E|(n1)(n2)的简单无向图G是不连通的例子。解 下图满足条件但不连通。27.一个n阶连通图G最少有几个割点？最多有几个割点？解 一个n阶连通图G为树时割点最少，只有一个；为完全图时割点最多，有n1个。28.求完全图Kn中任两点之间长为k的路的数目。解 设E为元素全为1的n阶矩阵，I为阶单位矩阵，于是Kn的邻接矩阵为AEI。Kn中长度为k的路的数目由决定。由于(EI)k所以，。29.有向图D如图10-51所示：(1)求D的邻接矩阵A。(2)D中v1到v4长度为4的路有多少？(3)D中v1到自身长度为3的回路有多少？(4)D中长度为4的路数为多少？其中有几条回路？(5)D中长度小于等

20、于4的路有多少？其中有多少条回路？(6)D是哪类连通图？解 (1) 求D的邻接矩阵为：且有 (2)由中可知，D中v1到v4长度为4的路有4条，分别为：、。(3)由中可知，D中v1到自身长度为3的回路只有1条，为。(4)D中长度为4的路总数为，其中对角元素之和为3，说明长度为4的回路为3条。(5)D中长度小于等于4的路总数为、中全体元素之和：710131646，其中回路数为：13138。(6)由可知，D是单向连通图。30.有向图G如图10-52所示，试求：(1)求G的邻接矩阵A。(2)求出A2、A3和A4，v1到v4长度为1、2、3和4的路有多少？(3)求出ATA和AAT，说明ATA和AAT中的

21、第(2，2)元素和第(2，3)元素的意义。(4)求出可达矩阵P。(5)求出强分图。解 (1)求G的邻接矩阵为：(2)由于 所以v1到v4长度为1、2、3和4的路的个数分别为1、1、2、3。(3)由于 再由定理10.19可知，所以ATA的第(2，2)元素为3，表明那些边以为终结点且具有不同始结点的数目为3，其第(2，3)元素为0，表明那些边既以为终结点又以为终结点，并且具有相同始结点的数目为0。AAT中的第(2，2)元素为2，表明那些边以为始结点且具有不同终结点的数目为2，其第(2，3)元素为1，表明那些边既以为始结点又以为始结点，并且具有相同终结点的数目为1。(4)因为+，所以求可达矩阵为。(

22、5)因为，所以，构成G的强分图。31.画一个无向欧拉图，使它具有：(1)偶数个顶点，偶数条边。(2)奇数个顶点，奇数条边。(3)偶数个顶点，奇数条边。(4)奇数个顶点，偶数条边。解 (1)n（n为偶数，且n2）阶圈都是偶数个顶点，偶数条边的无向欧拉图。(2)n（n为奇数，且n1）阶圈都是奇数个顶点，奇数条边的无向欧拉图。(3)在(1)中的圈上任选一个顶点，在此顶点处加一个环，所得图为偶数个顶点，奇数条边无向欧拉图。(4)在(3)中的圈上任选一个顶点，在此顶点处加一个环，所得图为奇数个顶点，偶数条边无向欧拉图。32.画一个无向图，使它是：(1)既是欧拉图，又是哈密尔顿图。(2)是欧拉图，但不是哈

23、密尔顿图。(3)是哈密尔顿图，但不是欧拉图。(4)既不是欧拉图，也不是哈密尔顿图。解 (1)n（n3）阶圈，它们都是欧拉图，又是哈密尔顿图。(2)给定k（k2）个长度大于等于3的初级回路，即圈，。将中某个顶点和中的某个顶点重合，但边不重合，中某个顶点和中的某个顶点重合，但边不重合，续行此法，直到将中某个顶点和中的某个顶点重合，但边不重合，设最后得到的连通图为，则是欧拉图，但不是哈密尔顿图。(3)在n（n4）阶圈中，找两个不相邻的顶点，在它们之间加一条边，所得图是哈密尔顿图，但不是欧拉图。(4)在(2)中的图中，设存在长度大于等于4的圈，比如，在中找，两个不相邻的顶点，在它们之间加一条边，然后按

24、照（2）的方法构造图，则既不是欧拉图，也不是哈密尔顿图。33.(1)n为何值时，无向完全图Kn是欧拉图？n为何值时，Kn仅存在欧拉路而不存在欧拉回路？(2)什么样的完全二部图是欧拉图？(3)n为何值时，轮图Wn为欧拉图？解 (1)一般情况下，我们不考虑。n（n2）为奇数时，无向完全图Kn是欧拉图。Kn各结点的度均为n1，若使Kn为偶拉图，n1必为偶数，因而必n为奇数。K2仅存在欧拉路而不存在欧拉回路。(2)设为完全二部图，当、均为偶数时，为欧拉图。(3)设Wn（n4）为轮图，在Wn中，有n1个结点的度数为3，因而对于任何取值的n（n4），轮图Wn都不是欧拉图。34.证明：完全图K9中至少存在彼

25、此无公共边的两条哈密尔顿回路和一条哈密尔顿通路。证明 设为K9中一条哈密尔顿回路。令为K9删除中全部边之后的图，则中每个结点的度均为6。由定理10.26可知仍是哈密尔顿图，因而存在中的哈密尔顿回路（显然也是K9中的哈密尔顿回路，并且与无公共边）。再设为中删除中的全部边后所得图，为4正则图。由定理10.26可知具有哈密尔顿通路。设为中的一条存在哈密尔顿通路，显然、无公共边。事实上，可以证明在K9中存在4条边不重的哈密尔顿回路。可以证明：在K3中存在一条边不重合的哈密尔顿回路，K5中存在两条边不重合的哈密尔顿回路，K7中存在3条边不重合的哈密尔顿回路，一般情况下，K2k+1(k1)中最多可存在条边

26、不重合的哈密尔顿回路。35.已知a、b、c、d、e、f、g 7个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？解 用a、b、c、d、e、f、g 7个结点代表7个人，若两人能交谈（会讲同一种语言），就在代表它们的结点之间连无向边，所得无向图如下图（1），此图中存在哈密尔顿回路：，如图（2）粗边所示，于是按图（3）所示的顺序安排座位即可。36.证明：对于每个竞赛图D，至多改变一条边的方向后就可以变成哈密尔顿图。证明 由定理10.26可知D

27、中存在哈密尔顿通路，设D为n（n3）阶竞赛图，为中的一条哈密尔顿通路，若边在D中，则为D中一条哈密尔顿回路，故D为哈密尔顿图。否则边在D中，将改变方向得到边，于是D就变成了哈密尔顿图。37.给定简单无向图G，且|V|m，|E|n。试证：若n2，则G是哈密尔顿图。证明 若n2，则2nm23m6 （1）。若存在两个不相邻结点、使得d()d()m，则有2nm(m2)(m3)mm23m6，与（1）矛盾。所以，对于G中任意两个不相邻结点、都有d()d()m。由定理10.26可知，G是哈密尔顿图。38.设G是无向连通图，证明：若G中有割点或割边，则G不是哈密尔顿图。证明 若G中有割点，则G中至少有两个连通

28、分支，从而w(G)|，由定理10.25可知，G不是哈密尔顿图。若G中有割边，当G只有两个结点时，显然G不是哈密尔顿图。当G的结点数多余2时，从G中删除割边e之后至少有两个连通分支，其中一个连通分支含有割边e的一个端点且其结点个数大于1，于是w(G)|，由定理10.25可知，G不是哈密尔顿图。39.某次会议有20人参加，其中每个人都至少有10个朋友，这20人围一圆桌入席，要想使与每个人相邻的两位都是朋友是否可能？根据什么？解 可能。依题意，若用结点代表人，两人是朋友时相应结点之间连一条边，则得到一个无向图G，该题转化为求哈密尔顿回路问题。由于对任意、V，有d()d(v)101020，根据定理10

29、.26，G为哈密尔顿图，G中存在哈密尔顿回路，按此回路各点位置入席即为所求。40.设G是具有k(k0)个奇数度结点的无向连通图，证明G中边不重合的简单通路的最小数目是，它们包含G的全部边。证明 由握手定理的推论可知，k是偶数。对k做归纳法。(1)当k2时，由定理10.22可知，G中存在偶拉路，结论得证。(2)设k2r（r2）时结论成立，要证k为2r2时结论成立。设，为G中任意二奇度结点，由G的连通性可知，从到存在路径，删除上的全部边，得连通分支，。这些连通分支共含2r个奇度结点，设中含个奇度结点，则22r（1rs），且2r。由归纳假设可知，中存在条边不重合的简单通路，它们含中的所有边。于是G中

30、共含11r条边不重合的简单通路，它们含G中的全部边。41.甲、乙、丙、丁四位教师，分配他们教数学、物理，电工和计算机原理四门课。甲能教物理和电工，乙能教数学和计算机原理，丙能教数学、物理和电工，丁只能教电工，对他们的工作怎样分配？解 设.甲、乙、丙、丁四位教师分别用、表示，数学、物理，电工和计算机原理四门课分别用、表示，。若能教，令。所作图G，则G为二部图，如下图所示。易证满足“相异性条件”，且|，所以，存在到的完全匹配。图中粗线所示就是其一种分配方案。42.某杂志发表了7个征求答案的题目，当从读者寄来的解答中挑选每题的两个解答时，编者发现所有14个选出来的解答恰好是7个读者提出来的，而且每个

31、人正好提出了两个答案。试证明：编辑可以这样发表每道题的一个解答，使得在发表的解答中，这7个读者每个人都恰有一个解答。解 7个位读者分别用、表示，7个题目分别用、表示，。若为做解答，令。所作图G，则G为二部图。由已知条件可知中每个结点关联两条边，中每个结点也关联两条边，即G满足t2的“t条件”，所以存在到的完备匹配，又因为|，因而对于任意的到的完备匹配M，不存在M-非饱和点，故M也是完全匹配。即使得7个题目的7个解答分别由7个读者给出是办得到的。43.给定二部图G，且|V1V2|m，|E|n，证明nm2/4。证明 设|V1|m1，则|V2|mm1，于是nm1(mm1)m1m。因为，即，所以nm2

32、/4。44.设G是面数r小于12的简单平面图，G中每个结点的度数至少为3。(1)证明G中存在至多由4条边围成的面。(2)给出一个例子说明，若G中的面数为12，且每个结点的度至少为3，则(1)的结论不成立。证明 1)不妨设G是连通的，否则可以对它的每个连通分支进行讨论（因为每个连通分支均满足条件）。因而由偶拉公式有nmr2， （1）又由已知条件得r12且nm， （2）将（2）其代入（1）得2mm12，m30。 （3）若所有的面均至少由5条边围成，则5r2m，rm， （4）将（2）、（4）代入（1）得2mmm，m30。 （5）（3）与（5）是矛盾的，因而必存在至多由4条边围成的面。2)十二面体图有

33、12个面，每个结点均为3度，每个面由5条边围成，并没有4条边围成的面。45.把平面分成b个区域，每两个区域都相邻，问b最大为几？解 在每个区域放一个结点，当两区域相邻时就在相应的两个结点之间连一条线，如此构造了一个平面图且是完全图，而最大的平面完全图为，所以b最大为4。46.设简单平面图G中结点数n7,边数m15，证明G是连通的。证明 反证法。设G为非连通的，具有k2个连通分支,。设的结点数为，边数为，1，2，。若存在1，则必为2，因为只有此时G为一个平凡图并上一个才能使其边数为15，可是不是平凡图，这矛盾于G为平面图这个事实，所以不存在1。若存在2，中至少有一条边（因为G为简单图），另外5个

34、结点构成时边数最多，但充其量为10条边，这与G有15条边矛盾。综上所述，必大于等于3，1，2，。由定理10.37可知，3（2）36，1，2，。求和得36 （1）将n7,m15代入（1）得15216，于是1，这与k2矛盾。至此证明了G必为连通图。47.设G是边数m小于30的简单平面图，试证明G中存在结点v使得d(v)4。解 不妨设G是连通的，否则因为它的每个连通分支的边数都应小于30，因此可对它的每个连通分支进行讨论，所以可设G是连通的。若G中无回路，则G必为树，结论显然成立。若G中有回路，由于G为简单图，因而G中每个面至少由3个边围成，由定理10.37有m3n6。下面用反证法证明结论。若不然，

35、G中所有结点的度数均大于等于5，由握手定理可知2m5n，所以nm，将其代入m3n6得m3m6，于是m30，与m30矛盾，所以一定存在结点v使得d(v)4。48.设G为有k(k2)个连通分支的平面图，G的平面图的每个面至少由f(f3)条边围成，则m(nk1)。解 设G的各面的边界长度之和为。G的每条边在计算时，均提供2，又因为G的平面图G 的每个面至少由f条边围成，所以f2m。又因为k1mn，将其代入f2m得f(k1mn)2m，整理得m(nk1)。49.证明：平面图G的对偶图G*是欧拉图G中每个面的次数均为偶数。证明 显然G*是连通图，设为G*的任一结点，位于G的面R中，由于R由偶数边围成，所以

36、d()为偶数，由的任意性可知，G*是欧拉图。50.在由6个结点，12条边构成的连通平面图G中，每个面由几条边围成？为什么？解 每个面由3条边围成。因图中结点数和边数分别为n6，m12。根据欧拉公式nmr2得r8。又因为2m24，而简单连通平面图的每个面至少由3条边围成，所以G中每个面由3条边围成。51.给定连通简单平面图G，且|V|6，|E|12。证明：对任意fF，d(f)3。证明 由偶拉公式得|V|E|F|2，所以|F|2|V|E|8，又由定理10.31得2|E|24。若存在fF，使得d(f)3，则3|F|2|E|24，于是|F|8，与|F|8矛盾。故对任意fF，d(f)3。52.证明：不存

37、在具有5个面，每两个面都共享一条公共边的平面图G。证明 若存在这样的平面图G，设G的对偶图为G*，则G*也是平面图。由于G有5个面，所以G*具有5个结点。设为G*的任一结点，设它位于G的面R中。由于R与其余4个面均有公共边，所以与其余面中的结点均相邻，于是d()4，而且G*为简单图，所以G*必为，可是为非平面图，这与G*为平面图矛盾。53.已知一棵无向树T有三个3度结点，一个2度结点，其余的都是1度结点。(1)T中有几个1度结点？(2)试画出两棵满足上述度数要求的非同构的无向树。解 (1)设T中有x个1度结点，则T中结点数n31x，T中边数m31x13x。T中各结点度数之和33211x11x。

38、由握手定理得11x2m62x，于是x5。所以T中有5个1度结点。(2)下图中所示的两棵树均满足要求，但它们是不同构的。54.一棵无向树T有ni个度数为i的结点，i2，3，k，问有多少个1度结点？解 设T中有x个1度结点，则T中结点数nx，T中边数mx1。T中各结点度数之和1xx。由握手定理得2(x1)x，于是x222。所以T中有2个1度结点。55.证明恰有两个结点的度数为1的树必为一条通路。证明 设T为一棵具有两个1度结点的树（n，m），则mn1且有2m2(n1)。又T连通且除两个1度结点外，其他结点度数均大于等于2，而2，有2(n1)2，故2(n1)。因此n2个分支结点的度数都恰为2，即T为

39、一条通路。56.设无向图G是由k(k2)棵树构成的森林，至少在G中添加多少条边才能使G成为一棵树？解 设G的k个连通分支为、，设结点，i1，2，k。在G中添加边(，)，i1，2，k，设所得图为，则连通且无回路，因而是树。所以边的添加数k1是使得G为树的最小数目。57.试画出4个结点和5个结点的所有非同构的无向树。解 4个结点的所有非同构的无向树有2棵，如图（1）和（2）所示。5个结点的所有非同构的无向树有3棵，如图（3）、（4）和（5）所示。58.设G是连通图且eE，试证明：e是G的割边e包含在G的每棵生成树中。证明 设e包含在G的每棵生成树中，但e不是G的割边。在图G中删去e得图G，G 仍是

40、连通图。对G来说必有一棵生成树T，T中不包含边e，与假设矛盾。设边e不是G的割边，删去e，G就分成两个互不连通的子图G1和G2。对于G的任一一棵生成树T，由于T是连通图，故连结G1和G2之间的唯一边e必在T中。59.如何由有向图G的邻接矩阵A判定G是否是根树，若是根树，如何定出它的树根和树叶。解 一个有向图G为根树，它的邻接矩阵A必须满足：1）所有主对角元素为0；2）矩阵中有一列元素全为0，所有其它列中都恰有一个1。如果一个邻接矩阵对应的有向图是根树，那么全0列对应的结点为根。而全0行对应的结点为树叶。60.设T为任意一棵正则二叉树，m为边数，t为树叶数，试证明m2t2，其中t2。证明 设T中

41、结点数为n，分支结点数为i，根据正则二叉树的定义得下面等式成立：nit (1)m2i (2)mn1 (3)由以上三式整理得m2t2。61.证明一棵完全二叉树必有奇数个结点。证明 设完全二叉树T有n个结点，m条边。依定义，T中每个分支点都关联两条边，所以m必为偶数。又由T是树，有nm1，故n为奇数。因此，完全二叉树必有奇数个结点。62.画出所有不同构的高为2的二叉树，其中有多少棵正则二叉树？有多少棵满二叉树？解 高为2的所有不同构的二叉树有7棵，如图所示。其中有2棵正则二叉树，如图(5)和(7)；1棵满二叉树如图(7)。63.求带权2、3、5、7、8的最优二叉树及其权，并求该二叉树对应的2元前缀

42、码。解 (1)构造最优二叉树的全部过程如图所示。树的权为(23)3(578)255。(2)该二叉树对应的2元前缀码为000，001，01，10，11。64.(1)求带权为1、1、2、3、3、4、5、6、7的最优三叉树。(2)求带权为1、1、2、3、3、4、5、6、7、8的最优三叉树。解 求最优叉树的Huffman算法：为分支数，t为树叶数，(1)若为整数，求最优叉树的算法与求最优2叉树的算法类似，只是每次取个最小的权。(2)若-1除t-1余数s不为0，1s-1，将s+1个较小的权对应的树叶为兄弟放在最长的通路上，然后的算法同(1)。(1)所求树的树叶数t9，分支数3。4，说明所求3叉树为正则3叉树。由Huffman算法得3叉树如图所示。(2) 所求树的树叶数t10，分支数3。，于是-1除t-1余数为1，由Huffman算法得3叉树如图所示。65.在下面给出的3个符号串集合中，哪些是前缀码？哪些不是前缀码？若是前缀码，构造二叉树，其树叶代表二进制编码。若不是前缀码，则说明理由。(1)0，10，110，1111。(2)1，01，001，000。(3)1，11，101，001，0011。解 (1)和(2)中的各字符串互不为前缀，因而(