第四次辅导-欢迎访问安徽广播电视大学网站！

1《计算机数学基础(1)》第四单元辅导本单元重点：欧拉图和哈密顿图、平面图和树的基本概念.代数运算及性质，群的概念，交换群和循环群.一、重点内容1.欧拉图欧拉通路(回路)与欧拉图通过图G的每条边一次且仅一次，而且走遍每个结点的通路(回路)，就是欧拉通路(回路).存在欧拉回路的图就是欧拉图.欧拉回路要求边不能重复，结点可以重复.笔不离开纸，不重复地走完所有的边，且走过所有结点，就是所谓的一笔画.欧拉图或通路的判定(1)无向连通图G是欧拉图G不含奇数度结点(G的所有结点度数为偶数):(定理1)(2)非平凡连通图G含有欧拉通路G最多有两个奇数度的结点；(定理1的推论)(3)连通有向图D含有有向欧拉回路(即欧拉图)D中每个结点的入度＝出度连通有向图D含有有向欧拉通路D中除两个结点外，其余每个结点的入度＝出度，且此两点满足deg－(u)－deg＋(v)＝1.(定理2)2.哈密顿图哈密顿通路(回路)与哈密顿图通过图G的每个结点一次，且仅一次的通路(回路)，就是哈密顿通路(回路).存在哈密顿回路的图就是哈密顿图.判断哈密顿图是较为困难的.哈密顿图的充分条件和必要条件(1)在无向简单图G=V,E中V3,任意不同结点VvuGvu)deg()deg(,,,则G是哈密顿图.(充分条件，定理4)(2)有向完全图D＝V,E,若3V，则图D是哈密顿图.(充分条件，定理5推论)(3)设无向图G=V,E,V1V，则P(G－V1)V1(必要条件，定理3)若此条件不满足，即V1V，使得P(G－V!)V1,则G一定不是哈密顿图(非哈密顿图的充分条件).3.平面图平面图一个图能画在平面上，除结点之外，再没有边与边相交.面、边界和面的次数由连通平面图G的边围成的其内部不含G的结点和边的区域是面，常用r表示.围成面的各边组成的回路是边界.边界回路的长度是面的次数，记作deg(r).重要结论(1)平面图ereEvVEVGrii2)deg(,,,,1则(所有面的次数之和＝边的2倍)(定理6).(2)欧拉公式：平面图,,,,eEvVEVG面数为r，则2rev(结点数与面数之和＝边数＋2)(定理7)(3)平面图633,,,,veveEvVEVG，则若(定理8)判定条件：图G是平面图的充分必要条件是G不含与K3，3或K5在2度结点内同构的子图.4.树树连通无回路的无向图.2树的判别图mEnVEVT,,,,T是树的充分必要条件是(六个等价定义)(定理14):(1)T是无回路的连通图；(2)图T无回路且m＝n－1；(3)图T连通且m＝n－1(4)图T无回路，若增加一条边，就得到一条且仅一条回路；(5)图T连通，若删去任一边，G则不连通；(6)图T的每一对结点之间有一条且仅有一条通路.生成树图G的生成子图是树，该树就是生成树.权与带权图n个结点的连通图G，每边指定一正数，称为权，每边带权的图称为带权图.G的生成树T的所有边的权之和是生成树T的权，记作W(T).最小生成树带权最小的生成树.有向树有向图删去边的方向为树，该有向图就是有向树.根树与树根非平凡有向树，恰有一个结点的入度为0(该结点为树根)，其余结点的入度为1，该树为根树.每个结点的出度小于或等于2的根树为二元树(二叉树)；每个结点的出度等于0或2的根树为二元完全树(二叉完全树)；每个结点的出度等于2的根树称为正则二元树(正则二叉树).哈夫曼树用哈夫曼算法得到的最优二叉树.4.有关树的求法生成树的破圈法和避圈法求法；最小生成树的克鲁斯克尔求法；哈夫曼树的哈夫曼求法.二、实例例6.1判别图6－1的两幅图是否可以一笔画出？解在图6－1(a)中，deg(v1)=deg(v2)=deg(v3)＝3有两个以上的结点的度为3.故在(a)中不存在欧拉通路，不能一笔画出.在图6－1(b)中，deg(A)=2,deg(B)=deg(C)=deg(D)=4，deg(E)=deg(F)=3只有两个奇数度的结点，所以存在欧拉通路，可以一笔画出.一条欧拉通路，如EDBEFCABCDF.例6.2判定图6－2中，两个图是否有欧拉回路？若有请把欧拉回路写出来.解在图D1中，v1点的出度为2，入度为0；v5的出度为0，入度为2，且这两点出度与入度之差不等于1，所以，图D1不存在欧拉通路，图D1不是欧拉图.图D2中，各个结点的出度、入度都相等2，所以存存欧拉回路，图D2是欧拉图.一个欧拉回路为v1av2bv3fv1ev3cv4hv2gv4dv1例6.3指出图6－3各图是否哈密顿图，有无哈密顿通路，回路？解(1)容易判断，存在哈密顿回路，故是哈密顿图.(2)只有哈密顿通路，无哈密顿回路，故不是哈密顿图.(3)无哈密顿通路，显然不是哈密顿图.v4v5EFAv2v3BCv1D（a）(b)图6－1v1v1dv4v2v5fhagecv3v4v2bv3D1D2图6－23例6.4画出具有下列条件的有5个结点的无向图.(1)不是哈密顿图，也不是欧拉图；(2)有哈密顿回路，没有欧拉回路；(3)没有哈密顿回路，有欧拉回路；(4)是哈密顿图，也是欧拉图.解作图如图6－4(不唯一).(1)(2)(3)(4)图6－4例6.5判断图6－5是否为平面图？解在G中，将(v1,v4)和(v3,v4)改画成如虚线所示.可见G是平面图.v1例6.6在具有n个结点的完全图Kn中，需要删去多少条边才能v2v3.得到树？v4v5G图6－5解n个结点的完全图共有2n条边，而n个结点的树共有n－1条边.因此需要删去2)2)(1()1(2nnnn条边后方可得到树.例6.7设G是图，无回路，但若外加任意一条边于G后，就形成一回路.试证明G必为树.证明由树的定义可知，只需证G连通即可.任取不相邻两点u,v,由题设，加上边u,v就形成一回路，于是去掉边u,v,从u到v仍有路u,…,v，即u,v连通，由u,v的任意性可知，G是连通的，故G必是树.例6.8如图6－6是有6个结点a,b,c,d,e,f的带权无向图，各边的权如图所示.试求其最小生成树.解构造连通无圈的图，即最小生成树，.用克鲁斯克尔算法：第一步：取ab＝1；第二步：取af=4；第三步：取fe=3；第四步：取ad=9；第五步：取bc=23.如图6－7。权为1+4+3+9+23=30例6.9单项选择题(1)(2)(3)图6－3b23115c25a4f289163d15e图6－6b231ca4f93de图6－741.无向图G是欧拉图，当且仅当()(A)G的所有结点的度数为偶数(B)G的所有结点的度数为奇数(C)G连通且所有结点的度数为偶数(D)G连通且所有结点的度数为奇数答案：(C)解答：见本单元定理1.2.设mEnVEVG,,,为连通平面图且有r个面，则r＝()(A)m－n+2(B)n－m－2(C)n+m-2(D)m+n+2答案：(A)解答：见定理7欧拉公式.3.设G是5个结点的无向完全图，则从G中删去()条边可以得到树.(A)4(B)5(C)6(D)10答案：(C)解答：删去边的公式为2)2)(1()1(2nnnn.故选择(C)正确.4.在5个结点的二元完全树中，若有4条边，则有()片树叶。(A)2(B)3(C)5(D)4答案：(B)解答：二元完全树，即每个结点只有0个或2树枝的树，树根必有2个树枝，于是2个树枝只能其一又有2个树枝，而另一个就无树枝.满足5个结点4条边.可见有3片树叶.选择(B)正确.一般地，在二元完全树中，有m条边，t片树叶，则有m=2(t－1)5.图6－8是()(A)完全图(B)欧拉图(C)平面图(D)哈密顿图答案：(D)解答：因为n=6,每对结点度数之和大于或大于6，满足存在哈密顿回路的条件，故为哈密顿图.选择(D)正确.例6.10填空题1.设G是完全二叉树，G有15个结点，其中有8个是树叶，则G有条边，G的总度数是，G的分支点数是，G中度数为3的结点数是.答案：14；28；7；6.解答：可画图如图6－9.有8个树叶，15个结点的完全二叉树，2.连通有向图D含有欧拉回路的充分必要条件是答案：D中每个结点的入度＝出度.解答：见欧拉回路的判断方法，定理2.3.设G是n个结点的简单图，若G中每对结点的度数之和，则G一定是哈密顿图.答案：大于或等于n解答：见定理4.4.设G是有n个结点，m条边的连通图，要确定G的一棵生成树，必须删去G的条边.图6－8图6－95答案：m－n+1解答：见生成树的破圈或避圈求法.5.一个有向树T称为根树，若，其中，称为树根，称为树叶.答案：若有向图T恰有一个结点的入度为0，其余结点入度为1；入度为0的结点；入度为1的结点.解答：见根树、树根、树叶的定义.三、练习题1.在图6－10中，哪些是欧拉图？哪些是哈密顿图？哪些是平面图？(6)图6－102.设G是平面图，并且G的所有面的次数均为3，证明ve其中e是G的边数.v是G的结点数.3.(1)设G是无向图，如图6－11(1)，说明G不a3d是欧拉图；(2)求带权图，如图6－11(2)的最小生成树.5e64.将平面图G1，G2(如图6－－12)改写成不相交的形式.bc.(1)(2)5.已知有向图D的邻接矩阵为图6－110000000100000010110100000试作出D的图，并求关联矩阵6.(1)在1棵有2个2度结点，4个3度结点，uv(1)(2)11234G1G2图6－12(4)(3)(5)6其余为树叶的无向树中，应该有几片树叶？(2)画出两棵不同构的满足条件(1)的结点度数的无向树T1，T2.7.设G＝V,E是有p个结点，s条边的连通图，则从G中删去多少条边，才能确定图G的一棵生成树？8.求图6－13图G的对偶图.9.画出满足下列条件的图：(1)画一个有一条欧拉回路和一条哈密顿回路的图；(2)画一个有一条欧拉回路，但没有哈密顿回路的图；(3)画一条没有欧拉路，但有一条哈密顿回路的图.四、练习题答案1.(1)的图记作G1，从G1中删去结点u,v，得到G1的三个连通分支，有2},{3}),{(1vuvuGP由定理3的逆可知，G1不是哈密顿图.由于它是连通的，且无奇数度结点，由定理1可知，它是欧拉图，显然是平面图；(2)是平面图.由于它非连通，所以它不是欧拉图.也不是哈密顿图；(3)是平面图.因为无回路，所以它不是欧拉图，也不是哈密顿图；(4)是平面图.因为奇数度的结点超过2个，根据定理1的推论，该图不是欧拉图；在图中容易找到一条哈密顿回路，故是哈密顿图；(5)是平面图.因为无奇数度的结点，所以是欧拉图，又因为可以找到一条哈密顿回路，所以是哈密顿图.(6)不是平面图.又奇数度的结点多于2个，所以它不是欧拉图，可以找到一条哈密顿回路，是哈密顿图.2.因为G的所有面的次数为3，因此对G的任意面r，有deg(r)=3从而，)()deg(的面的个数表示的面是GrrrGr又根据定理6，G的所有面的次数之和等于其边数的2倍，即erGr的面是)deg(即er代入欧拉公式rev，eevve2.(1)因为G中各结点均为奇数度，由欧拉图的充分必要条件知，G不是欧拉图.(2)最小生成树为T1＝{a,b,c,d,e}，{(a,e),(d,e),(b,e),(b,c)}或用图形表示，如图6－14.图6－137adebc图6－14第3(2)题解答图4.改写后的图，如图6－155.图形如图6－16M(D)=