该文档为电子科大张晓军老师图论课后习题答案第一章、第二章能够在张晓军老师发的答案中找到第三章批改后未找到作业，故未整理
作业仅供参考，可能有错误
电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：120分钟 一．填空题(每题3分，共18分) 1．4个顶点的不同构的简单图共有__11___个； 2．设无向图G 中有12条边，已知G 中3度顶点有6个，其余顶点的度数均小于3。则G 中顶点数至少有__9___个； 3．设n 阶无向图是由k(k ?2)棵树构成的森林，则图G 的边数m= _n-k____; 4．下图G 是否是平面图？答__是___; 是否可1-因子分解？答__是_. 5．下图G 的点色数=)(G χ______, 边色数=')(G χ__5____。 图G 二．单项选择(每题3分，共21分) 1．下面给出的序列中，是某简单图的度序列的是( A ) (A) (11123); (B) (233445); (C) (23445); (D) (1333). 2．已知图G 如图所示，则它的同构图是（ D ） 3． 下列图中，是欧拉图的是（ D ） 4． 下列图中，不是哈密尔顿图的是（B ） 5． 下列图中，是可平面图的图的是（B ） A C D A B C D
6．下列图中，不是偶图的是（ B ） 7．下列图中，存在完美匹配的图是（B ） 三．作图(6分) 1．画出一个有欧拉闭迹和哈密尔顿圈的图； 2．画出一个有欧拉闭迹但没有哈密尔顿圈的图； 3．画出一个没有欧拉闭迹但有哈密尔顿圈的图； 解： 四．(10分)求下图的最小生成树，并求其最小生成树的权值之和。 解：由克鲁斯克尔算法的其一最小生成树如下图： 权和为：20. 五．(8分)求下图G 的色多项式P k (G). 解：用公式 (G P k -G 的色多项式： )3)(3)()(45-++=k k k G P k 。 六．(10分) 22，n 3个顶点的度数为3，…，n k 个顶点的度数为k ，而其余顶点的度数为1，求1度顶点的个数。 解：设该树有n 1个1度顶点，树的边数为m. 一方面：2m=n 1+2n 2+…+kn k 另一方面：m= n 1+n 2+…+n k -1 v v 1 3 图G
第一章 液压传动概述 液压传动系统由哪几部分组成各组成部分的作用是什么 解答：液压传动由以下四部分组成： （1）动力元件(液压泵)：它是把原动机输出的机械能转换成油液压力能的元件。作用:给液压系统提供压力油，是液压系统的心脏。 （2）执行元件：包括液压缸和液压马达等。 作用:把油液的压力能转换成机械能以驱动工作机构的元件。 （3）控制元件：包括压力、方向、流量控制阀。作用:是对液压系统中油液的压力、流量和流动方向进行控制和调节的元件。 （4）辅助元件：除上述三项以外的、液压系统中所需的其它装置。如油箱、滤油器、油管、管接头等。作用:保证液压系统有效工作，寿命长。 第二章 液压泵和液压马达 要提高齿轮泵的压力需解决哪些关键问题通常都采用哪些措施 解答：（1）困油现象： 采取措施：在两端盖板上开卸荷槽。（2）径向不平衡力：采取措施：缩小压油口直径；增大扫膛处的径向间隙； 过渡区连通；支撑上采用滚针轴承或滑动轴承。（3）齿轮泵的泄漏： 采取措施：采用断面间隙自动补偿装置。 齿轮泵的模数 mm m 4=，齿数9=z ，齿宽mm B 18=，在额定压力下，转速min 2000r n =时，泵的 实际输出流量min 30L Q =，求泵的容积效率。 解答：()() 2 2630 0.876.6~7 6.69418200010v t q q q zm bn η-= ===????? YB63型叶片泵的最高压力MPa P 3.6max =，叶片宽度mm B 24=，叶片厚度mm 25.2=δ，叶片数 12=Z ，叶片倾角?=13θ,定子曲线长径mm R 49=，短径mm r 43=，泵的容积效率9.0=v η，机械效率 90.0=m η，泵轴转速min 960r n =，试求：(1) 叶片泵的实际流量是多少(2)叶片泵的输出功率是多少 解答： （1） ()()()()() 22 223 322cos 20.0490.04320.0490.0430.024120.0249600.9cos131.0210v R r q R r bz Bn m s πηφπ-??=--???? ?-?? =--?????????? =? （2） 633 6.310 1.0210 6.4210N pq -==???=?出 斜盘式轴向柱塞泵的斜盘倾角?=20β，柱塞直径mm d 22=，柱塞分布圆直径mm D 68=，柱塞数7=z ，机械效率90.0=m η，容积效率97.0=v η，泵转速min 1450r n =，泵输出压力MPa p 28=，试计算：(1)平
习题一 作者---寒江独钓 1.证明：在n 阶连通图中 (1) 至少有n-1条边； (2) 如果边数大于n-1，则至少有一条闭迹； (3) 如果恰有n-1条边，则至少有一个奇度点。 证明: (1) 若G 中没有1度顶点，由握手定理： ()2()21v V G m d v n m n m n ∈= ≥?≥?>-∑ 若G 中有1度顶点u ，对G 的顶点数作数学归纳。 当n=2时，结论显然；设结论对n=k 时成立。 当n=k+1时，考虑G-u,它仍然为连通图，所以，边数≥k-1.于是G 的边数≥k. (2) 考虑G 中途径： 121:n n W v v v v -→→→→L 若W 是路，则长为n-1;但由于G 的边数大于n-1,因此，存在v i 与v j ,它们相异，但邻接。于是： 1i i j i v v v v +→→→→L 为G 中一闭途径，于是 也就存在闭迹。 (3) 若不然，G 中顶点度数至少为2，于是由握手定理： ()2()21v V G m d v n m n m n ∈= ≥?≥?>-∑ 这与G 中恰有n-1条边矛盾！ 2.(1)2n ?12n 2?12n ?1 (2)2n?2?1 (3) 2n?2 。 证明 :u 1的两个邻接点与v 1的两个邻接点状况不同。所以， 两图不同构。 4.证明下面两图同构。 u 1 v 1
证明:作映射f : v i ? u i (i=1,2….10) 容易证明，对?v i v j ∈E ((a)),有f (v i v j,),=,u i,u j,∈,E,((b)) (1≤ i ≤ 10, 1≤j ≤ 10 ) 由图的同构定义知，图(a)与(b)是同构的。 5.指出4个顶点的非同构的所有简单图。 分析：四个顶点的简单图最少边数为0，最多边数为6，所以 可按边数进行枚举。 (a) v 2 v 3 u 4 u (b)
习题一： ● 。 证明:作映射f : v i ? u i (i=1,2….10) 容易证明，对?v i v j ∈E ((a)),有f (v i v j,),=,u i,u j,∈,E,((b)) (1≤ i ≤ 10, 1≤j ≤ 10 ) 由图的同构定义知，图(a)与(b)是同构的。 ● 5.证明：四个顶点的非同构简单图有11个。 证明：设四个顶点中边的个数为m ，则有： m=0: m=1 ： m=2： m=3： m=4： (a) v 23 4 (b)
m=5： m=6： 因为四个顶点的简单图最多就是具有6条边，上面所列出的情形是在不同边的条件下的不同构的情形，则从上面穷举出的情况可以看出四个顶点的非同构简单图有11个。 ● 11.证明：序列（7,6,5,4,3,3,2）和（6,6,5,4,3,3,1） 不是图序列。 证明：由于7个顶点的简单图的最大度不会超过6，因此序列（7,6,5,4,3,3,2）不是图序列； （6,6,5,4,3,3,1）是图序列 1 1 12312(1,1,,1,,,)d d n d d d d d π++=---是图序列 （5,4,3,2,2,0）是图序列，然而（5,4,3,2,2,0）不是图序列，所以（6,6,5,4,3,3,1）不是图序列。 ● 12.证明：若 ，则包含圈。 证明：下面仅对连通图的下的条件下进行证明，不连通的情形可以通过分成若干 个连通的情形来证明。设 , 对于中的路 若与邻接，则构成一个闭路。若是一条路，由于，因 此，对于，存在与之邻接，则构成一个圈。 ● 17.证明：若G 不连通，则连通。 证明：对于任意的 ,若与属于G 的连通分支，显然与在中连通；
图论及其应用答案电子科 大 This model paper was revised by the Standardization Office on December 10, 2020
习题三： 证明：e是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意u ∈V 1及v ∈V 2, G 中的路（u，v）必含e . 证明：充分性: e是G的割边，故G ?e至少含有两个连通分支，设V 1是其中一个连通分支的顶点集，V 2是其余分支的顶点集，对12,u V v V ?∈?∈，因为G中的u ,v不连通， 而在G中u与v连通，所以e在每一条(u ,v )路上，G中的(u ,v )必含e。 必要性：取12,u V v V ∈∈，由假设G中所有(u ,v )路均含有边e，从而在G ?e中不存在从 u与到v的路，这表明G不连通，所以e 是割边。 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 （1）→（2）： G是块，任取G的一点u，一边e，在e边插入一点v，使得e成为两条边，由此得到新图G 1，显然G 1的是阶数大于3的块，由定理，G中的u,v 位于同一个圈上，于是G 1中u 与边e都位于同一个圈上。 （2）→（3）： G无环，且任意一点和任意一条边都位于同一个圈上，任取G的点u ，边e ，若u在e 上，则三个不同点位于同一个闭路，即位于同一条路，如u不在e上，由定理，e的两点在同一个闭路上，在e边插入一个点v ，由此得到新图G 1，显然G 1的是阶数大于3的块，则两条边的三个不同点在同一条路上。 （3）→（1）： G连通，若G不是块，则G中存在着割点u，划分为不同的子集块V 1, V 2, V 1, V 2无环，12,x v y v ∈∈，点u在每一条(x ,y )的路上，则与已知矛盾，G是块。 7.证明：若v 是简单图G 的一个割点，则v 不是补图G ?的割点。 证明：v是单图G的割点，则G ?v有两个连通分支。现任取x ,y ∈V (G ?v ), 如果x ,y 不在G ?v的同一分支中，令u是与x ,y处于不同分支的点，那么，x ,与y在G ?v的补图中连通。若x ,y在G ?v的同一分支中，则它们在G ?v的补图中邻接。所以，若v是G 的割点，则v不是补图的割点。 12.对图3——20给出的图G1和G2，求其连通度和边连通度，给出相应的最小点割和最小边割。 解：()12G κ= 最小点割 {6,8} 1()2G λ= 最小边割{（6,5），（8,5）}
图论及其应用答案电子科 大 Newly compiled on November 23, 2020
习题三： ● 证明：e 是连通图G 的割边当且仅当V(G)可划分为两 个子集V1和V2，使对任意u ∈V 1及v ∈V 2, G 中的路（u ，v ）必含e . 证明：充分性: e 是G 的割边，故G ?e 至少含有两个连通分支，设V 1是其中一个连通分支的顶点集，V 2是其余分支的顶点集，对12,u V v V ?∈?∈，因为G 中的u,v 不连通， 而在G 中u 与v 连通，所以e 在每一条(u,v)路上，G 中的(u,v)必含e 。 必要性：取12,u V v V ∈∈，由假设G 中所有(u,v)路均含有边e ，从而在G ?e 中不存在从 u 与到v 的路，这表明G 不连通，所以e 是割边。 ● 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 （1）→（2）： G 是块，任取G 的一点u ，一边e ，在e 边插入一点v ，使得e 成为两条边，由此得到新图G 1，显然G 1的是阶数大于3的块，由定理，G 中的u,v 位于同一个圈上，于是G 1中u 与边e 都位于同一个圈上。 （2）→（3）： G 无环，且任意一点和任意一条边都位于同一个圈上，任取G 的点u ，边e ，若u 在e 上，则三个不同点位于同一个闭路，即位于同一条路，如u 不在e 上，由定理，e 的两点在同一个闭路上，在e 边插入一个点v ，由此得到新图G 1，显然G 1的是阶数大于3的块，则两条边的三个不同点在同一条路上。
1 文件系统阶段的数据管理有些什么缺陷试举例说明。 文件系统有三个缺陷： （1）数据冗余性（redundancy)。由于文件之间缺乏联系，造成每个应用程序都有对应的文件，有可能同样的数据在多个文件中重复存储。 （2）数据不一致性（inconsistency)。这往往是由数据冗余造成的，在进行更新操作时，稍不谨慎，就可能使同样的数据在不同的文件中不一样。 （3）数据联系弱(poor data relationship)。这是由文件之间相互独立，缺乏联系造成的。 2 计算机系统安全性 （1）为计算机系统建立和采取的各种安全保护措施，以保护计算机系统中的硬件、软件及数据； （2）防止其因偶然或恶意的原因使系统遭到破坏，数据遭到更改或泄露等。 3. 自主存取控制缺点 （1）可能存在数据的“无意泄露” （2）原因：这种机制仅仅通过对数据的存取权限来进行安全控制，而数据本身并无安全性标记 （3）解决：对系统控制下的所有主客体实施强制存取控制策略 4. 数据字典的内容和作用是什么 数据项、数据结构 数据流数据存储和加工过程。 5. 一条完整性规则可以用一个五元组（D，O，A，C，P）来形式化地表示。 对于“学号不能为空”的这条完整性约束用五元组描述 D：代表约束作用的数据对象为SNO属性； O（operation）：当用户插入或修改数据时需要检查该完整性规则； A（assertion）：SNO不能为空； C（condition）：A可作用于所有记录的SNO属性； P（procdure）：拒绝执行用户请求。 6.数据库管理系统（DBMS）
：①即数据库管理系统（Database Management System)，是位于用户与操作系统之间的 一层数据管理软件，②为用户或应用程序提供访问DB的方法，包括DB的建立、查询、更 新及各种数据控制。 DBMS总是基于某种数据模型，可以分为层次型、网状型、关系型、面 向对象型DBMS。 7.关系模型：①用二维表格结构表示实体集，②外键表示实体间联系的数据模型称为关系模 型。 8.联接查询：①查询时先对表进行笛卡尔积操作，②然后再做等值联接、选择、投影等操作。 联接查询的效率比嵌套查询低。 9. 数据库设计：①数据库设计是指对于一个给定的应用环境，②提供一个确定最优数据模 型与处理模式的逻辑设计，以及一个确定数据库存储结构与存取方法的物理设计，建立起 既能反映现实世界信息和信息联系，满足用户数据要求和加工要求，又能被某个数据库管 理系统所接受，同时能实现系统目标，并有效存取数据的数据库。 10．事务的特征有哪些 事务概念 原子性一致性隔离性持续性 11．已知3个域： D1=商品集合=电脑，打印机 D3=生产厂=联想，惠普 求D1，D2，D3的卡尔积为： 12.数据库的恢复技术有哪些 数据转储和和登录日志文件是数据库恢复的
一、填空 20% （每小题2分） 1、 P ：你努力，Q ：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。 2、论域D={1，2}，指定谓词P 则公式),(x y yP x ??真值为 。 2、 设S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，则由B 31所表达的子集是 。 3、 设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则R= （列举法）。 R 的关系矩阵M R = 。 5、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= ； A 上既是对称的又是反对称的关系R= 。 6、设代数系统，其中A={a ，b ，c}, 则幺元是 ；是否有幂等 性 ；是否有对称性 。 7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。
9、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。 10、公式R Q P Q P P ?∧∨?∧∧?∨)(())(( 的根树表示为 。 二、选择 20% （每小题2分） 1、在下述公式中是重言式为（ ） A ．)()(Q P Q P ∨→∧； B ．))()(()(P Q Q P Q P →∧→??； C ．Q Q P ∧→?)(； D ．)(Q P P ∨→ 。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为（ ），成真赋值的个数为（ ）。 A ．0； B ．1； C ．2； D ．3 。 3、设}}2,1{},1{,{Φ=S ，则 S 2 有（ ）个元素。 A ．3； B ．6； C ．7； D ．8 。 4、 设} 3 ,2 ,1 {=S ，定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有（ ）个分块。 A ．4； B ．5； C ．6； D ．9 。 5、设} 3 ,2 ,1 {=S ，S 上关系R 的关系图为
电子科技大学研究生试卷 （考试时间： 至 ，共_____小时） 课程名称 图论及其应用 教师 学时 60 学分 教学方式 讲授 考核日期_2007__年___月____日 成绩 考核方式： （学生填写） 一．填空题(每题2分，共12分) 1．简单图G=(n,m)中所有不同的生成子图(包括G 和空图)的个数是___2m __个； 2．设无向图G=(n,m)中各顶点度数均为3，且2n=m+3,则n=_ 6__; m=_9__； 3．一棵树有i n 个度数为i 的结点，i=2,3,…,k,则它有2+(i ?2)∑n i i 个度数为1的结点； 4．下边赋权图中，最小生成树的权值之和为__20___; 5、某年级学生共选修9门课。期末考试时，必须提前将这9门课先考完，每天每人只在下午考一门课，则至少需要___9__天才能考完这9门课。 二．单项选择(每题2分，共10分) 1．下面给出的序列中，不是某简单图的度序列的是( D ) (A) (11123); (B) (22222); (C) (3333); (D) (1333). 2． 下列图中，是欧拉图的是（ D ） 学 号 姓 学 …………………… 密……………封…………… 线……………以……………内……………答…… ………题… …………无……………效…………………… v 5 v v 6A B
3．下列图中，不是哈密尔顿图的是（B） A B C D 4．下列图中，是可平面图的图的是（B） A B C D 5．下列图中，不是偶图的是（B） C A B D 三、 (8分)画出具有7个顶点的所有非同构的树 解：m=n?1=6 …… 四，用图论的方法证明：任何一个人群中至少有两个人认识的朋友数相同(10分) 证明：此题转换为证明任何一个没有孤立点的简单图至少有两个点的度数相同。 参考教材P5。 五．(10分) 设G为n 阶简单无向图，n>2且n为奇数，G与G的补图G中度数为奇数的顶点个数是否相等？证明你的结论 证明：根据补图定义d G(v i)+d G(v i)=n?1。相等。 由频序列相同证明有同样奇数的顶点个数。 参考教材P5。
第1章 图论预备知识 1.1 解：(1) p={φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} (2) p={,{a},{{b,c}},{a,{b,c}}} (3) p={,{}} (4) p={,{},{{}},{,{}}} (5)p={,{{a,b}},{{a,a,b}},{{a,b,a,b}},{{a,b},{a,a,b}},{{a,b},{a,b,a,b}},{{a,b},{a,a,b},{a,b,a,b}}} 1.2 解：(1) 真 (2) 假 (3)假 (4)假 1.3 解：(1) 不成立，A={1} B={1,2} C={2} (2) 不成立，A={1} B={1,2} C={1,3} 1.4 证明：设(x,y)∈(A ∩B)X(C ∩D) 说明x ∈A ∩B,y ∈C ∩D 由于 x ∈A,y ∈C 所以 (x,y) ∈A X C 由于x ∈B,y ∈D 所以 (x,y) ∈B X D 所以 (x,y) ∈（A X C ）∩（B X D ） 反过来，如果（x,y ）∈(A X C) ∩（B X D ） 由于 (x,y) ∈（A X C ）所以 x ∈A,y ∈C 由于 (x,y) ∈（B X D ）所以x ∈B,y ∈D 所以x ∈(A ∩B) y ∈(C ∩D) 所以 (x,y) ∈(A ∩B)X(C ∩D) 所以(A ∩B)X(C ∩D)= (A X C) ∩（B X D ） 1.5 解：Hasse 图 φφφφφφφφφ
极大元{9,24,10,7} 极小元{3,2,5,7} 最大元{24} 最小元{2} 1.6 解 (2)关系图为： (3)不存在最大元，最小元为{2} 1.7 解：(1)R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>} (2)略 (3)I A ?R 故R 是自反的。 <1,2>∈R <2,3>R 但是<1,3> ?R 故不满足传递性 1.8 解：(1) 不成立 A={1} B={2} C={3} D={4} 则左式={<1,3>，<1,4>,<2,3>,<2,4>} 右式={<1,3>,<2,4>} (2) 不成立 A={1,3} B={1} C={2,4} D={2} 则左式={<3,4>} 右式={<1,4>,<3,2>,<3,4>} (3) 不成立 A={1} B={2} C={3} D={4} 则左式={<1,3>,<1,4>,<2,3>,<2,4>} 右式={<1,3>,<2,4>} (4) 成立 证明：设
离散数学图论部分综合练习 一、单项选择题 1．设图G 的邻接矩阵为 ??? ???? ? ????? ???0101 010******* 11100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝
图三 7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( ) ． 图四 A ．（a ）是强连通的 B ．（b ）是强连通的 C ．（c ）是强连通的 D ．（d ）是强连通的 应该填写：D 8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路． A ．m 为奇数 B ．n 为偶数 C ．n 为奇数 D ．m 为偶数 9．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋2 10．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点 11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树． A ．1m n -+ B ．m n - C ．1m n ++ D ．1n m -+ 12．无向简单图G 是棵树，当且仅当( )． A ．G 连通且边数比结点数少1 B ．G 连通且结点数比边数少1 C ．G 的边数比结点数少1 D ．G 中没有回路． 二、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结 点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割 ο ο ο ο c a b f
图论第一次作业 By byh
|E(G)|,2|E(G)|2G υυ??≤ ??? ?? ??? 1.1 举出两个可以化成图论模型的实际问题 略 1.2 证明其中是单图 证明：（思路）根据单图无环无重边的特点，所以 最大的情形为任意两个顶点间有一条边相连，即极 端情况为。
?1.4 画出不同构的一切四顶单图 ?0条边：1条边： ?2条边：3条边： ?4条边：5条边：?6条边：
1.10G?H当且仅当存在可逆映射θ:V G→V H，使得uv∈E G?θuθv∈E H，其中G和H是单图。（证明充分性和必要性） ?必要性 ?若G?H，由定义可得，存在可逆映射θ:V G→V Hφ:E G→E(H)当且仅当ψ G e=uv时，ψHφe=θuθ(v)，所以uv∈E G? θuθv∈E H ?充分性 ?定义?:E G→E(H)，使得uv∈E G和θuθv∈E(H)一一对应，于是?可逆，且ψ e=uv的充要条件是ψHφe=θuθv，得G?H G
1.12求证(a)?K m ,n =mn，(b)G是完全二分图，则?G≤1 4 v G2 ?(a)对于K m ,n ，将顶集分为X和Y，使得X∪Y=V K m,n， X∩Y= ?，X=m，Y=n，对于X中的每一顶点，都和Y中所有顶点相连，所以?K m,n =mn ?(b)设G的顶划分为X,Y，X=m,Y=v?m，则?G≤ ??K m ,v-m =v?m m≤v2 4
?证明： ?(a)第一个序列考虑度数7,第二个序列考虑6,6,1 ?(b)将顶点v分成两部分v’和v’’ ?v’ = {v|v= v i, 1≤ i≤ k}, ?v’’ = {v|v= v i, k< i≤ n} ?以v’点为顶的原图的导出子图度数之和小于 ?然后考虑剩下的点贡献给这k个点的度数之和最大可能为
1 《邓稼先》课后习题参考答案 思考探究 一、通读全文，把握文意，回答下列问题。 1.初读课文时，哪些句段最让你感动？反复细读后，再想想这些内容是否最 能体现全文所要表达的思想情感。 2.找出文中表现奥本海默与邓稼先两人不同个性、品质的词语及细节，思考 作者为什么要进行对比，通过对比得出了怎样的结论。 参考答案：1.作者饱含真情，于字里行间高度赞扬了邓稼先深沉的爱国主义精神和将个人生命奉献给祖国国防事业的崇高情怀。这样的句段很多，如：“对这一转变做出了巨大贡献的,有一位长期以来鲜为人知的科学家——邓稼先。”“一次井下突然有一个信号测不到了，大家十分焦虑，人们劝他回去，他只说了一句话：‘我不能走。’”…… 2.文中的奥本海默与邓稼先两人的个性、品质截然不同。奥本海默是 锋芒毕露，读研究生时就常打断别人的报告，即便到了中年，成了名人，有时还会这样。而邓稼先“是一个最不要引人注目的人物”“忠厚平实”“真诚坦白，从不骄人”“没有小心眼儿，一生喜欢‘纯’字所代表的品格”“最有中国农民的朴实气质”；“他没有私心，人们绝对相信他”，“文革”中能说服两派群众组织，能说服工宣队、军宣队。作者把奥本海默与邓稼先进行对比，鲜明地突出邓稼先的精神品质，自然而然地得出结论：“邓稼先是中国几千年传统文化孕育出来的有最高奉献精神的儿子”“邓稼先是中国共产党的理想党员”。 二、有感情地朗读课文第五部分，想一想：这部分开头引用《吊古战场文》， 有什么作用？结尾处又引用儿时学到的“‘五四’时代的一首歌”，表达了怎样的情感？ 参考答案：课文第五部分开头引用《吊古战场文》，把读者引入中国历史的深处，让人从中国传统文化的角度去思考。结尾处引用自己儿时学到的“‘五四’时代的一首歌”，说明了邓稼先就是一个典型的中国男儿，他有着为祖国而献身的崇高的精神品质。
离散数学图论部分综合练习 一、单项选择题 1.设图G 的邻接矩阵为 ??? ???? ? ????? ???01010 1001000001 1100100110 则G 的边数为( ). A.6 B.5 C.4 D.3 2.已知图G 的邻接矩阵为 , 则G 有( ). A.5点,8边 B.6点,7边 C.6点,8边 D.5点,7边 3.设图G ＝
图三 7.设有向图(a )、(b )、(c )与(d )如图四所示,则下列结论成立的就是 ( ). 图四 A.(a )就是强连通的 B.(b )就是强连通的 C.(c )就是强连通的 D.(d )就是强连通的 应该填写:D 8.设完全图K n 有n 个结点(n ≥2),m 条边,当( )时,K n 中存在欧拉回路. A.m 为奇数 B.n 为偶数 C.n 为奇数 D.m 为偶数 9.设G 就是连通平面图,有v 个结点,e 条边,r 个面,则r = ( ). A.e －v ＋2 B.v ＋e －2 C.e －v －2 D.e ＋v ＋2 10.无向图G 存在欧拉通路,当且仅当( ). A.G 中所有结点的度数全为偶数 B.G 中至多有两个奇数度结点 C.G 连通且所有结点的度数全为偶数 D.G 连通且至多有两个奇数度结点 11.设G 就是有n 个结点,m 条边的连通图,必须删去G 的( )条边,才能确定G 的一棵生成树. A.1m n -+ B.m n - C.1m n ++ D.1n m -+ 12.无向简单图G 就是棵树,当且仅当( ). A.G 连通且边数比结点数少1 B.G 连通且结点数比边数少1 C.G 的边数比结点数少1 D.G 中没有回路. 二、填空题 1.已知图G 中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G 的边数就是 . 2.设给定图G (如图四所示),则图G 的点割 集就是 . 3.若图G=
二、应用题 题0：（1996年全国数学联赛） 有n （n ≥6）个人聚会，已知每个人至少认识其中的[n /2]个人，而对任意的[n /2]个人，或者其中有两个人相互认识，或者余下的n -[n /2]个人中有两个人相互认识。证明这n 个人中必有3个人互相认识。 注：[n /2]表示不超过n /2的最大整数。 证明 将n 个人用n 个顶点表示，如其中的两个人互相认识，就在相应的两个顶点之间连一条边，得图G 。由条件可知，G 是具有n 个顶点的简单图，并且有 （1）对每个顶点x ， )(x N G ≥[n /2]； （2）对V 的任一个子集S ，只要S ＝[n /2]，S 中有两个顶点相邻或V-S 中有 两个顶点相邻。 需要证明G 中有三个顶点两两相邻。 反证，若G 中不存在三个两两相邻的顶点。在G 中取两个相邻的顶点x 1和y 1,记N G (x 1)＝{y 1,y 2,……,y t }和N G (y 1)={x 1,x 2,……,x k },则N G (x 1)和N G (y 1)不相交，并且N G (x 1)（N G (y 1)）中没有相邻的顶点对。 情况一；n=2r ：此时[n /2]＝r ，由（1）和上述假设，t=k=r 且N G (y 1)＝V-N G (x 1)，但N G (x 1)中没有相邻的顶点对，由（2），N G (y 1)中有相邻的顶点对，矛盾。 情况二；n=2r+1: 此时[n /2]＝r ，由于N G (x 1)和N G (y 1)不相交，t ≥r,k ≥r,所以r+1≥t,r+1≥k 。若t=r+1,则k=r ，即N G (y 1)=r ，N G (x 1)＝V-N G (y 1)，由（2），N G (x 1)或N G (y 1)中有相邻的顶点对，矛盾。故k ≠r+1，同理t ≠r+1。所以t=r,k=r 。记w ∈V- N G (x 1) ∪N G (y 1),由（2），w 分别与N G (x 1)和N G (y 1)中一个顶点相邻，设wx i0∈E, wy j0∈E 。若x i0y j0∈E ，则w ，x i0, y j0两两相邻，矛盾。若x i0y j0?E ，则与x i0相邻的顶点只能是(N G (x 1)-{y j0})∪{w},与y j0相邻的顶点只能是(N G (y 1)-{x j0})∪{w}。但与w 相邻的点至少是3，故N G (x 1)∪N G (y 1)中存在一个不同于x i0和y j0顶点z 与w 相邻，不妨设z ∈N G (x 1)，则z ，w ，x i0两两相邻，矛盾。 题1：已知图的结点集V ={a ,b ,c ,d }以及图G 和图D 的边集合分别为： E (G )={(a ,a ), (a ,b ), (b ,c ), (a ,c )} E (D)={, ,
一、填空 20% 1、 P ：你努力，Q ：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。 2、论域D={1，2}，指定谓词P 则公式),(x y yP x ??真值为 。 2、 设S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，则由B 31所表达的子集是 。 3、 设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则R= （列举法）。 R 的关系矩阵M R = 。 5、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= ； A 上既是对称的又是反对称的关系R= 。 6、设代数系统，其中A={a ，b ，c}, 则幺元是 ；是否有幂等 性 ；是否有对称性 。 7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。
9、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。 10、公式R Q P Q P P ?∧∨?∧∧?∨)(())(( 的根树表示为 。 二、选择 20% （每小题2分） 1、在下述公式中是重言式为（ ） A ．)()(Q P Q P ∨→∧； B ．))()(()(P Q Q P Q P →∧→??； C ．Q Q P ∧→?)(； D ．)(Q P P ∨→ 。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为（ ），成真赋值的个数为（ ）。 A ．0； B ．1； C ．2； D ．3 。 3、设}}2,1{},1{,{Φ=S ，则 S 2 有（ ）个元素。 A ．3； B ．6； C ．7； D ．8 。 4、 设} 3 ,2 ,1 {=S ，定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有（ ）个分块。 A ．4； B ．5； C ．6； D ．9 。 5、设} 3 ,2 ,1 {=S ，S 上关系R 的关系图为
图论第三次作业 一、第六章 2.证明： 根据欧拉公式的推论，有m ≦l*(n-2)/(l-2), (1)若deg(f)≧4,则m ≦4*(n-2)/2=2n-4; (2)若deg(f)≧5,则m ≦5*(n-2)/3,即：3m ≦5n-10; (3)若deg(f)≧6,则m ≦6*(n-2)/4,即：2m ≦3n-6. 3.证明： ∵G 是简单连通图，∴根据欧拉公式推论，m ≦3n-6; 又，根据欧拉公式：n-m+φ=2,∴φ=2-n+m ≦2-n+3n-6=2n-4. 4.证明： (1)∵G 是极大平面图，∴每个面的次数为3， 由次数公式：2m==3φ, 由欧拉公式：φ=2-n+m, ∴m=2-n+m,即：m=3n-6. (2)又∵m=n+φ-2,∴φ=2n-4. (3)对于3n >的极大可平面图的的每个顶点v ，有()3d v ≥，即对任一一点或者
子图，至少有三个邻点与之相连，要使这个点或子图与图G 不连通，必须把与之相连的点去掉，所以至少需要去掉三个点才能使()(H)w G w G <-，由点连通度的定义知()3G κ≥。 5.证明： 假设图G 不是极大可平面图，那么G 不然至少还有两点之间可以添加一条边e ，使G+e 仍为可平面图，由于图G 满足36m n =-，那么对图G+e 有36m n '=-，而平面图的必要条件为36m n '≤-，两者矛盾，所以图G 是极大可平面图。 6.证明： (1)由()4G δ=知5n ≥当n=5时，图G 为5K ，而5K 为不可平面图，所以6n ≥，（由()4G δ=和握手定理有24m n ≥，再由极大可平面图的性质36m n =-，即可得6n ≥）对于可平面图有()5G δ≤，而6n ≥，所以至少有6个点的度数不超过5. (2)由()5G δ=和握手定理有25m n ≥，再由极大可平面图的性质36m n =-，即可得12n ≥，对于可平面图有()5G δ≤，而12n ≥，所以至少有12个点的度数不超过5. 二、第七章 2.证明： 设n=2k+1,∵G 是Δ正则单图，且Δ>0, ∴m(G)==>k Δ,由定理5可知χˊ(G)=Δ(G)+1.
第七章 一、填空 1．柯尔伯格经长期研究，发现儿童和成人道德判断的发展经历三个水平：A〃前习俗-水平，B、习俗水平，c。后习俗水平，大多数少年的道德评价处于习俗--水平。 2．克拉斯沃尔等人提出的价值内化经历了五个阶段。它们是A〃----注意-，B〃—反应-，C〃----评价--，D〃---组织--，E〃--价值性格化--。 3．心理学认为态度和品德都包括：A。----认知-- ，B．----情感-，C。--行为三个成分。 4．态度与品德的区别在于；A．--态度的范围大于品德—，B〃价值内化程度不同--。 5．社会心理学家凯尔曼提出的态度改变需要经历的三个阶段为：A。--顺从--，B．------认同----，C。---内化---- 。 6．态度的功能有：A。----价值表现--，B。-------调节--和C。---过滤----。7．社会学习理论是由----班杜拉---提出来的，适合解释------社会--行为。8．费斯廷格提出的四种认知失调情境是：A．----逻辑不一致---，B。-----与社会风气不一致--，C。------与一贯行为不一致---，D。--与过去经验不一致---。 二、概念与原理的解释和运用 1．某些教科书把态度和品德分别安排在两章教授。这两个概念可能的关系 是：A c．态度是 一种比品德更稳定的心理品质；D．品德是态度形成与改变的条件。 2．让寝室里的同学共同讨论制订出寝室守则，这种方法是：A.说服 用群体规定;C.价值观辨析;D.角色扮演。 3．在一个好的集体里，差生的不良言行很少有市场；在一个不好的集体里， 好学生也会附和不良言行。这一现象的适当解释是A． 众；c老师的威信；D．认知失调。 4．甲孩子因偷吃东西，打破一只碗；乙孩子因帮妈妈洗碗，打破15只碗。 童；B．小学儿童；C．中学生；D．无法确定。 5．假如家长想用看电视作为强化物奖励儿童认真按时完成家庭作业的行为，最适合的安排是：A.让儿童看完电视后立即督促他们完成作业；B．规定每周看 电视的适当时间；c. 看电视。 6．国外有座收费的桥。当局规定，凡乘一人的车收税，乘两人以上的车可免收税，于是人们纷纷多人乘一辆车过桥。根据强化原理，这种行为最适当的解
图论复习题答案 一、 判断题，对打√，错打 1．无向完全图是正则图。( √ ) 2．零图是平凡图。( ) 3．连通图的补图是连通图. ( ) 4．非连通图的补图是非连通图。( ) 5．若连通无向简单图G中无圈，则每条边都是割边。( √ ) 6．若无向简单图G是（n，m）图，并且m=n-1，则G是树。( ) 7．任何树都至少有2片树叶。( ) 8．任何无向图G都至少有一个生成树。( ) 9．非平凡树是二分图。( √ ) 10．所有树叶的级均相同的二元树是完全二元树。( ) 11．任何一个位置二元树的树叶都对应唯一一个前缀码。( √ ) 12．3,3 K是欧拉图也是哈密顿图。( ) 13．二分图的对偶图是欧拉图。( ) 14．平面图的对偶图是连通图。( √ ) 15．设G*是平面图G的对偶图，则G*的面数等于G的顶点数。( )二、填空题 1．无向完全图K6有 15 条边。 2．有三个顶点的所有互不同构的简单无向图有 4 个。 3．设树T中有2个3度顶点和3个4度顶点，其余的顶点都是树叶，则T中有 10 片树叶。 4．若连通无向图G是（n，m）图，T是G的生成树，则基本割集 有 n-1 个，基本圈有 m-n+1 个。 5．设连通无向图G有k个奇顶点，要使G变成欧拉图，在G中至少要 加k / 2 条边。 6．连通无向图G是（n，m）图，若G是平面图，则G有m-n+2 个面。 三、解答题 1．有向图D如图1所示，利用D的邻接矩阵及其幂运算 求解下列问题： （1）D中长度等于3的通路和回路各有多少条。（2）求D的可达性矩阵。 （3）求D的强分图。 a b e 图1
解： （1） M=????????????????00010 1000000001 010******* M 2 =?? ?? ??? ? ??? ?????010******* 00010 1000001000 M 3=????????????????1000001000010000001010000 M 4=??????? ?????????0001001000100000100000010 由M 3可知，D 中长度等于3的通路有5条，长度等于3的回路有3条。 （2） I+M+M 2+M 3+M 4 =????????????? ???100000100000100 0001000001 +??????????? ?? ???000101000000001 010******* +??? ???? ? ??? ?? ???010000001000010 1000001000 + ????????????????1000001000010000001010000 +??? ?? ???????????0001001000100000100000010 = ??? ???? ? ????????21020 13010111110202011021 D 的可达性矩阵为 R=B （I+M+M 2+M 3+M 4 ）=??? ???? ? ????? ???110101********* 1101011011 （3）R T =????????????????11111 1111100100 1111100101 R×R T =??? ???? ? ??? ?????11010 11010 001001101000001 由矩阵R×R T 可知，该有向图的强分图有：{a}，{ b ，d ，e}， { c} a b e 图1