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

离散数学图论部分综合练习ooooocabedof图1如果设置图g=，则以下结论成立():A.deg (v)=2e b. deg (v)=eC.D.图g正确，如图1所示()。A.(a，d)B.(a，d)图2C.(d，e)D.(a，d)，(a，c)如图ii所示，以下陈述是正确的():A.e是切削点b。 a，e是点切削集C.b，e是点切削集D. D.d是点切削集如图3所示，以下陈述是正确的():A.(a，e) B. (a，e)是边切口集C.(a，e)，(b，c)边切削集D. (d，e)是边切削集图3如图4所示，如果有方向图(a)、(b)、(c)和(d)，则以下结论为()。透视A.(a)强连接的B. (b)是强连接的C.(c)是强连接的D. (d)是强连接的6.将全图k设置为n节点(n2)，m边，k有Euler循环。对于A.m，为奇数b.n，为偶数c.n，为奇数d.m，为偶数7.v节点、e边、r面、r=()。A.e-v 2b.v e-2c.e-v-2d.e v 28.有指向无向图g的Euler路径，并且()。A.g的所有节点度都是偶数B.g最多包含两个奇节点C.g连接在一起，所有节点的角度都是偶数D.g是连接的，最多有两个奇节点9.将g设置为具有n个节点、m条边的连接图表。要确定g的生成树之一，必须删除g的()边。A.b.c.d10.无向简单图g是树()。连接A.g，边数小于节点数的1 B.G，节点数小于边数的1C.g的边数与节点数相比，1 D.G没有循环。二、填空1.已知图g具有一个1度节点、两个2度节点、三个3度节点和四个4度节点时，g的边数为。ooooocabedof透视设定给定图形g时(如图4所示)，切断图形g的点套装是。如果图G=中有哈密顿回路，对于节点集v中的每个非空集s，s将从g中删除中所有节点的连接分支为w时，s的节点与数字|S| w满意度的关系是。4.仅当全向图g具有Euler电路并且连接了g时还有。5.方向图形d为Euler图形时，图d中每个节点的输入。6.整个图形k有n个节点(N2)，m个边，k有Euler循环。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=是具有6个节点、8条边的连接图，则从g中删除边时，您将看到图g中的生成树之一。13.如果给定系列集000，001，01，10，0并删除其元素，则系列集将构成前缀代码。三、判断说明问题图6所示的图g具有欧拉电路。V1V2V3V5V4dbacefghn图6如图7所示，提供了两个图G1、G2。(1)判断他们是欧拉多，汉密尔顿图吗？说明原因。(2)对于欧拉图，请创建欧拉回路。V1V2V3V4V5V6oooooV5V1V2V4V6oV3图8图7判别图g是否为平面图，如图8所示。说明原因。将g设置为具有6个节点14条边的连接。一般图表，g是平面图。四、计算问题1.设定图形G=。其中V=a1，a2，a3，a4，a5，E=，(1)测试g的图形表达。(2)判断图g是强连接图、单侧连接图还是弱连接图？2.图G=，V= v1，v2，v3，v4，v5，E= (v1，v2)，(v1，v3)，(v2，v3)，(1)绘制g的图形表达。(2)查找每个节点的度。(3)绘制g的补充图面。3.G=，V= v1，v2，v3，v4，v5，E= (v1，v3)，(v2，v3)，(v2，v4)，(1)给出了g的图形表示。(2)查找每个节点的度。(3)绘制补充图形的图形。4.图G=，其中V= a，b，c，d，e，e=(a，b)，(a，c)，(a，e)，(b，d(1)绘制g的图形。(2)求g权重最小的生成树及其权重。5.2，3，5，7，11，13，17，19，23，29，31，有一套考试的权利(1)绘制相应的最佳二叉树。(2)计算他们的权重。绘制权能为1、2、2、3、4的最佳二叉树来计算其权利。五、证明问题1.如果无向图g仅包含两个奇数度节点，则这两个节点必须连接在一起。2.将g设置为n阶无向简单图，n是大于2的奇数。证明图g等于相应补充图中的奇数度顶点数。3.连接也证明了g具有k奇数节点，并且在图g中至少添加了一条边才能成为欧拉图。参考回答一、单一选择题1.C 2 .C 3 .A 4 .D 5 .D 6 .c7.a 8 .d 9 .a 10 .a二、填空1.15 2 .f，c，e 3.w | s |4.所有节点的度数都是偶数5。和出图一样6.n为奇数7.v-e r=2 8.39.e=v-1 10.4 11.512.3 13.0三、判断说明问题1.解决方案：没错。这是因为图g连接在一起，每个顶点的角度都是偶数。解决方案：(1)图G1是Euler图。因为图G1中的每个节点角度都是偶数。图G2是汉密尔顿图。图G2中有汉密尔顿循环(不是唯一的):A (a，b) b (b，e) e (e，f) f (f，g) g (g，d) d (d，c) c (c，a)问题：请想想为什么图G1不是汉密尔顿地图，图G2不是欧拉地图。(2)图G1中的Euler循环如下： (非唯一):oooooV5V1V2V4V6oV3投球V1 (v1，v2) v2 (v2，v3) v3 (v3，v4) v4 (v4，V5) V5(V5，v2) v2 (v2，V6) V6 (V6，v4) v4 (v4，v1) v1解法：图g是楼板平面图。这是因为您只需拉动节点v2和V6的连接(v2、V6)移出节点v1，连接节点v3和V6(v3，V6)向节点v4，V5外拖动将展平图面，如图9所示。解决：错误。“如果g是具有v节点e的边的连接简单平面，并且v3，则e3v-6”未满足四、计算问题1.oooooA1A2A3A4A5解决方案：(1)图g是直接图。(2)度g是单侧连接图，也是弱连接图。2.v1V2V3V4V5ooooo解决方案：(1)图g图10(3)deg(v1)=2Deg(v2)=3V1V2V3V4V5ooooo度(v3)=4Deg(v4)=3度(V5)=2(4)图11图11解决方案：(1)图12中的g图形图12(2)v1、v2、v3、v4和V5节点的度数为1，2，4，3，2(3)图13:图13解决方案：(1)图14中的g图形表示：图14(2)粗线表示最小的生成树，如图15所示图15最小生成树的权重为1 1 2 3=7:解决方案：(1)最佳二叉树，如图16所示：ooooooooo3271355111734oo1602910ooo231942oo17o24o5331ooo9565方法(仅限赫夫曼):从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中在图16中，反向选择7，10，11，13的三层节点从上面的数列中删除，加上他们的和，也就是说17、17、24、19、23、29、31；.(2)权重如下：26 36 55 74 114 134 173 193 233 293 312=12 18 25 28 44 52 51 57 69 87 62=5056.ooooooooo1223347512解决方案：最佳二叉树，如图17所示图17该权利为13 23 22 32 42=27五、证明问题1.证明：反证法。将g的两个奇数度节点设置为u和v。假设u和v没有连接。也就是说，如果没有彼此的路径，g至少有两个连接的分支G1、G2，u和v分别属于G1和G2，因此G1和G2各有一个奇数度节点。这与定理7.1.2的推论相矛盾。因此，u和v必须连接在一起。2.证明：设置。e从n阶无向完全图的边上去除。因此，对于随机节点，g和中u的度数之和等于u的度数。因为n是奇数(例如2)，所以每个节点都是偶数(以度为单位)，如果g是奇