图论复习题答案
一、判断题，对打，错打
1．无向完全图是正则图。
()
2．零图是平凡图。()
3．连通图的补图是连通图.()
4．非连通图的补图是非连通图。()
5．若连通无向简单图G中无圈，则每条边都是割边。()
6．若无向简单图G是（n，m）图，并且m=n-1，则G是树。()
7．任何树都至少有2片树叶。()
8．任何无向图G都至少有一个生成树。()
9．非平凡树是二分图。()
10．所有树叶的级均相同的二元树是完全二元树。()
11．任何一个位置二元树的树叶都对应唯一一个前缀码。()
12．
K是欧拉图也是哈密顿图。()
3,3
13．二分图的对偶图是欧拉图。()
14．平面图的对偶图是连通图。()
页脚内容1
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的强分图。
解：（1）
a
b
c d
e
图1
页脚内容2
页脚内容3
M=????????????????000101000000001
010*******M 2=??
?
?
???????
?????010*******
000101000001000
M 3=????????????????10000
01000010000001010000M 4=???
????
?
???
?????00010
01000
100000100000010
由M 3可知，D 中长度等于3的通路有5条，长度等于3的回路有3条。
（2）
I+M+M 2+M 3+M 4=?????????????
???100000100000100
0001000001
+???????????
??
???000101000000001
010*******
+???????????
??
???010000001000010
1000001000
+???
????
?
???
??
???100000100001000
0001010000
+
????????????????00010
01000100000100000010
=???
????
????
??
???21020
1301011111
020*******
D 的可达性矩阵为
R=B （I+M+M 2+M 3+M 4）=???
????
?
?????
???110101*********
1101011011
b
c d e 图1
页脚内容4
（3）R T =????????????????1111111111001001111100101R×R T =???
????
?
???
?????1101011010
001001101000001
由矩阵R×R T 可知，该有向图的强分图有：{a}，{b ，d ，e}，{c}
2． 画出有1个4次顶点，2个2次顶点，4个1次顶点的所有非
同构的树。
3． 用Kruskal 算法求图2所示带权图的最小生成树，并计算它的权。
C （T ）=25 4．
试画出带权为1,2,3,4,5,7,的最优二元树,并计算它的权。
m （T ）=（1+2）4+33+（7+4+5）2=53
5．
出席某次国际学术报告会的六个成员
654321,,,,,P P P P P P 被分在一组。他们的情况是：
1P 会讲汉语、法语和日语； 2P 会讲德语、日语和俄语；
3P 会讲英语和法语；
4P 会讲汉语和西班牙语；
5P 会讲英语和德语；
12943685710
1236
22754139
页脚内容5
6P 会讲俄语和西班牙语。
怎样把他们安排在一张圆桌旁坐下，使得每个人都能和他两旁的人交谈？
解构造无向图>= },,,,,{654321P P P P P P V =，}|),{(会讲同一种语言与j i j i P P P P E =， 则得无向图如图所示。 由该图得一条哈密顿回路：1352641PP P P P P P ，即为满足要求的安排。 四、证明题 1． 设T 是完全二元树，T 中有m 条弧和t 片树叶，证明： m=2(t 1)。 证明：设完全二元树T 有n 个顶点。因为它有t 片树叶，所以除树叶以外的顶点有t n -个。由于完全二元树中，根和分支点的引出次数为2，每片树叶的引出次数为0，故所有顶点的引出次数之和为)(2t n -，它等于边数m 。又因为1-=n m ，故有1)(2-=-n t n ，解得12-=t n 。因此 )1(2221-=-=-=t t n m 。 电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：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 10-4统计案例 基 础 巩 固 一、选择题 1．对于事件A 和事件B ，通过计算得到χ2的观测值χ2≈4.514，下列说法正确的是( ) A ．有99%的把握说事件A 和事件 B 有关 B ．有95%的把握说事件A 和事件B 有关 C ．有99%的把握说事件A 和事件B 无关 D ．有95%的把握说事件A 和事件B 无关 [答案] B [解析] 由独立性检验知有95%的把握说事件A 与B 有关． 2．r 是相关系数，则下列叙述中正确的个数为( ) ①r ∈[－1，－0.75]时，两变量负相关很强； ②r ∈[0.75,1]时，两变量正相关很强； ③r ∈(－0.75，－0.3]或[0.3,0.75)时，两变量相关性一般； ④r ＝0.1时，两变量相关性很弱． A ．1 B ．2 C ．3 D ．4 [答案] D 3．某化工厂为预测某产品的回收率y ，需要研究它和原料有效成分含量x 之间的相关关系，现取了8对观察值，计算得∑i ＝1 8 x i ＝52，∑i ＝1 8 y i ＝228，∑ i ＝18 x 2 i ＝478，∑ i ＝1 n x i y i ＝1849，则 y 与x 的回归方程是( ) A.y ^ ＝11.47＋2.62x B.y ^ ＝－11.47＋2.62x C.y ^ ＝2.62＋11.47x D.y ^ ＝11.47－2.62x [答案] A 4．(2011·湖南理，4)通过随机询问110名性别不同的大学生是否爱好某项运动，得到如下的列联表： 由K 2＝(a ＋b )(c ＋d )(a ＋c )(b ＋d ) 算得，K 2＝ 110×(40×30－20×20)2 60×50×60×50≈7.8. 附表： A ．在犯错误的概率不超过0.1%的前提下，认为“爱好该项运动与性别有关” B ．在犯错误的概率不超过0.1%的前提下，认为“爱好该项运动与性别无关” C ．有99%以上的把握认为“爱好该项运动与性别有关” D ．有99%以上的把握认为“爱好该项运动与性别无关” [答案] C [解析] 本小题考查内容为独立性检验． 本试卷满分90分 （06级计算机、信息安全专业、实验学院） 一、判断对错（本题满分10分，每小题各1分） （ 正确画“√”，错误画“×”） 1．对每个集合A ，A A 2}{∈。 （×） 2．对集合Q P ,，若?==Q P Q Q P ,，则P =?。 （√） 3．设,,:X A Y X f ?→若)()(A f x f ∈，则A x ∈。 （×） 4．设,,:Y B Y X f ?→则有B B f f ?-))((1。 （×） 5．若R 是集合X 上的等价关系，则2R 也是集合X 上的等价关系。 （√） 6．若:f X Y →且f 是满射，则只要X 是可数的，那么Y 至多可数的。（√） 7．设G 是有10个顶点的无向图，对于G 中任意两个不邻接的顶点u 和v, 均有9deg deg ≥+v u ，则G 是哈密顿图。 （×） 8．设)(ij a A =是 p 个顶点的无向图G 的邻接矩阵，则对于G 的顶点i v , 有∑==p j ij i a v 1deg 成立。 （√） 9. 设G 是一个),(q p 图，若1-≥p q ，则]/2[)(q p G ≤χ。 （×） 10．图G 和1G 同构当且仅当G 和1G 的顶点和边分别存在一一对应关系。（×） 二.填空(本题40分，每空各2分) 1．设}},{,{φφ=S 则=S 2 }}}{,{}},{{},{,{φφφφφ 。 2．设B A ,是任意集合，若B B A =\，则A 与B 关系为 φ==B A 。 3．设1)(,0)()(,:};3,2{},1,0{},,,{===→===c f b f a f Y X f Z Y c b a X , 3)1(,2)0(,:==→g g Z Y g ,则)()(c f g a f g ，分别为 2，3 。 4．设X 和Y 是集合且X m =，Y n =，若n m ≤，则从X 到Y 的单射的 个数为 !m C m n 。 5．设}2,1{},,,2,1{==B n X ，则从X 到Y 的满射的个数为 22-n 。 6．设)}2,4(),1,3(),3,2{()},4,3(),2,2(),2,1{(},4,3,2,1{===S R X ，则 =)(R S R )}2,3(),4,2(),4,1{( 。 7． 设???? ??=???? ??=5123454321,415235432121σσ，则???? ??=235411234521σσ 。 8. 设)},(),,(),,{(},,,,{a c c b b a R d c b a X ==，则 )},(),,(),,(),,(),,(),,(),,(),,(),,{(b c a c a b c b c a b a c c b b a a R =+ 。 9. 设X 为集合且X n =，则X 上不同的自反或对称的二元关系的个数 为 22222222n n n n n n +--+- 。 10．设}}{},{},,{{},,,,{d c b a A d c b a X ==是X 的一个划分，则由A 确定的 X 上的等价关系为 )},(),,(),,(),,(),,(),,{(d d c c a b b a b b a a 。 11．}10,,2,1{ =S ，在偏序关系“整除”下的极大元为 6，7，8，9，10 。 12．给出一个初等函数)(x f ，使得它是从)1,0(到实数集合R 的一一对应， 这个函数为 x ctg π或-x ctg π或)2/(ππ-x tg 。 13. 设G 是),(p p 连通图，则G 的生成树的个数至多为 p 。 目录 第一章图的基本概念 (2) 二路和连通性 (4) 第二章树 (4) 第三章图的连通度 (6) 第四章欧拉图与哈密尔顿图 (8) 一，欧拉图 (8) 二．哈密尔顿图 (10) 第五章匹配与因子分解 (14) 一．匹配 (14) 二．偶图的覆盖于匹配 (15) 三．因子分解 (16) 第六章平面图 (20) 二．对偶图 (24) 三．平面图的判定 (25) 四．平面性算法 (28) 第七章图的着色 (34) 一．边着色 (34) 二．顶点着色 (35) 第九章 有向图 (40) 二 有向树 (41) 第一章 图的基本概念 1. 点集与边集均为有限集合的图称为有限图。 2. 只有一个顶点而无边的图称为平凡图。 3. 边集为空的图称为空图。 4. 既没有环也没有重边的图称为简单图。 5. 其他所有的图都称为复合图。 6. 具有二分类（X, Y ）的偶图（或二部图）：是指该图的点集可以分解为两个（非空）子 集 X 和 Y ，使得每条边的一个端点在 X 中，另一个端点在Y 中。 7. 完全偶图：是指具有二分类（X, Y ）的简单偶图，其中 X 的每个顶点与 Y 的每个顶点 相连，若 |X|=m ，|Y|=n ，则这样的偶图记为 Km,n 8. 定理1 若n 阶图G 是自补的（即 ），则 n = 0, 1（mod 4） 9. 图G 的顶点的最小度。 10. 图G 的顶点的最大度。 11. k-正则图: 每个点的度均为 k 的简单图。 例如,完全图和完全偶图Kn,n 均是正则图。 12. 推论1 任意图中，奇点的个数为偶数。 ()G δ()G ? 13. 14.频序列：定理4 一个简单图G的n个点的度数不能互不相同。 15.定理5 一个n阶图G相和它的补图有相同的频序列。 16. 17. 18.对称差：G1△G2 = (G1∪G2) - (G1∩G2) = (G1-G2)∪(G2-G1) 19.定义：联图在不相交的G1和G2的并图G1+G2中，把G1的每个顶点和G2的每个 顶点连接起来所得到的图称为G1和G2的联图，记为G1∨G2 20.积图：积图设G1= (V1, E1)，G2 = (V2, E2)，对点集V = V1×V2中的任意两个点u = (u1,u2)和v = (v1,v2)，当(u1 = v1和u2 adj v2) 或(u2 = v2 和u1 adj v1) 时就把u 和v 连接起来所得到的图G称为G1和G2积图。记为G = G1×G2 设G1= (V1, E1)，G2 = (V2, E2)，对点集V = V1×V2中的任意两个点u = (u1,u2)和v = (v1,v2)，当(u1 adj v1) 或(u1= v1 和u2 adj v2) 时就把u 和v 连接起来所得到的图G称为G1和G2的合成图。记为G=G1[G2]。 2011二级建造师实务 案例分析一 背景资料： 某广场地下车库工程，建筑面积18000㎡。建设单位和某施工单位根据《建设工程施工合同（示范文本）》（GF-99-0201）签订了施工承包合同，合同工期140天。 工程实施过程中发生了下列事件： 事件一：施工单位将施工作业划分为A、B、C、D、四个施工过程，分别由指定的专业班组进行施工，每天一班工作制，组织无节奏流水施工，流水施工参数见下表： 事件二：项目经理部根据有关规定，针对水平混凝土构件模板（架）体系，编制了模板（架）工程专项施工方案，经过施工项目负责人批准后开始实施，仅安排施工项目技术负责人进行现场监督。 事件三：在施工过程中，该工程所在地连续下了6天特大暴雨（超过了当地近10年来季节的最大降雨量），洪水泛滥，给建设单位和施工单位造成了较大的经济损失。施工单位认为这些损失是由于特大暴雨（不可抗力事件）所造成的，提出下列索赔要求（以下索赔数据与实际情况相符）： （1）工程清理、恢复费用18万； （2）施工机械设备重新购置和修理费用29万； （3）人员伤亡善后费用62万； （4）工期顺延6天。 问题： 1、事件一中，列式计算A、B、C、D、四个施工过程之间的流水步距分别是多少天？5分 答案： 2、事件一中，列式计算流水施工的计划工期是多少天？能否满足合同工期的要求？（5分） 答案： 3、事件二中，指出专项施工方案实施中有哪些不妥之处？说明理由。（5分） 答案： 4、事件三中，分别指出施工单位的索赔要求是否成立？说明理由。5分 答案： 案例分析二 背景资料： 某施工单位承建两栋15层的框架结构工程。合同约定：（1）钢筋由建设单位供应；（2）工程质量保修按国务院279号令执行。开工前施工单位编制了单位工程施工组织设计，并通过审批。施工过程中，发生下列事件：事件一：建设单位按照施工单位提出的某批次钢筋使用计划按时组织钢筋进场。 事件二：因工期紧，施工单位建议采取每5层一次竖向分阶段组织验收的措施，得到建设单位认可。项目经理部对施工组织设计作了修改，其施工部署中劳动力计划安排为“为便于管理，选用一个装饰装修班组按栋分两个施工组织流水作业”。 事件三：分部工程验收时，监理工程师检查发现某墙体抹灰约有1.0㎡的空鼓区域，责令限期整改。 事件四：工程最后一次阶段验收合格，施工单位于2010年9月18日提交工程验收报告，建设单位于当天投入使用。建设单位以工程质量问题需要在使用中才能发现为由，将工程竣工验收时间推迟到11月18日进行，并要求《工程质量保修书》中竣工日期以11月18日为准。施工单位对竣工日期提出异议。 问题： 1、事件一中，对于建设单位供应分该批次钢筋，建设单位和施工单位各应承担哪些责4分 答案： 2、事件二中，施工组织设计修改后，应该什么程序报审？4分 答案： 3、事件二中，本工程劳动力计划安排是否合理？写出合理安排。4分 答案： 4、写出事件三中墙体抹灰空鼓的修补程序（至少列出4项）。4分 答案： 5、事件四中，施工单位对竣工日期提出异议是否合理？说明理由。写出本工程合理的竣工日期。4分 答案： 思考练习 第一章 1对任意图，证明。 证：，故。 2 在一次聚会有个人参加，其中任意6个人中必有3个人互相认识或有3个人互不认识。举例说明，将6个人改成5个人，结论不一定成立。 证：构图如下：图的顶点代表这6个人，两个顶点相邻当且仅当对应的两个人 互相认识。则对于图中任意一个点或。 不妨设及它的3个邻点为。若中有任意两个点，不妨设为 ，相邻，则对应的3个人互相认识；否则，中任意两个点不邻， 即它们对应的3个人互不认识。 若这5个人构成的图是5圈时，就没有3个人互相认识或有3个人互不认识。 3 给定图 画出下列几个子图: (a) ； (b); (c) 解：(a) (b) (c) 第二章 1设是一个简单图，。证明：中存在长度至少是的路。 证：选取的一条最长路，则的所有邻点都在中，所以 ，即中存在长度至少是的路。 2证明：阶简单图中每一对不相邻的顶点度数之和至少是，则是连通图。 证：假设不连通，令、是的连通分支，对，有 ，与题设矛盾。故连通。 3设是连通图的一个回路，，证明仍连通。 证：，中存在路， 1、若，则是中的路； 2、若，则是中的途径，从而中存在 路。 故连通。 4图的一条边称为是割边，若。证明的一条边是割边当且仅当不含在的任何回路上。 证：不妨设连通，否则只要考虑中含的连通分支即可。 必要性：假设在的某一回路上，则由习题2.13有连通，，与是割边矛盾。故不在回路中。 充分性：假设不是割边，则仍连通，存在路，则就是含的一个回路，与不在回路中矛盾。故是割边。 5证明：若是连通图，则。 证：若是连通图，则。 第三章 1 证明：简单图是树当且仅当中存在一个顶点到中其余每个顶点有且只有一条路。 证：必要性：由定理3.1.1立即可得。 充分性：首先可见连通。否则，设有两个连通分支、，且， 则到中的顶点没有路，与题设矛盾。 其次，中无回路。否则，若有回路。由于连通，到上的点有路， 且设与的第一个交点为，则到上除外其余点都至少有两条路，又与题设矛盾。 故是树。 2 设图有个连通分支，。证明含有回路。 证：假设中不含回路。设的个连通分支为，则每个连通无回路，是树。从而 ， 与题设矛盾，故无回路。 3是连通简单图的一条边。证明在的每个生成树中当且仅当是的割边。 证：必要性：假设不是的割边，即连通，有生成树，与在的每个生成树矛盾。故不是的割边。 充分性：假设存在一棵生成树，使得不在中，从而连通，与是的割边矛盾。故在的每个生成树中。 4设是至少有3个顶点的连通图，证明中存在两个顶点，使得仍 离散数学图论部分综合练习 一、单项选择题 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 2011年度全国注册安全工程师执业资格考试试卷安全生产事故案例分析 中华人民共和国 人事考试中心制 人力资源和社会保障部 二O 一一年七月 一、A焦化厂为民营企业，从业人员1000人，2009年发生生产安全事故2起、造成2人轻伤。该厂因精苯工业废水兑水稀释后外排，被环保部门责令整改。该厂采取的措施是将废水向煤堆喷洒，这样既仰制了扬尘，又避免了废水外排。为防止相关事故发生，该厂于2009年5月20日制定实施了《A焦化厂精苯污水喷洒防尘管理办法》。 2011年5月11日15时20分许，A厂备煤工甲、乙在进行胶带输送机巡检作业时闻到强烈异味，随后两人分别前往不同部位查找原因。15时38分，乙听到从甲的方向传来一声闷响，气浪迎面扑来，发现通廊部分坍塌。乙立即呼救。厂领导接到报告后，迅速组织对胶带输送机通廊坍塌现场进行搜救，在胶带输送机通廊北端发现甲倒在废墟中。甲头部有明显外伤，身上大面积烧伤，经医务人员确认已经死亡。 事故调查确认，此次事故为1号煤仓内苯蒸汽爆炸事故。在含苯废水向煤场内煤堆喷洒1年后，废水管道断裂，废水从管道断裂处流入煤堆底部，经胶带输送机运输，大量含苯煤粉进入1号煤仓，从含苯煤粉中挥发出的低浓度苯蒸汽积累、聚集达到爆炸极限，遇到点火源后引起爆炸。 根据以上场景，回答下列问题（共14分，每题2分，1~3题为单选题，4~7题为多选题）： 1、根据《中华人民共和国安全生产法》关于安全生产管理机构设置及安全管理人员配备的规定，A厂（） A.可以只配备兼职安全生产管理人员。 B.可以委托注册安全工程师事务所代管企业安全生产。 C.可以委托具有安全评价资质的评价机构代管企业安全生产。 D.应当设置安全生产管理机构或配备专职安全生产管理人员 E.可以委托具有注册安全工程师职业资格的个人代管企业安全生产。 2、A厂招收新从业人员，新上岗的从业人员安全培训时间不得少于（）学时 A.12 B.24 C.36 D.48 E.72 3、A厂2009年百万工时伤害率（） A.1 B.2 C.3 D.4 E.5 4、根据注册安全工程师管理规定，作为A厂的注册安全工程师，可从事的安全生产工作包括（） A、参与本厂组织的事故调查 B、参与本厂厂内隐患排查治理 C、进行本厂员工职业病鉴定 D、参与本厂员工安全培训 E、为本厂选用和发放劳动防护用品 答案：ABDE。解析： 第十九条生产经营单位的下列安全生产工作，应有注册安全工程师参与并签署意见： （一）制定安全生产规章制度、安全技术操作规程和作业规程； （二）排查事故隐患，制定整改方案和安全措施； （三）制定从业人员安全培训计划； （四）选用和发放劳动防护用品； （五）生产安全事故调查； （六）制定重大危险源检测、评估、监控措施和应急救援预案； （七）其他安全生产工作事项。 5、根据生产事故调查和处理条例，该起事故的调查，下列说法正确的是（） A、由A厂所在地县级人民政府国资委组织调查 B、由A厂所在地县级人民政府安全生产监督管理部门组织调查 C、由A厂所在地县级人民政府环境部门组织调查 D、可邀请相关专家作为调查组成员参与事故调查 E、A厂上级主管部门、工会参与事故调查 答案：BDE。事故调查组成员有关人民政府、安全生产监督管理部门、负有安全生产监督管理职责的部门、工会、公安机关、监察机关。可以邀请人民检察院参与事故调查。还可以聘请专家参与事故调查。从题目来看，国资委（如果属于国有企业）和环保部门可以参加事故调查，绝对不可能组织事故调查。 6、A厂工作场所存在的职业性有害因素包括（） 浙江师范大学《图论》考试卷 （2007－2008学年第一学期） 考试类别 闭卷 使用学生 行知数学 051.052. 考试时间 150 分钟 出卷时间 2008年1月4日 说明：考生应将全部答案都写在答题纸上，否则作无效处理。 一、填空题 (25%) 1、给定图G 11 （1）给出图G 的一条最长路＿＿＿＿＿＿＿； （2）给出图G 的二个参数值λ(G)= ,κ(G)= ； （3）给出图G 的一个最大独立集 ； （4）作出子图G[u 2,u 5,u 7,u 9,u 11,u 12]________,G-{u 8,u 9,u 12}____________, G-{u 1u 3,u 1u 4,u 1u 7,u 1u 10}_________ _______； 2、图G 是二分图的充分必要条件是 ； 3、G=(X,Y,E)是二分图，无孤立点，则β1(G) 与α0(G)的关系是 ； 4、Ramsey 数r(k,t)、r(k-1,t) 和r(k,t-1) 的关系是 ； 5、G 是含有56个顶点的无回路图，且对Ｇ中任两个不相邻的顶点v u ,，Ｇ+uv 有唯一的回路，则Ｇ的边数为____________; 6、图G 有Euler 环游的充要条件是＿＿＿＿； 二、设七个字母在通迅中出现频率分别为a;25%,b;22%,c;20%,d;12%,e;10%,f;6%，g;5%。编一个最优前缀码，并画出相应的最优二元树。 (15%) 三、 证明：非平凡连通图G 至少有二个非割点。 (10%) 四、 G 是点色数χ(G)=2的k —正则简单图。证明G 有k 个边不交的完美对集M 1,M 2, ┄, M k ， 使 E(G)= M 1∪M 2∪┄∪M k 。 (13%) 五、 给出平面图G 的顶点数p(G)、边数q(G)、面数 )(G ?和连通分支数ω(G)的一个关系式， 并给予证明。 (15%) 六、 G 是p 个顶点的简单图，对G 中每一对不相邻的顶点u 、v,均有d G (u)+d G (v)≥p-1。 （1） 证明G 有Hamilton 路；（2） G 是二连通图吗？为什么？。 (12%) 七、设Ｇ是连通图，若对每个真子集V 0?V(G) ，只要∣V 0∣≤k-1，G- V 0仍连通.证明q(G)≥ kp(G)/2 。 (10%) 组合数学部分 第1章 排列与组合 例1： 1)、求小于10000的含1的正整数的个数； 2、)求小于10000的含0的正整数的个数； 解：1)、小于10000的不含1的正整数可看做4位数,但0000除外.故有9×9×9×9－1＝6560个.含1的有：9999－6560=3439个 2)、“含0”和“含1”不可直接套用。0019含1但不含0。在组合的习题中有许多类似的隐含的规定，要特别留神。不含0的1位数有19个，2位数有29个，3位数有39个，4位数有49个 不含0小于10000的正整数有() ()73801919999954321=--=+++个含0小于10000的正整数9999－7380=2619个。 例2： 从[1,300]中取3个不同的数，使这3个数的和能被3整除，有多少种方案？ 解：将[1,300]分成3类： A={i|i ≡1(mod 3)}={1,4,7,…,298}, B={i|i ≡2(mod 3)}={2,5,8,…,299}, C={i|i ≡0(mod 3)}={3,6,9,…,300}. 要满足条件，有四种解法： 1)、3个数同属于A; 2)、3个数同属于B ； 3)、3个数同属于C; 4)、A,B,C 各取一数；故共有3C(100,3)+1003=485100+1000000=1485100。 例3：（Cayley 定理：过n 个有标志顶点的数的数目等于2-n n ） 1）、写出右图所对应的序列； 2）、写出序列22314所对应的序列； 解： 1）、按照叶子节点从小到大的顺序依次去掉节点（包含与此叶子 节点相连接的线），而与这个去掉的叶子节点相邻的另外一个点值则记入序列。如上图所示，先去掉最小的叶子节点②，与其相邻的点为⑤，然后去掉叶子节点③，与其相邻的点为①，直到只剩下两个节点相邻为止，则最终序列为51155.。 2）、首先依据给定序列写出（序列长度+2）个递增序列，即1234567，再将给出序列按从小到大顺序依次排列并插入递增序列得到：7。我们再将给出序列22314写在第一行，插入后的递增序列写在第二行。如下图第一行所示： ??→????? ??--②⑤67112223344522314??→???? ? ??--②⑥11223344672314 ??→????? ??--③②11233447314??→???? ? ??--①③11344714 案例一 文员小曹向分管营销业务的孙副经理请示了业务处理的意见后，又遇到了负责宣传的张副经理，小曹又向他作了请示，结果两位领导的意见很不一致，小曹无所适从，两位领导也因此矛盾加深。孙认为小曹与张关系亲近些，支持过张，认为小曹有意与他作对；而张认为此业务是他引介的，小曹应先同他通气。 问题：请你分析小曹这样做对不对？错在哪里？面对这种情况小曹应该怎么办？ 1、小曹犯了多头请示的错误。遵照领导职权分工、单向请示的原则，既然向主管 领导请示乐乐，就应该按孙的意见办，不应多头请示。 2、在工作中不应过分亲近或疏远某领导，以至落到尴尬的境地。 3、两位领导都做了指示，如果张通情达理，小曹应向他说明只能按职权分工办事， 求得谅解后，按孙的意见办。 4、如果不能求得谅解是，小曹应向两位领导分别自我检讨，再建议两位商讨一个 方法遵照执行。 5、如果矛盾不能统一，应向总经理请示，遵照总经理的意见办，并请 他对孙或张作解释。这时文员执行主要决策人的意见。 案例二 新加坡利达公司销售部文员刘小姐要结婚了，为了不影响公司的工作，在征得上司的同意后，她请自己最好的朋友陈小姐暂时代理她的工作，时间为一个月。陈小姐大专刚毕业，比较单纯，刘小姐把工作交代给她，并鼓励她努力干，准备在蜜月回来后推荐陈小姐顶替自己。 某一天，经理外出了，陈小姐正在公司打字，电话铃响了，陈小姐与来电者的对话如下：来电者：“是利达公司吗？” 陈小姐：“是。” 来电者：“你们经理在吗？” 陈小姐：“不在。” 来电者：“你们是生产塑胶手套的吗？” 陈小姐：“是。” 来电者：“你们的塑胶手套多少钱一打？” 陈小姐：“1.8美元。” 来电者：“1.6美元一打行不行？” 陈小姐：“对不起，不行的。”说完，“啪”挂上了电话。 上司回来后，陈小姐也没有把来电的事告知上司。过了一星期，上司提起他刚谈成一笔大生意，以1.4美元一打卖出了100万打。陈小姐突口而出：“啊呀，上星期有人问1.6美元一打行不行，我知道你的定价是1.8，就说不行的。”上司当即脸色一变说：“你被解雇了”陈小姐哭丧着脸说：“为什么？”上司说：“你犯了五个错。” 问题：陈小姐被解雇是因为上司说她犯了五个错，分别是什么？她在电话礼仪方面还犯了哪些错？ 1、该问的没有问（对方情况，手套的需要量等） 2、该记得没有记录：对方姓名、公司、电话号码 3、该说的没有说：没有及时向上司汇报 4、不该说的却说了：价格上的自作主张，不向上司请示 电子科技大学研究生试卷 （测试时间：至，共__2_小时） 课程名称图论及其使用教师学时60 学分 教学方式讲授考核日期_2012__年___月____日成绩 考核方式：（学生填写） 一、填空题（填表题每空1分，其余每题2分，共30分) 1．n 阶k 正则图G 的边数()m G =___ ___2 nk ； 2．3个顶点的不同构的简单图共有___4___个； 3．边数为m 的简单图G 的不同生成子图的个数有__2___m 个； 4. 图111(,)G n m =和图222(,)G n m =的积图12G G ?的边数为1221____n m n m +； 5. 在下图1G 中，点a 到点b 的最短路长度为__13__； 6. 设简单图G 的邻接矩阵为A ，且 23 112012********* 102001202A ?? ? ? ?= ? ? ??? ，则图G 的边数为 __6__； 7. 设G 是n 阶简单图，且不含完全子图3K ，则其边数一定不会超过2___4n ?? ????； 8．3K 的生成树的棵数为__3__; 9. 任意图G 的点连通度()k G 、边连通度()G λ、最小度()G δ之间的关系为 __()()()____k G G G λδ≤≤； 10. 对下列图，试填下表（是??类图的打〝√ 〞，否则打〝?〞）。 ① ② ③ 学号姓名学院 ……………………密……………封……………线……………以……………内……………答……………题……………无……………效…………………… 4 5 6 6 4 1 1 2 7 2 4 3 a b G 1 能一笔画的图 Hamilton 图 偶图 可平面图 ① ? √ ? √ ② ? ? ? √ ③ ? √ √ √ 二、单项选择(每题2分，共10分) 1．下面命题正确的是(B ) 对于序列(7,5,4,3,3,2)，下列说法正确的是： (A) 是简单图的度序列； (B) 是非简单图的度序列; (C) 不是任意图的度序列; (D)是图的唯一度序列. 2．对于有向图，下列说法不正确的是(D) (A) 有向图D 中任意一顶点v 只能处于D 的某一个强连通分支中； (B) 有向图D 中顶点v 可能处于D 的不同的单向分支中; (C) 强连通图中的所有顶点必然处于强连通图的某一有向回路中; (D)有向连通图中顶点间的单向连通关系是等价关系。 3.下列无向图可能不是偶图的是( D ) (A) 非平凡的树； (B)无奇圈的非平凡图； (C) n (1)n ≥方体； (D) 平面图。 4.下列说法中正确的是( C ) (A)连通3正则图必存在完美匹配； (B)有割边的连通3正则图一定不存在完美匹配； (C)存在哈密尔顿圈的3正则图必能1因子分解； (D)所有完全图都能作2因子分解。 5. 关于平面图，下列说法错误的是( B ) (A) 简单连通平面图中至少有一个度数不超过5的顶点； (B)极大外平面图的内部面是三角形，外部面也是三角形； (C) 存在一种方法，总可以把平面图的任意一个内部面转化为外部面； (D) 平面图的对偶图也是平面图。 三、 (10分)设G 和其补图G 的边数分别为12,m m ，求G 的阶数。 解：设G 的阶数为n 。 因12(1) 2n n m m -+=…………………………………4分 所以：212220n n m m ---=……………………..2分 1 2017年图论课程练习题 一．填空题 1.图1中顶点a 到顶点b 的距离d (a ,b )= 。 a b 9 图1 1 2.已知图G 的邻接矩阵0 11011 01001 1010001011001 0A = ，则G 中长度为2的途径总条数为 。 3.图2中最小生成树T 的权值W (T )= 。 4.图3的最优欧拉环游的权值为 。 12 图 2 2 图3 5.树叶带权分别为1,2,4,5,6,8的最优二元树权值为 。 二．单项选择 1．关于图的度序列，下列说法正确的是( ) (A) 对任意一个非负整数序列来说，它都是某图的度序列； (B) 若非负整数序列12(,,,)n d d d π= 满足1n i i d =∑为偶数，则它一定是图序 列； (C) 若图G 度弱于图H ，则图G 的边数小于等于图H 的边数； (D) 如果图G 的顶点总度数大于或等于图H 的顶点总度数，则图G 度优 于图H 。 2．关于图的割点与割边，下列说法正确的是（ ） (A) 有割边的图一定有割点； (B) 有割点的图一定有割边； (C) 有割边的简单图一定有割点； (D) 割边不在图的任一圈中。 3.设()k G ，()G λ，()G δ分别表示图G 的点连通度，边连通度和最小度。下面说法错误的是( ) 3 (A) 存在图G ，使得()k G =()G δ=()G λ； (B) 存在图G ，使得()()()k G G G λδ<<； (C) 设G 是n 阶简单图，若()2n G δ ≥ ，则G 连通，且()()G G λδ=； (D) 图G 是k 连通的，则G 的连通度为k 。 4.关于哈密尔顿图，下列命题错误的是( ) (A) 彼得森图是非哈密尔顿图； (B) 若图G 的闭包是哈密尔顿图，则其闭包一定是完全图； (C) 若图G 的阶数至少为3且闭包是完全图，则图G 是哈密尔顿图； (D) 设G 是三阶以上简单图，若G 中任意两个不邻接点u 与v ，满足 ()()d u d v n +≥，则G 是哈密尔顿图。 5.下列说法错误的是( ) (A) 有完美匹配的三正则图一定没有割边； (B) 没有割边的三正则图一定存在完美匹配； (C) 任意一个具有哈密尔顿圈的三正则图可以1因子分解； (D) 完全图21n K +是n 个哈密尔顿圈的和。 三、 设无向图G 有10条边，3度与4度顶点各2个，其余顶点度数均小于3，问G 中至少有几个顶点？在最少顶点数的情况下，写出G 的度序列，该度序列是一个图序列吗？。 案例1： 林某是一家高科技企业的年轻的客户经理，有着双学位的学历背景和较好的客户资源，但是个性较强的林某，常常是公司各种规章制度的“钉子户”，果不其然在公司新的绩效考核方法推行的过程中，林某又一次“撞到枪口上”。 林某所在的公司所推行新的考核办法是根据每个员工本月工作的工时和工作完成度对其工作进行考核，考核结果与工资中的岗位工资和绩效工资挂钩，效益工资和员工创造出的相关效益挂钩。因为该公司有良好的信息化基础，工时是根据员工每日在信息化系统上填写的工作安排和其直接上级对员工工作安排工时的核定来累计的，员工的工作完成度也是上级领导对员工本月任务完成情况的客观反映。上月月末，该公司绩效考核专员根据信息化系统所提供的数据，发现林某上月的工时离标准工时差距很大而且林某的工作完成度也偏低，经过相关工资计算公式的演算，林某这个月的工资中的岗位工资和绩效工资要扣掉几百元钱。 拿到工资后的林某，面对工资数额的减少，非常激动，提出了如下几点质疑：1.工作安排不写不仅是他的错，因为上级朱某没有及时下达任务；2.没有完成相关的经济目标责任也不应该全由他承担，因为这和整个公司的团队实力有关；3.和他同一岗位的同事相比，他认为自己的成绩比别人好，而拿到手上的工资却比同事低的多，这太不公平。 带着一身的怨气，林某走进了一向以严明著称的公司董事长赵某办公室…… 诊断分析 这是一个典型的因为绩效评估结果而造成的纠纷，这个纠纷涉及的三个当事人分别是：林某——绩效评估的对象；朱某——绩效评估者；赵某——绩效评判者。简言之就是运动员、裁判和运动会主席之间的故事。 我们先从三者的心理分析入手： 林某：考核不公正。林某对于考核不公正的看法产生于对于考核过程的责任归属有异议，对于考核结果横向比较的内部公平性赶到不满。 朱某：考核真无奈。朱某对于林某一向抱有“惜才”的心理，对于林某平时的一些表现，也仅仅是“点到为止”。对于根据系统计算出的考核结果，朱某也非常吃惊，并且面对这样的结果朱某感到很大的压力。 赵某：考核本应公正严明。面对考核结果，应该公正严明处理，不能因为任何一个个体而违反考核的原则，考核的意义是让员工更好的工作，考核的关键是考核的过程而不是考核的结果。 从董事长赵某的态度和观念上，我们可以看到，这个问题的关键主要在考核的过程沟通和处理。作为林某，在公司推行新的考核办法后，应该予以积极的配合，不能因为上级领导的放松而自我放松，并且对于工作上需要利用的公司资源应主动与公司沟通，而不是消极的等待公司来对责任的认定，至于与同事之间的横向比较也是因为缺乏对考核的理解，考核是对工作过程的一种综合评判，而并非单纯的对工作业绩的反馈，林某所在的公司工作业绩更多的反映在员工效益工资和相关奖金中。作为林某的直接上级朱某，应该在日常工作中对于林某的一些工作行为及时予以提醒、指正，不能自己束缚住手脚，面对管理上的困难，也应该及时和上级请示，寻求上级的支持和方法上的建议，这样也不会将矛盾激化，出现自己被动的局面。 所以就这个案例来说，矛盾的根源是林某自身对绩效考核缺乏理解和认识，同时林某的直接上级忽视了考核过程中的绩效沟通，缺乏管理的力度和方法。针对这样的情况，董事长赵某和林某进行了交流，向其阐述绩效考核的意义和相关方法，并对其工作上的一些行为和观念上的误区进行了指正，这使得林某心服口服，更加深切的明白企业是需要的人才是德才兼备的。对于朱某，赵董事长向其建议了相关改进的工作方法，并对他的工作提供了更多了支持，这使得朱某增加了管理的信心。于此同时，赵董事长降低了朱某和自己的工作完成度，在工资总额上都相应减少了。虽然从结果上看，案例中的三个当事人都扣了工资，但是林某的怨气没有了，朱某的困惑消除了，这个纠纷解决了。 思维纵深 CAD 2004初级教程 打开方式：1、双击桌面CAD图标 2、开始——程序——Autodesk——Auto CAD2004 文件的新建,打开,保存,关闭命令 新建：1.文件菜单下新建命令 2.快捷键为Ctrl+N 打开: 1.文件菜单下打开命令 2.快捷键为Ctrl+O 保存: 1.文件菜单下保存命令 2.快捷键为Ctrl+S 关闭：1.单击标题栏上的关闭按纽 二、鼠标作用 左键为1.选择物体2.确定图形第一点的位置 滚轴作用为1.滚动滚轴放大或缩小图形(界面在放大或缩小) 2.双击可全屏显示所有图形 3.如按住滚轴可平移界面 空格：1、确定（下文中出现“确定”部分均按空格） 2、执行上步命令 三、选择物体的方法 1、直接点击 2、正选：左上角向右下角拖动(全部包含其中) 3、反选：右下角向左上角拖动(碰触到物体的一部分就行) 一、直线命令（快捷键为L） 绘制方式:1.直接在绘图工具栏上点击直线按纽 2.在绘图菜单下单击直线命令 3.直接在命令中输入快捷键L（在命令行内输入命令快捷 键，回车或空格或鼠标右键确定） 直线的输入的方法1.从命令行内输入直线命令的快捷建L确定,2.用鼠标左键在屏幕中点击直线一端点,拖动鼠标,确定直线方向3.输入直线长度确认依照同样的方法继续画线直至图形完毕,按空格键结束直线命令。 取消命令方法为按ESC键或右击。 二、构造线命令（快捷键为XL）：一般作为辅助线使用，创建的线是无限长的。 绘制方式：1.直接在绘图工具栏上点击构造线按纽 2.在绘图菜单下单击构造线命令 3.直接在命令中输入快捷键XL 在构造线命令行中：H为水平构造线，V为垂直构造线，A为角度（可设定构造线角度，也可参考其它斜线进行角度复制），B二等分（等分角度，两直线夹角平分线），O偏移（通过T，可以任意设置距离。） -- 本试卷满分90分 (计算机科学与技术学院0９级各专业) 一、填空（本题满分１0分,每空各1分) 1.设B A ,为集合,则A B B A = )\(成立的充分必要条件是什么？(A B ?) ２.设}2,1{},,,2,1{==Y n X ,则从X 到Y 的满射的个数为多少?（22-n ) ３．在集合}11,10,9,8,4,3,2{=A 上定义的整除关系“|”是A 上的偏序关系， 则 最大元是什么? ( 无 ） 4．设{,,}A a b c =，给出A 上的一个二元关系,使其同时不满足自反性、反自 反性、对称性、反对称和传递性的二元关系。({(,),(,),(,),(,)}R a a b c c b a c =） ５．设∑为一个有限字母表,∑上所有字(包括空字）之集记为*∑，则*∑是 否是可数集? （ 是 ) ６.含5个顶点、3条边的不同构的无向图个数为多少？ （ ４ ） 7.若G 是一个),(p p 连通图，则G 至少有多少个生成树? （ 3 ） 8. 如图所示图G ,回答下列问题： (１）图G 是否是偶图? ( 不是 ) (2）图G 是否是欧拉图? ( 不是 ） (3)图G 的色数为多少？ ( 4 ) 二、简答下列各题（本题满分40分） 1．设D C B A ,,,为任意集合，判断下列等式是否成立?若成立给出证明，若不 成立举出反例。(6分) (1))()()()(D B C A D C B A ??=? ； （2）()()()()A B C D A C B D ?=??。 解:（1）不成立。例如}{,a c B D A ====φ即可。 （2）成立。(,)x y ?∈()()A B C D ?，有,x A B y C D ∈∈，即 ,,,x A x B y C y D ∈∈∈∈。所以(,),(,)x y A C x y B D ∈?∈?,因此 (,)()()x y A C B D ∈??,从而()()A B C D ??()()A C B D ??。 反之,(,)x y ?∈()()A C B D ??，有,,,x A x B y C y D ∈∈∈∈。即 (,)x y ∈()()A B C D ?，从而()()A C B D ???()()A B C D ?。电子科技大学研究生试题《图论及其应用》(参考答案)
统计案例试题及答案
集合论与图论 试题A
图论期末考试整理复习资料
历年二建案例真题及答案
图论试题浙师大
离散数学图论部分经典试题及答案
2011年案例试题及答案
图论模拟题
图论与组合数学期末复习题含答案
案例题及参考答案
12年图论试题
电子科技大学2017年图论期末试卷
人力资源案例分析题10道及答案
(完整word版)Cad2007教程(适合零基础)分析
哈工大年集合论与图论试卷
相关主题
文本预览