离散数学图论部分综合练习讲解

1离散数学图论部分综合练习1．设图G＝V,E，则下列结论成立的是()．A．deg(V)=2EB．deg(V)=EC．EvVv2)deg(D．EvVv)deg(2．图G如图一所示，以下说法正确的是()．A．{(a,d)}是割边B．{(a,d)}是边割集C．{(d,e)}是边割集D．{(a,d),(a,c)}是边割集3．如图二所示，以下说法正确的是()．A．e是割点B．{a,e}是点割集C．{b,e}是点割集D．{d}是点割集4．如图三所示，以下说法正确的是()．A．{(a,e)}是割边B．{(a,e)}是边割集C．{(a,e),(b,c)}是边割集D．{(d,e)}是边割集图三5．设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是()．图四A．（a）是强连通的B．（b）是强连通的C．（c）是强连通的D．（d）是强连通的6．设完全图Kn有n个结点(n≥2)，m条边，当（）时，Kn中存在欧拉回路．A．m为奇数B．n为偶数C．n为奇数D．m为偶数7．设G是连通平面图，有v个结点，e条边，r个面，则r=()．A．e－v＋2B．v＋e－2C．e－v－2D．e＋v＋2cabedf图一图二28．无向图G存在欧拉通路，当且仅当()．A．G中所有结点的度数全为偶数B．G中至多有两个奇数度结点C．G连通且所有结点的度数全为偶数D．G连通且至多有两个奇数度结点9．设G是有n个结点，m条边的连通图，必须删去G的()条边，才能确定G的一棵生成树．A．1mnB．mnC．1mnD．1nm10．无向简单图G是棵树，当且仅当()．A．G连通且边数比结点数少1B．G连通且结点数比边数少1C．G的边数比结点数少1D．G中没有回路．二、填空题1．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是．2．设给定图G(如图四所示)，则图G的点割集是．3．若图G=V,E中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为．4．无向图G存在欧拉回路，当且仅当G连通且．5．设有向图D为欧拉图，则图D中每个结点的入度．6．设完全图Kn有n个结点(n2)，m条边，当时，Kn中存在欧拉回路．7．设G是连通平面图，v,e,r分别表示G的结点数，边数和面数，则v，e和r满足的关系式．8．设连通平面图G的结点数为5，边数为6，则面数为．9．结点数v与边数e满足关系的无向连通图就是树．10．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去条边后使之变成树．11．已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为．12．设G＝V,E是有6个结点，8条边的连通图，则从G中删去条边，可以确定图G的一棵生成树．13．给定一个序列集合{000，001，01，10，0}，若去掉其中的元cabedf图四3素，则该序列集合构成前缀码．三、判断说明题1．如图六所示的图G存在一条欧拉回路．2．给定两个图G1，G2（如图七所示）：（1）试判断它们是否为欧拉图、汉密尔顿图？并说明理由．（2）若是欧拉图，请写出一条欧拉回路．图七3．判别图G(如图八所示)是不是平面图，并说明理由．4．设G是一个有6个结点14条边的连通图，则G为平面图．四、计算题1．设图GV，E，其中Va1,a2,a3,a4,a5,Ea1,a2，a2,a4，a3,a1，a4,a5，a5,a2（1）试给出G的图形表示；（2）判断图G是强连通图、单侧连通图还是弱连通图？2．设图G=V，E，V={v1，v2，v3，v4，v5}，E={(v1,v2)，(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)}，试（1）画出G的图形表示；（2）求出每个结点的度数；（3）画出图G的补图的图形．3．设G=V，E，V={v1，v2，v3，v4，v5}，E={(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)}，试v1v2v3v4v5v6v1v2v3v5v4dbacefghn图六v5v1v2v4v6v3图八4（1）给出G的图形表示；（2）求出每个结点的度数；（3）画出其补图的图形．4．图G=V,E，其中V={a,b,c,d,e}，E={(a,b),(a,c),(a,e),(b,d),(b,e),(c,e),(c,d),(d,e)}，对应边的权值依次为2、1、2、3、6、1、4及5，试（1）画出G的图形；（2）求出G权最小的生成树及其权值．5．设有一组权为2,3,5,7,11,13,17,19,23,29,31,试（1）画出相应的最优二叉树；（2）计算它们的权值．6．画一棵带权为1,2,2,3,4的最优二叉树,计算它的权．五、证明题1．若无向图G中只有两个奇数度结点，则这两个结点一定是连通的．2．设G是一个n阶无向简单图，n是大于等于2的奇数．证明图G与它的补图G中的奇数度顶点个数相等．3．设连通图G有k个奇数度的结点，证明在图G中至少要添加2k条边才能使其成为欧拉图．参考解答一、单项选择题1．C2．C3．A4．D5．D6．C7．A8．D9．A10．A二、填空题1．152．{f}，{c，e}3．W|S|4．所有结点的度数全为偶数5．等于出度6．n为奇数7．v-e+r=28．39．e=v-110．411．512．313．0三、判断说明题1．解：正确．因为图G为连通的，且其中每个顶点的度数为偶数．2．解：（1）图G1是欧拉图．因为图G1中每个结点的度数都是偶数．5图G2是汉密尔顿图．因为图G2存在一条汉密尔顿回路（不惟一）：a(a,b)b(b,e)e(e,f)f(f,g)g(g,d)d(d,c)c(c,a)a问题：请大家想一想，为什么图G1不是汉密尔顿图，图G2不是欧拉图。（2）图G1的欧拉回路为：（不惟一）：v1(v1,v2)v2(v2,v3)v3(v3,v4)v4(v4,v5)v5(v5,v2)v2(v2,v6)v6(v6,v4)v4(v4,v1)v13．解：图G是平面图．因为只要把结点v2与v6的连线(v2,v6)拽到结点v1的外面，把把结点v3与v6的连线(v3,v6)拽到结点v4,v5的外面，就得到一个平面图，如图九所示．4．解：错误．不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．”四、计算题1．解：（1）图G是有向图：（2）图G是单侧连通图，也是弱连通图．2．解：（1）图G如图十（3）deg(v1)=2deg(v2)=3deg(v3)=4deg(v4)=3deg(v5)=2（4）补图如图十一图十一a1a2a3a4a5v1v2v3v4v5v1v2v3v4v5v5v1v2v4v6v3图九63．解：（1）G的图形如图十二图十二（2）v1，v2，v3，v4，v5结点的度数依次为1，2，4，3，2（3）补图如图十三：图十三4．解：（1）G的图形表示如图十四：图十四（2）粗线表示最小的生成树，如图十五如图十五最小的生成树的权为1+1+2+3=7：5．解：（1）最优二叉树如图十六所示：7方法（Huffman）：从2,3,5,7,11,13,17,19,23,29,31中选2,3为最低层结点，并从权数中删去，再添上他们的和数，即5,5,7,11,13,17,19,23,29,31；再从5,5,7,11,13,17,19,23,29,31中选5,5为倒数第2层结点，并从上述数列中删去，再添上他们的和数，即7,10,11,13,17,19,23,29,31；然后，从7,10,11,13,17,19,23,29,31中选7,10和11,13为倒数第3层结点，并从如图十六上述数列中删去，再添上他们的和数，即17,17,24,19,23,29,31；……（2）权值为：26+36+55+74+114+134+173+193+233+293+312=12+18+25+28+44+52+51+57+69+87+62=5056．解：最优二叉树如图十七如图十七它的权为：13+23+22+32+42=27五、证明题1．证明：用反证法．设G中的两个奇数度结点分别为u和v．假设u和v不连通，即它们之间无任何通路，则G至少有两个连通分支G1，G2，且u和v分别属于G1和G2，于是G1和G2各含有一个奇数度结点．这与定理7.1.2的推论矛盾．因而u和v一定是连通的．2．证明：设,GVE，,GVE．则E是由n阶无向完全图nK的边删去E所得到的．所以对于任意结点uV，u在G和G中的度数之和等于u在nK中的度数．由于n是大于等于2的奇数，从而nK的每个结点都是偶数度的（1(2)n度），于是若uV在G中是奇数度结点，则它在G中也是奇数度结点．故图G与它的补图G中的奇数度结点个数相等．3．证明：由定理7.1.2，任何图中度数为奇数的结点必是偶数，可知k是偶数．3271355111734160291023194217245331956512233475128又根据定理7.4.1的推论，图G是欧拉图的充分必要条件是图G不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图．故最少要加2k条边到图G才能使其成为欧拉图．