图论复习题答案
一、
判断题，对打√，错打
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
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+3?3+（7+4+5）?2=53 5．出席某次国际学术报告会的六个成员
654321,,,,,P P P P P P 被分在一组。他们的情况是：
1P 会讲汉语、法语和日语； 2P 会讲德语、日语和俄语；
3P 会讲英语和法语；
4P 会讲汉语和西班牙语；
5P 会讲英语和德语； 6P 会讲俄语和西班牙语。
怎样把他们安排在一张圆桌旁坐下，使得每个人都能和他两旁的人交谈？ 解 构造无向图>= },,,,,{654321P P P P P P V =，}|),{(会讲同一种语言与j i j i P P P P E =， 则得无向图如图所示。 3 2P 4P 6P 5 电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：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 《政治学原理》综合练习题及答案（三） 二、选择题 51、下列组织属于邦联制的是（ ABD） A、欧洲共同体 B、独联体 C、俄罗斯联邦 D、东南亚国家联盟 52、为了有效消除执政者的欲望，防止执政偏向，亚里士多德提出了（ABD）等一系列的权力制约方法。 A、限任 B、监督 C、法治 D、选举 53、纵观各国的宪法，以下的（ABCD）体现了法治原则。 A、司法独立 B、国家制定的法律必须是良法 C、法律面前人人平等 D、各国家机关的权力必须由宪法和法律授予。 54、马克思主义认为（ A）是奴隶制和封建制国家的典型政体形式。 A、专制君主制 B、立宪君主制 C、二元君主制 D、寡头制 55、从社会主义的发展历史来看，具有典型意义的政体形式主要有（ACD）。 A、苏维埃政权形式 B、委员会政权形式 C、巴黎公社政权形式 D、人民代表大会政权形式 56、马克思主义认为，国家是（ AD）的产物。 A、私有制 B、社会契约 C、社会共同体 D、分工 57、（ C ）是政府的灵魂。 A、权威性 B、有机组织性 C、阶级性 D、公共性 58、（ D ）原则是现代宪法为国家组织规定的第一个基本原则，它主要阐明了国家权力的来源和归属问题。 A、权力制约原则 B、法治原则 C、法制原则 D、人民主权原则 59、作为1787年美国宪法主要起草人的（ A）指出，一个国家的统治者和被统治者都不是天使而是人，因而防止把某些权力逐渐集中于同一部门的最可靠办法，就是给予各部门的主管人抵制其他部门侵犯的必要法定手段和个人的主动。 A、汉密尔顿 B、华盛顿 C、杰斐逊 D、潘恩 60、（ B ）指出：在专制政府中国王便是法律，同样地，在自由国家中法律便应成为国王。 A、杰斐逊 B、潘恩 C、汉密尔顿 D、华盛顿 61、市民社会是国家权力体系外自发形成的一种自治社会，以其（ AD）为特点。 A、制度化 B、平等性 C、组织化 D、独立性 62、政党形成于19世纪初期，它的产生是现代（ D）政治发展的产物。 A、委员会 B、君主立宪 C、精英民主 D、议会民主 63、1847年，马克思恩格斯创立了第一个国际性的工人阶级政党（ D）。 A、第一国际 B、社会工人党 C、共产党 D、共产主义者同盟 64、共产党组织被认为是（ C ）政党的典型。 A、核心会议型 B、支部型 C、单位化 D、代表性 65、中国共产党领导的多党合作中的民主党派属于（D）。 A、在野党 B、反对党 C、执政党 D、参政党 66、（ A D ）是多党制的典型。 A、法国 B、美国 C、日本 D、意大利 67、作为社会（或市民社会）构成的主要角色，（ C D）是现代政治生活中的重要政治现象，是现代政治体系的重要组成部分。 本试卷满分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]。 政治学原理复习题 (课程代码264001) 一、名词解释 1、政治权利 2、国家 3、政治权力 4、政党 5、政治文化 6、两党制 7、政治统治 8、联邦制 9、政治管理 二、简答 1、简述政治统治与政治管理的关系。 2、政治领袖的政治心理有哪些基本类型。 3、什么是政治学？试简要对比中西方政治学历史演变。 4、什么是政党？简述资本主义国家的不同政党类型。 5、简述政治统治的基础与方式。 6、简述政治权力的构成要素及其特性。 7、简述社会主义政党制度。 三、辨析 1、我国唯一的执政党是中国共产党，其余民主党派的实质身份就是西方政党制度中 的在野党。 2、苏联和中国都实行社会主义政党制度，所以二者采取了完全相同的政党制度。 3、从我国实行“一国两制”以后，我国已经不再是一个单一制国家，而成为复合制 国家 4、政治统治和政治管理一样都只能是少数人对多数人的统治。 四、论述 1、试结合现实，评述我国各类政治社团的发展历程以及对当前政治生活的影响。 2、中国共产党领导的多党合作制与政治协商制有哪些特点？并据此说明在中国为什 么不能照搬西方的政党制度？ 一、名词解释 1、所谓政治权利，就是在特定的社会经济基础上，由社会公共权力确定的社会成员获得自身利益的特定资格。 2、国家的起源：国家是一个历史的、社会的产物，是最高社会公共权力的体现。原始社会并未形成国家，但已在孕育之中。（血亲复仇、近亲不能结婚和氏族议事大会）形成国家的要素：领土、人口、语言、主权。国家的本质：阶级矛盾不可调和的产物，阶级统治的工具。 3、政治权力实际上是在特定的力量对比关系中，政治权力主体为了实现和维护自身的利益而拥有的对政治权力客体的制约能力。政治权力在本质上是特定的力量制约关系，最高形式是特定的国家权力。 4、政党：本质上是特定阶级利益的集中代表，是特定阶级政治力量中的领导力量，是由各阶级的政治中坚分子为了夺取或巩固国家的政治权力而组成的政治组织。 5、人们在社会政治生活当中形成的对于政治生活的感受、认识、情感和道德习俗规范的复杂综合。政治文化一般由政治心理和政治思想两个层次构成。 6、两党制：代表资产阶级不同利益集团的两大政党通过竞选而轮流掌握国家政治权力，组织政府，主持国家政治事务的制度。两党制起源于英国，后推行到美国、加拿大、澳大利亚、新西兰等国。 7、政治统治就是阶级统治，它是经济上最强大的、占优势地位的阶级，为维护和强化既定的政治关系和社会秩序，通过国家权力而对全社会所进行的一种强力支配与控制。 8、联邦制国家：由若干相对独立的政治实体或行政区域通过政治协议而组成的联合体。联邦制国家的具体特点如下： （1）国家具有最高的立法、行政、司法机关，行使国家最高政治权力。各联邦组成单位也有自己独立的立法、行政和司法机关，且与中央机关之间没有隶属关系。 （2）国家有统一的宪法和基本法律，但是，在国家统一宪法和基本法律的范围内，各联邦成员又有自己的宪法和法律。 （3）在对外关系中，中央政府拥有外交权，各联邦组成单位也有一定的对外交往独立性。 当前世界上主要的联邦制国家包括：美国、俄罗斯、加拿大、印度、澳大利亚、巴西、 思考练习 第一章 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 基本信息 试卷号：9811 作业名称：第一次作业 学生学号：17 学生：爽 第一次作业 试题总分：100 单选题 单选题：（共25道试题，每题4分） 1．在2000多年的历史演变中，（）学说成为与中央集权的君主专制体制最相匹配的政治意识形态。 A．墨家 B．儒家 C．法家 D．道家 2．威权主义的政府如果政治体系腐败不堪，效率低下，无法维持政治稳定的局面，并且无法吸收新生社会力量时，则有可能发生（）。 A．政变 B．政治改良 C．政治革命 D．政治改革 3．实行（）的国家往往采用单名选区制。 A．一党居优制 B．两党制 D．一党制 4．（）在《自由与繁荣的国度》中指出：“分析旧自由主义纲领与新自由纲领之间的区别最简单、最直观的方法是看它们如何理解平等问题”。 A．诺齐克 B．米瑟斯 C．罗尔斯 D．哈耶克 5．美国政治学家（）认为政治是对于社会价值的权威性分配的决策活动。这一定义在当今西方社会得到广泛认同和引用。 A．马克斯·韦伯 B．戴维·伊斯顿 C．汉密尔顿 D．哈罗得·拉斯韦尔 6．（）是政治权力主观构成要素中最为基本的要素。 A．组织 B．能力素质 C．身份资格 D．理论与策略 7．（）理论认为，就是人民统治，即所谓的“人民当家作主”。 A．自由 B．代议制 D．间接参与 8．（）理论是现代的主流理论，也是现代通行的宪政制度的理论基础。 A．代议制 B．直接参与 C．精英 D．多元 9．虽然解决矛盾或危机的方法很多，但在政治制度中， （）则是最根本的途径。 A．监督 B．选举 C．弹劾 D．罢免 10．当今世界上，大多数国家都实行（）。 A．多党制 B．两党制 C．一党居优制 D．一党制 11．中国共产党领导的多党合作制中的党派属于 （）。 A．在野党 B．反对党 C．执政党 浙江师范大学《图论》考试卷 （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 电子科技大学研究生试卷 （测试时间：至，共__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 的度序列，该度序列是一个图序列吗？。 《政治学原理》试题卷号：（） 一、填空题(每空分，共计分) ．韩非指出，政治就是用权，“先王所期者利也，所用者力也”。 ．马基雅维利被认为是近代西方政治科学的奠基人。 ．经验事实表明，权力的滥用是社会动荡的根源。 ．权力制约原则在资本主义国家的宪法中主要表现为分权原则。 ．政党和社会团体是公民进入政治体系(市场)，形成政治输入的中介。 ．善治提倡有效率的治理，它对效率的强调则不局限于管理效率，同关注制度本身的效率。 ．政治制度化包括政治参与的制度化、政治管理的制度化两个基本方面的内容。 ．现代民主宪政包含人民的统治和对人民的保护两方面的内容。 二、选择题(每小题分，共计分。每题至少有一个正确答案，多选或少选均不能得分) ．“政治”概念的提出，始于人类文明史上的( )社会时期。 ．封建．奴隶．资本主义．原始 ．道德政治观或伦理政治观最为典型的例子是中国古代的( )学说和古希腊学者们的认识。 ．法家．杂家．兵家．儒家 ．古典政治学时代政治学研究的主题是关于( )。 ．城市国家的观念．城邦的理论 ．世界国家论．直接民主理论 ．( )技术指导文件是“法治”社会的政治设计思路。 ．科学主义．经验主义．现实主义．理想主义．马克思主义认为( )是凝聚社会力量的核心。 ．国家．共产党．民族认同．利益 ．( )是政治权力的主观构成要素。 ．组织．能力素质．身份资格．理论与策略．除了国家的阶级本质之外，下列( )因素影响着具体国家和历史发展阶段中具体政体的选择。 ．具体的历史条件．民族构成 ．政治力量的对比．经济生活方式 ．当今世界，( )实行单一制国家结构形式。 ．法国．中国．德国．日本 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 ?。 《政治学原理》历届试题及答案 试卷代号:2209 中央广播电视大学2006-2007学年度第一学期“开放专科”期末考试行政管理专业 政治学原理试题（2007年1月） 一、填空(每空1分，共6分) 1、政治制度化包括政治参与的制度化、（）的制度化两个基本方面的容。 2、政党就是指人们为了通过（）或其他手段赢得政府权力而组织的政治团体。 3、政治（）主要指政治秩序或体系丧失其合法性的情况。 4、国家的三要素说，认为具有（）、土地、主权者即为国家。 5、古典观以（）为蓝本，把视为人民当家作主的权力，提倡人民参与国家事务的决策和管理。 6、柏拉图在《理想国》一书中明确指出，政治的本质在于（），一个“理想国”具有智慧、勇敢、节制和正义四种美德。 二、选择题(每题至少有一个答案，多选少选均不能得分。每题2分，共20分) 1、根据政治学的一般分析原理，非政府政治体系由()组成。 A.个体公民 B.社团 C.政党 D.市民社会 2、一般来讲，社会监督的途径和方式主要包括() A.舆论监督 B.公民监督 C.政党监督 D.社会团体监督 3、（）精辟地论述道:“一切有权力的人都容易滥用权力，这是万古不易的一条经验。有权力的人们使用权力一直遇有界限的地方才休止。……要防止滥用权力，就必须以权力约束权力。” A.密尔 C.卢梭 B.孟德斯鸠 D.托克维尔 4、（）是政府的灵魂。 A.权威性 B.有机组织性 C.阶级性 D.公共性 5、英国政府一直在()的轮流执掌之下。 A.保守党 B.党 C.党 D.工党 6、的限度包括()。 A.以不产生多数人对少数人的暴政为限度 B.以不干涉政党活动为限度 C.以不干涉社会自主为限度 D.以不侵人“私人领域”为限度 7、马克思主义认为()是奴隶制和封建制国家的典型政体形式。 A.专制君主制 B.立宪君主制 C.二元君主制 D.寡头制 8、()是得以保障和保存的基础性权利。 A.弹劾权 B.选举权 C.罢免权 D.质询权 9、概括而言，政党的功能和作用主要体现在()。 A.实现社会化和政治动员的途径 B.组织政府的手段 C.实现利益聚集和表达的途径 D.形成和培养政治精英的渠道 离散数学图论部分综合练习 一、单项选择题 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=电子科技大学研究生试题《图论及其应用》(参考答案)
《政治学原理》综合练习题及答案
集合论与图论 试题A
图论期末考试整理复习资料
《政治学原理》期末考试复习题及答案
图论试题浙师大
离散数学图论部分经典试题及答案
政治学原理#作业答案
图论模拟题
图论与组合数学期末复习题含答案
12年图论试题
电子科技大学2017年图论期末试卷
(待分)《政治学原理》试题及答案卷号：7413A
(完整word版)Cad2007教程(适合零基础)分析
哈工大年集合论与图论试卷
2016《政治学原理》试题答案
离散数学图论部分经典试题及答案
相关主题
文本预览