离散数学形成性考核作业（三）
离散数学学图论部部分综合合练习辅辅导本次活动动是本学学期的第第二次活动动(20008.11.18)，主要要是针对对第二单元元图论的重重点学习习内容进进行辅导导，方式式是通过过讲解一一些典型型的综合合练习题题目，帮帮助大家家进一步步理解和和掌握图图论的基基本概念念和方法法。图论作为为离散数数学的一一部分，主主要介绍绍图论的的基本概概念、理理论与方方法。教教学内容容主要有有图的基基本概念念与结论论、图的连连通性与与连通度度、图的的矩阵表表示、最最短路问问题、欧欧拉图与与汉密尔尔顿图、平平面图、对对偶图与与着色、树树与生成成树、根根树及其其应用等等。本次综合合练习主主要是复复习这一一部分的的主要概概念与计计算方法法，与集集合论一一样，也也安排了了五种类类型，有有单项选选择题、填空题题，判断说说明题、计算题题、证明明题。这样的的安排也也是为了了让同学学们熟悉悉期末考考试的题题型，能能够较好好地完成成这一部部分主要要内容的的学习。下面分分别讲解解。一、单项项选择题题1设图图G的邻接接矩阵为为则G的边边数为( )A5BB6C3D4正确答案案：D上学期的的作业中中，有的的同学选选择答案案B。主主要是对对邻接矩矩阵的概概念理解解不到位位。我们们复习定定义：定义3.3.11设G=<V，E>是一个个简单图图，其中中V=v1，v2，vn，则 n阶方阵阵A（G）=（aij）称称为G的邻接矩矩阵其其中各元元素而当给定定的简单单图是无无向图时时，邻接接矩阵为为对称的的即当当结点vvi与vj相邻时时，结点点vj与vi也相邻邻，所以以连接结结点vi与vj的一条条边在邻邻接矩阵阵的第i行第j列处和和第j行第i列处各各有一个个1，题题中给出出的邻接接矩阵中中共有88个1，故故有8¸22=4条条边。2设图图G<V, E>，则则下列结结论成立立的是 ( )Adeeg(VV)=22½E½Bdegg(V)=½E½CD正确答案案：C该题主要要是检查查大家对对握手定定理掌握握的情况况。复习习握手定定理：定理3.1.11 设G是一个个图，其其结点集集合为VV，边集集合为EE，则ooooocabedof3图GG如右图所示示，以下下说法正正确的是是 ( )A(a, d)是割边边B(a, d)是边割割集C(d, e)是是边割集集D(a, d) ,(aa, cc)是是边割集集正确答案案：C上学期许许多同学学选择答答案A。主主要是对对割边、边边割集的概概念理解解不到位位。复习习割边、边边割集的的定义：定义3.2.99设无向向图G=<V,E>为连通通图，若若有边集集E1ÌE，使图图G删除了了E1的所有有边后，所所得的子子图是不不连通图图，而删删除了EE1的任何何真子集集后，所所得的子子图是连连通图，则则称E1是G的一个个边割集集若某某个边构构成一个个边割集集，则称称该边为为割边（或或桥）如果答案案A正确确，即删删除边(a, d)后后，得到到的图是是不连通通图，但但事实上上它还是是连通的的。因此此答案A是是错误的的。4设GG是连通通平面图图，有vv个结点点，e条边，rr个面，则则r= ( )Aev2 BBve2 Cev2 DDev2正确答案案：A 该题主主要是检检查大家家对平面面图的欧欧拉定理理的理解解情况。定理4.3.22（欧拉拉定理）设连通平面图G的结点数为v，边数为e，面数为r，则下列欧拉公式成立v-e+r =25无向向图G存在欧欧拉通路路，当且且仅当( )AG中中所有结结点的度度数全为为偶数 BG中中至多有有两个奇奇数度结结点CG连连通且所所有结点点的度数数全为偶偶数DG连连通且至至多有两两个奇数数度结点点正确答案案：D上学期许许多同学学选择答答案C。主主要是将将题中的的“欧拉通通路”误认为为“欧拉回路”了。其实实应该运用定理4.1.1进行选择择，才是正正确的。复习定义和定理：定义4.1.11 给定定无孤立立结点图图G，若存存在一条条路经过过图G的每条条边一次次且仅一一次，则则该路称称为欧拉拉路；若存在一一条回路路经过图图G的每条条边一次次且仅一一次，在在该回路路称为欧欧拉回路路；定理4.1.11无向图图G具有一一条欧拉拉路，当当且仅当当G是连通通的，且且有零个个或2个奇数数度数的的结点 推论一一个无向向图具有有一条欧欧拉回路路，当且且仅当该该图是连连通的，并并且它的的结点度度数都是是偶数 所以，正正确答案案应该是是D6设GG是有n个结点点，m条边的的连通图图，必须须删去GG的( )条边边，才能能确定GG的一棵棵生成树树ABCD正确答案案：A上学期许许多同学学选择答答案D。主要要是把定理5.1.1给出出的图TT为树的的等价定义义之一是是图T连通且且e=vv-1中的公公式用错错了大大家只要要把m代入公公式e=v-1中的e，把n代入公公式e=v-1中的v，可以以知道答答案A是是正确。定理5.1.11 给定定图T，则以以下关于于图T为树的的定义等等价（1）无无回路的的连通图图（2）无无回路且且e=vv-1，其中中e是边数数，v是顶点点数（3）连连通且ee=v-1（4）无无回路，但但增加任任一新边边，得到到且仅得得到一个个回路（5）连连通，但但删去任任一边后后图便不不连通（v2）（6）每每一对顶顶点之间间有且仅仅有一条条路（v2）定理5.1.11的六个个等价定定义，大大家应该该熟记的的最主要要的是：无向简简单图GG是棵树树，当且且仅当GG连通且且边数比比结点数数少1二、填空空题1已知知图G中有11个1度度结点，22个2度度结点，33个3度度结点，44个4度度结点，则则G的边数数是应该填写写：155主要检查查大家对对握手定定理掌握握的情况况。定理3.1.11（握手手定理） 设G是一个个图，其其结点集集合为VV，边集集合为EE，则ooooocabedof因为图GG中有11个1度度结点，22个2度度结点，33个3度度结点，44个4度度结点，即，所以边数有。问：若无无向树TT中有8个结点点，4度度，3度度，2度度的分支点各一一个，那那么T的树叶叶数为多多少？2设给给定图GG(如右图所示示)，则则图G的点割集是应该填写写：f，c，e上学期许许多同学学填错答答案主要要对点割割集的概概念理解解不正确。定义3.2.7设无向向图G=<V,E>为连通通图，若若有点集集V1ÌV，使图图G删除了了V1的所有有结点后后，所得得的子图图是不连连通图，而而删除了了V1的任何何真子集集后，所所得的子子图是连连通图，则则称V1是G的一个个点割集集若某某个结点点构成一一个点割割集，则则称该结结点为割割点上学期许许多同学学填写的的f，c，主要要是没有完完全理解解定义3.2.7，因为为f是f，c的真子子集，而而删除f后，图图是不连连通的。3设无无向图GG<V,E>是汉密密尔顿图图，则VV的任意意非空子子集V1，都有有£½V1½应该填写写：W(G-V1) 因为具具有汉密密尔顿回回路的图图称为汉汉密尔顿顿图而由定理4.2.11若图G=<V,E>中具具有一条条汉密尔尔顿回路路，则对对于结点点集V的每个个非空子子集S均有W(G-S)£ |S|成立，其其中W(G-SS)是（G-S）中中连通分分支数因此应该该填写：W(G-V1)4设有有向图DD为欧拉拉图，则则图D中每个个结点的的入度应该填写写：等于于出度如果大家家记住“具有欧欧拉回路路的图称称为欧拉拉图”和定理4.1.2：一个有有向图具具有单向向欧拉回回路，当当且仅当当它是连连通的，且且每个结结点的入入度等于于出度大家一一定能填填写出正正确答案案的。5设完完全图KK有n个结点点(n³2)，mm条边，当时，K中存在在欧拉回回路应该填写写：n为奇数数上学期许许多同学学填错答答案主要要对完全全图的概概念理解解不正确确。定义3.1.66 简简单图GG=<V，E>中，若若每一对对结点间间都有边边相连，则则称该图图为完全全图有有n个结点点的无向向完全图图记为KKn由定义可可知，完完全图KKn中的任任一结点点v到其它它结点都都有一条条边，共共有n-1条边边，即每每个结点点的度数数是n-1，当当n为奇数数时，nn-1为偶偶数。由定理44.1.1的推论可知，应该该填写：n为奇数数。6给定定一个序序列集合合1，01，10，11，0001，0000，若去去掉其中中的元素素，则该该序列集集合构成成前缀码码应该填写写：1因为在二二进制中中1是110和111的前前缀。而而前缀码码的定义义是（定定义5.2.100）：给定定一个序序列集合合，若没没有一个个序列是是另一个个序列的的前缀，该该序列集集合称为为前缀码码填写该题题答案时时大家一一定要对对前缀码码的定义义理解非非常清楚楚。问：若把把序列集集合中的的1换成0，应该该去掉哪哪个元素素？三、判断断说明题题1给定定两个图图G1，G2（如下下图所示示）：（1）试试判断它它们是否否为欧拉拉图、汉汉密尔顿顿图？并并说明理理由v1（2）若若是欧拉拉图，请写出出一条欧欧拉回路路v6v5v4v3v2分析：先先复习欧拉拉图的判判别定理理和汉密密尔顿图图的定义义：定理4.1.11的推论：一个无无向图具具有一条条欧拉回回路，当当且仅当当该图是是连通的的，并且且它的结结点度数数都是偶偶数定义4.2.11：若存在在一条回回路经过过图G的每个个结点一一次且仅仅一次，则则该回路路称为汉汉密尔顿顿回路；具有汉汉密尔顿顿回路的的图称为为汉密尔尔顿图 解：（11）图G1是欧拉图图 因为图图G1中每个个结点的的度数都都是偶数数图G2是是汉密尔尔顿图因为图GG2存在一一条汉密密尔顿回回路（不不惟一）：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(vv1, v2)v2 (v2, v3)v3 (v3, v4) v4 (v4, v5)v5 (v5, v2)v2 (v2, v6)v6 (v6, v4)v4 (v4, v1)v1ooooov5v1v2v4v6ov3（上学期期的学生生在书写写欧拉回路路时不规规范，大大家要按按照正确确的方法法写法。）2判别别图G(如右图所示示)是不不是平面面图，并说明理理由分析：平平面图的的定义是是定义4.3.11设G=<V，E>是一个个无向图图，如果能把把G的所有有结点与与边画在在平面上上，并且且使得任何何两条边边除端点点外没有有其他的的交点，则则ooooov5v1v2v4v6ov3称G是一一个平面面图（也也称可平平面图）显然平面面
