图论习题一精编版
离散数学图论部分综合练习辅导
图论作为离散数学的一部分，主要介绍图论的基本概念、理论与方法。教学内容主要有图的基本概念与结论、图的连通性与连通度、图的矩阵表示、最短路问题、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用等。
本次综合练习主要是复习这一部分的主要概念与计算方法，与集合论一样，也安排了五种类型，有单项选择题、填空题，判断说明题、计算题、证明题。这样的安排也是为了让同学们熟悉期末考试的题型，能够较好地完成这一部分主要内容的学习。下面分别讲解。
一、单项选择题
1．设图G 的邻接矩阵为
???????
?????????010*******
000011100000100 则G 的边数为( )．
A ．5
B ．6
C ．3
D ．4
正确答案：D
上学期的作业中，有的同学选择答案B 。主要是对邻接矩阵的概念理解不到位。我们复习定义：
定义3.3.1 设G =
?????==j
i v v v v a j i j i ij 不相邻或与相邻与01 而当给定的简单图是无向图时，邻接矩阵为对称的．即当结点v i 与v j 相邻时，结点v j 与v i 也相邻，所以连接结点v i 与v j 的一条边在邻接矩阵的第i 行第j 列处和第j 行第i 列处各有一个1，题中给出的邻接矩阵中共有8个1，故有8÷2=4条边。
2．设图G ＝
A ．deg(V )=2∣E ∣
B ．deg(V )=∣E ∣
C ．E v V v 2)deg(=∑∈
D ．
E v V
v =∑∈)deg(
正确答案：C
该题主要是检查大家对握手定理掌握的情况。复习握手定理：
定理3.1.1 设G 是一个图，其结点集合为V ，边集合为E ，则
∑∈=V
v E v ||2)deg(
3．图G 如右图所示，以下说法正确的是 ( ) ． a b
A．{(a, d)}是割边
B．{(a, d)}是边割集
C．{(d, e)}是边割集
D．{(a, d) ,(a, c)}是边割集
正确答案：C
上学期许多同学选择答案A。主要是对割边、边
割集的概念理解不到位。复习割边、边割集的定义：
定义3.2.9设无向图G=
如果答案A正确，即删除边(a, d)后，得到的图是不连通图，但事实上它还是连通的。因此答案A是错误的。
4．设G是连通平面图，有v个结点，e条边，r个面，则r= ( )．
A．e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v＋2
正确答案：A
该题主要是检查大家对平面图的欧拉定理的理解情况。
定理4.3.2（欧拉定理）设连通平面图G的结点数为v，边数为e，面数为r，则下列欧拉公式成立．
v-e+r =2
5．无向图G存在欧拉通路，当且仅当( )．
A．G中所有结点的度数全为偶数
B．G中至多有两个奇数度结点
C．G连通且所有结点的度数全为偶数
D．G连通且至多有两个奇数度结点
正确答案：D
上学期许多同学选择答案C。主要是将题中的“欧拉通路”误认为“欧拉回路”了。其实应该运用定理4.1.1进行选择，才是正确的。复习定义和定理：定义4.1.1给定无孤立结点图G，若存在一条路经过图G的每条边一次且仅一次，则该路称为欧拉路；
若存在一条回路经过图G的每条边一次且仅一次，在该回路称为欧拉回路；
……
定理4.1.1无向图G具有一条欧拉路，当且仅当G是连通的，且有零个或2个奇数度数的结点．
推论一个无向图具有一条欧拉回路，当且仅当该图是连通的，并且它的结点度数都是偶数．
所以，正确答案应该是D．
6．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树．
A ．1m n -+
B ．m n -
C ．1m n ++
D ．1n m -+
正确答案：A
上学期许多同学选择答案D 。主要是把定理5.1.1给出的图T 为树的等价定义之一是图T 连通且e=v -1中的公式用错了．大家只要把m 代入公式e=v -1中的e ，把n 代入公式e=v -1中的v ，可以知道答案A 是正确。
定理5.1.1 给定图T ，则以下关于图T 为树的定义等价．
（1）无回路的连通图．
（2）无回路且e=v-1，其中e 是边数，v 是顶点数．
（3）连通且e=v-1．
（4）无回路，但增加任一新边，得到且仅得到一个回路．
（5）连通，但删去任一边后图便不连通．（v ≥2）
（6）每一对顶点之间有且仅有一条路．（v ≥2）
定理5.1.1的六个等价定义，大家应该熟记的．最主要的是：无向简单图G 是棵树，当且仅当G 连通且边数比结点数少1．
二、填空题
1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 ．
应该填写：15
主要检查大家对握手定理掌握的情况。
定理3.1.1（握手定理） 设G 是一个图，其结点集合为V ，边集合为E ，则
∑∈=V
v E v ||2)deg(
因为图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，即∑∈=?+?+?+?=V
v v 3044332211)deg(，所以边数有152/30==E 。
问：若无向树T 中有8个结点，4度，3度，2度的分
支点各一个，那么T 的树叶数为多少？
2．设给定图G (如右图所示)，则图G 的点割集是
．
应该填写：{f }，{c ，e }
上学期许多同学填错答案主要对点割集的概念理解
不正确。 定义3.2.7 设无向图G =
ο f
上学期许多同学填写的{f，c}，主要是没有完全理解定义3.2.7，因为{f}是{f，c}的真子集，而删除{f}后，图是不连通的。
3．设无向图G＝
应该填写：W(G- V1)
因为具有汉密尔顿回路的图称为汉密尔顿图．而由
定理4.2.1若图G=
4．设有向图D为欧拉图，则图D中每个结点的入度．
应该填写：等于出度
如果大家记住“具有欧拉回路的图称为欧拉图”和定理4.1.2：一个有向图具有单向欧拉回路，当且仅当它是连通的，且每个结点的入度等于出度．大家一定能填写出正确答案的。
5．设完全图K
n 有n个结点(n≥2)，m条边，当时，K
n
中存在欧
拉回路．
应该填写：n为奇数
上学期许多同学填错答案主要对完全图的概念理解不正确。
定义3.1.6简单图G=
由定义可知，完全图K n中的任一结点v到其它结点都有一条边，共有n-1条边，即每个结点的度数是n-1，当n为奇数时，n-1为偶数。
由定理4.1.1的推论可知，应该填写：n为奇数。
6．给定一个序列集合{1，01，10，11，001，000}，若去掉其中的元素，则该序列集合构成前缀码．
应该填写：1
因为在二进制中1是10和11的前缀。而前缀码的定义是（定义5.2.10）：给定一个序列集合，若没有一个序列是另一个序列的前缀，该序列集合称为前缀码．填写该题答案时大家一定要对前缀码的定义理解非常清楚。
问：若把序列集合中的1换成0，应该去掉哪个元素？
三、判断说明题
1．给定两个图G1，G2（如下图所示）：
（1）试判断它们是否为欧拉图、汉密尔顿图？并说明理由．
（2）若是欧拉图，请写出一条欧拉回路．
v1
分析：先复习欧拉图的判别定理和汉密尔顿图的定义：
定理4.1.1的推论：一个无向图具有一条欧拉回路，当且仅当该图是连通的，并且它的结点度数都是偶数．
定义4.2.1：若存在一条回路经过图G 的每个结点一次且仅一次，则该回路称为汉密尔顿回路；具有汉密尔顿回路的图称为汉密尔顿图．
解：（1）图G 1是欧拉图．
因为图G 1中每个结点的度数都是偶数．
图G 2是汉密尔顿图．
因为图G 2存在一条汉密尔顿回路（不惟一）：
a (a ,
b )b (b , e ) e (e , f ) f (f , g ) g (g , d ) d (d ,
c ) c (c , a )a
问题：请大家想一想，为什么图G 1不是汉密尔顿图，图G 2不是欧拉图。
（2）图G 1的欧拉回路为：（不惟一）：
v 1(v 1, v 2) v 2 (v 2, v 3) v 3 (v 3, v 4) v 4 (v 4, v 5)v 5 (v 5, v 2) v 2 (v 2, v 6)v 6 (v 6, v 4) v 4 (v 4, v 1)v 1
（上学期的学生在书写欧拉回路时不规范，大家要按照正确的方法写法。）
2．判别图G (如右图所示)是不是平面图，
并说明理由．
分析：平面图的定义是 定义4.3.1 设G=
如果能把G 的所有结点与边画在平面上，并且
使得任何两条边除端点外没有其他的交点，则
称G 是一个平面图（也称可平面图）．
显然平面图的边与边只在结点处相交．
解：图G 是平面图．
因为只要把结点v 2与v 6的连线(v 2, v 6)拽
到结点v 1的外面，把把结点v 3与v 6的连线
(v 3, v 6)拽到结点v 4, v 5的外面，就得到一个平
面图．
注意：定理4.3.3 设G 是一个有v 个结点e 条边
的连通简单平面图，若v ≥3，则e ≤3v -6．
会用于判断不是平面图。
四、计算题
1．设图G =
v 3 v 4 v 5 v 6 ο ο ο ο ο v 5 v 1 v 2 v 4 v 6 ο v 3 ο ο ο ο ο v 5 v 1 v 2 v 4 v 6 ο v 3
（1）试给出G 的图形表示；
（2）求G 的邻接矩阵；
（3）判断图G 是强连通图、单侧连通图还是弱连通图？
解：（1）图G 是有向图： （2）邻接矩阵如下：
,0001010000000010100000010)(??????
?
?????????=D A （3）图G 是单侧连通图，也是弱连通图．
关于强连通图、单侧连通图还是弱连通图的判断，希望大家掌握图论综合作业单项选择题中的第4题。
2．图G =
（1）画出G 的图形；
（2）写出G 的邻接矩阵；
（3）求出G 权最小的生成树及其权值．
解：（1）因为V ={a , b , c , d , e , f } E ={(a , b ), (a , c ), (a , e ), (b , d ), (b , e ), (c , e ), (d , e ), (d , f ), (e , f )}， 权值依次为5，2，1，2，6，1，9，3及8 所以，G 的图形如右图所示：
（2）分析：定义3.3.1 设G =
?????==.01j i v v v v a j i j i ij 不相邻或与相邻与
邻接矩阵： ????????????????????011000
101111110010
010001011001010110 （3）用避圈法： 第1步：选(a , e )和(c , e )边； 第2步：选(b , d )边；（为什么不选(a , c )？） 第3步：选(d , f )边； 第4步：选(a , b )边． ο ο ο ο ο a 1 a 2 a 3 a 4 a 5 ο ο ο ο ο c a b e d ο f 1 5 2 2
6 1 9 3 8 ο
ο ο ο ο c a b e d ο
f
1 5 2
2 6 1
9 3 8
这样，得到了最小的生成树，如右图中粗线所示．
最小的生成树的权为1+1+5+2+3=12．
上学期作业中的最小的生成树求的不对，主要是没有把握“取权数最小的边，且与前面取到的边不构成圈”，常常是只注意取权数最小的边了，而忽略“不构成圈”的要求。
问：如果结点集是V ={a , b , c , d , e }，边集E ={ (a , b ), (a , c ), (a , e ), (b , d ), (b , e ), (c , e ), (d , e ) }，对应边的权值依次为5，2，1，2，6，1，9，那么会求吗？
3．设有一组权为2,3,5,7,11,13,17,19,23,29,31,试
（1）画出相应的最优二叉树；
（2）计算它们的权值．
解：（1）最优二叉树如右图所示：
方法（Huffman ）：从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中选7,10和11,13为倒数第3层结点，并从上述数列中删去，再添上他们的和数，即17,17,24,19,23,29,31；
……
（2）权值为：2?6+3?6+5?5+7?4+11?4+13?4+17?3+19?3+23?3+29?3+31?2 =12+18+25+28+44+52+51+57+69+87+62=505
讲评：作业中最优二叉树都画对了，但计算总权值时把有些权的层数计算错了，导致总权值计算错误。
问：如果一组权为2,3,6,9,13,15,能否画出最优二叉树？
五、证明题
证明题上学期的学生做的很不好，原因是他们对证明题方法没有掌握，也是对一些概念不清楚所造成的。因此，希望大家认真学习教材和老师讲课中的证明方法，并通过作业逐步掌握做证明题的方法。
1．若无向图G 中只有两个奇数度结点，则这两个结点一定是连通的．
证明：用反证法．设G 中的两个奇数度结点分别为u 和v ．假设u 和v 不连通，即它们之间无任何通路，则G 至少有两个连通分支G 1，G 2，且u 和v 分别属于G 1和G 2，于是G 1和G 2各含有一个奇数度结点．这与定理3.1.2的推论矛盾．因而u 和v 一定是连通的．
2．设G 是一个n 阶无向简单图，n 是大于等于2的奇数．证明图G 与它的补图G 中的奇数度顶点个数相等． ο ο ο ο ο ο ο ο ο 3
2 7 1
3 5 5 11 17 3
4 ο ο 160 29 10 ο ο ο 23 19 42 ο ο 17 ο 24 ο 53 31 ο ο ο 9
5 65
证明：设,G V E =<>，,G V E '=<>．则E '是由n 阶无向完全图n K 的边删去E 所得到的．所以对于任意结点u V ∈，u 在G 和G 中的度数之和等于u 在n K 中的度数．由于n 是大于等于2的奇数，从而n K 的每个结点都是偶数度的
（ 1 (2)n -≥度），于是若u V ∈在G 中是奇数度结点，则它在G 中也是奇数度结点．故图G 与它的补图G 中的奇数度结点个数相等．
3．设连通图G 有k 个奇数度的结点，证明在图G 中至少要添加2
k 条边才能使其成为欧拉图．
证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k 是偶数． 又根据定理4.1.1的推论，图G 是欧拉图的充分必要条件是图G 不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G 的所有结点的度数变为偶数，成为欧拉图． 故最少要加2
k 条边到图G 才能使其成为欧拉图。
集合论与图论 试题A
本试卷满分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 。
2004图论复习题答案
图论复习题答案 一、判断题，对打，错打 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
求解AOE网关键路径例题详解3页word
☆求解AOE网关键路径例题 【例7-1】下表给出了某工程各工序之间的优先关系和各工序所需的时问（其中“一”表示无先驱工序），请完成以下各题： (1) 画出相应的AOE网。 (2) 列出各事件的最早发生时间和最迟发生时间。 (3) 求出关键路径并指明完成该工程所需的最短时间。 【例题分析】 ·试题考核AOE网和关键路径问题。要求熟悉AOE网的概念和如何求关键路径的方法及步骤。 【例题解答】 (1) 根据表的数据，可得AOE网，如图所示。 (2) 所有事件的最早发生时间ve，如下所示：
ve（v1）＝ 0 ve（v2）＝ 3 ve（v3）＝ 2 ve（v4）＝ Max{ ve（v2）+2，ve（v3）+4}＝ 6 ve（v5）＝ ve（v2）＋3 ＝ 6 ve（v6）＝ Max{ ve（v3）+3，ve（v4）+2，ve（v5）+1}＝ 8 所有事件的最迟发生时间vl，如下所示： vl（v6）＝ 8 vl（v5）＝vl（v6）－1＝ 7 vl（v4） ＝vl（v6）－2 ＝ 6 vl（v3）＝ Min{ vl（v4）－4，vl（v6）－3}＝ 2 vl（v2）＝ Min{ vl（v4）－2，vl（v5）－3}＝ 4 vl（v1）＝ Min{ vl（v2）－3，vl（v3）－2}＝ 0 (3) 求所有活动的最早发生时间e、最迟发生时间l和时 间余量l-e。 e（A）＝ve（v1）＝ 0 l（A）＝vl（v2）－3＝ 1 l（A） －e（A）＝ 1 e（B）＝ve（v1）＝ 0 l（B）＝vl（v3）－2＝ 0 l（B） －e（B）＝ 0 e（C）＝ve（v2）＝ 3 l（C）＝vl（v4）－2＝ 4 l（C） －e（C）＝ 1
北大集合论与图论往年考题.pdf
一、用真值表证明德*摩根律（证明其中一条即可）。 二、设A,B,C是集合，试问在什么条件下(A-B)-C=A-(B-C)？给出证明。 三、设A={a,b,c}，问A上有多少种不同的：二元关系？自反关系？对称关系？传递关系？等价关系？偏序关系？良序关系？ 四、用花括号和空集来表示1?2（注意?表示集合的叉乘）. 五、设R是实数集，Q是有理数集，试构造出R-Q与R之间的双射. 1．简单叙述构造的思路； 2．给出双射f：R-Q -> R 或f：R -> R-Q的严格定义。 2008年期末考题： 一、在有向图中，如果存在从顶点u到顶点v的有向通路，则说u可达v；如果顶点u和顶点v互相可达，则说u双向可达v。回答下列问题： 1．顶点集上的可达关系是不是等价关系？为什么？ 2．顶点集上的双向可达关系是不是等价关系？为什么？ 3．对于上述两个关系，如果是等价关系，其等价类的导出子图称为什么？ 二、一棵树有13个顶点，除了3个2度顶点和若干个树叶之外，其余顶点都是5度。 1．求出5度顶点的个数（写出计算过程）； 2．画出所有互不同构的这种树。 三、计算出右图中v1到v4长度为4的通路数（要写出计算过程 的主要步骤），并写出一个最小支配集、一个最大团、一个最小 边覆盖、一个最大匹配。 四、如果一个图中所有顶点度数都为k，则称为k正则图。8阶3 正则简单图一定是平面图吗？一定不是平面图吗？为什么？ 五、证明：如果正则简单图G和补图G都是连通图，则G和G中至少有一个是欧拉图。 六、证明：如果n阶（n≥3）简单图G中，对于任何1≤j
图论期末考试整理复习资料
目录 第一章图的基本概念 (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]。
图论练习题2009(学生练习)
图论练习题 一、基本题 1、设G是由5个顶点构成的完全图，则从G中删去（）边可以得到树。 A．6 B．5 C．8 D．4 2、下面哪几种图不一定是树（）。 A．无回路的连通图 B．有n个结点，n-1条边的连通图 C．对每对结点间都有通路的图 D．连通但删去任意一条边则不连通的图。 3、5阶无向完全图的边数为（）。 A．5 B．10 C．15 D．20 4、把平面分成x个区域，每两个区域都相邻，问x最大为（） A．6 B．4 C．5 D．3 5、设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k+1，则G中度数为k的节点数是（） A．n/2 B．n(n+1) C．nk-2m D．n(k+1)-2m 6、设G=
图论1-3藏习题解答
学号：0441 姓名：张倩 习题1 4．证明图1-28中的两图是同构的 证明：将图1-28的两图顶点标号为如下的(a)与(b)图 作映射f : f(v i )?u i (1? i ? 10) 容易证明，对?v i v j ?E((a)),有f(v i v j )?u i u j ?E((b)) (1? i ? 10, 1?j? 10 ) 由图的同构定义知，图1-27的两个图是同构的。 5.证明：四个顶点的非同构简单图有11个。 证明：设四个顶点中边的个数为m ，则有： m=0: m=1 ： m=2： m=3： (a) v 1 v 2 v 3 v v 5 v 6 v 7 v 8 v 9 v 10 u 1 u 2 u 3 u 4 u 5 u 6 u 7 u 8 u 9 u 10 (b)
m=4： 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 123121,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.证明：若δ≥2，则G 包含圈。 证明 只就连通图证明即可。设V(G)=｛v1,v2,…,vn｝,对于G 中的路v1v2…vk,若vk 与v1邻接，则构成一个圈。若vi1vi2…vin 是一条路，由于?? 2，因此，对vin ，存在点vik 与之邻接，则vik?vinvik 构成一个圈 。 17.证明：若G 不连通，则G 连通。 证明 对)(,_ G V v u ∈?,若u 与v 属于G 的不同连通分支，显然u 与v 在_ G 中连通；若u 与v 属于g 的同一连通分支，设w 为G 的另一个连通分支中的一个顶点，则u 与w ，v 与w 分别在_ G 中连通，因此，u 与v 在_ G 中连通。
集合论与图论试卷2
哈工大 2007 年 秋季学期 本试卷满分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 。
图论与组合数学期末复习题含答案
组合数学部分 第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
哈工大年集合论与图论试卷
-- 本试卷满分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 ?。
集合论与图论SG2017-期中试题-答案(1)
一、（20分）对于任意集合A和B， （1）证明：P(A)?P(B) = P(A?B)；（14分） 对任意的x∈P(A)?P(B)，有x∈P(A)且x∈P(B)。即x?A并且x?B，则x?A?B。所以x∈P(A?B)。故P(A)?P(B)?P(A?B)。（7分）对任意的x∈P(A?B)，有x?A?B，即x?A并且x?B，所以x∈P(A)且x∈P(B)。因此P(A?B)?P(A)?P(B)。（7分）综上所述，P(A)?P(B)=P(A?B) （2）举例说明P(A)?P(B) ≠ P(A?B). （6分） A={1}, B={2}, A?B={1, 2}; P(A)={?, {1}}, P(B)={?, {2}}, P(A)?P(B)= {?, {1}, {2}}, P(A?B)= {?, {1}, {2}, {1, 2}}; 所以P(A)?P(B)≠P(A?B) 二、（20分）设R, S是A上的等价关系且R?S=S?R，证明： R?S是A上的等价关系. 自反性和对称性容易证明，略。（5分） 传递性证明： 对任意a, b, c∈A，如果(a, b)∈R?S, (b, c)∈R?S，要证明(a, c)∈R?S。 因为R?S=S?R，则有(b, c)∈S?R，即存在e, f∈A，使(a, e)∈R，(e, b)∈S，(b, f)∈S，(f, c)∈R。 因为S是传递的，(e, b)∈S，(b, f)∈S，所以(e, f)∈S；因为(a, e)∈R，所以(a, f)∈R?S；R?S是对称的，则(f, a)∈R?S；因为R是对称的，(f, c)∈R，则(c, f)∈R。因为(f, a)∈R?S，则存在g∈A，使得(f, g)∈R，(g, a)∈S；因为R是传递的，
习题参考解答(图论部分)
习题十 1. 设G 是一个(n ，m)简单图。证明：，等号成立当且仅当G 是完全图。 证明：（1）先证结论： 因为G 是简单图，所以G 的结点度上限 max(d(v)) ≤ n-1, G 图的总点度上限为 max(Σ(d(v)) ≤ n ﹒max(d(v)) ≤ n(n-1) 。根据握手定理，G 图边的上限为 max(m) ≤ n(n-1)/2,所以。 （2） =〉G 是完全图 因为G 具有上限边数，假设有结点的点度小于n-1,那么G 的总度数就小于上限值，边数就小于上限值，与条件矛盾。所以，G 的每个结点的点度都为n-1，G 为完全图。 G 是完全图 =〉 因为G 是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G 的边数 。■ 2. 设G 是一个（n ，n +1）的无向图，证明G 中存在顶点u ，d （u ）≥3。 证明：反证法，假设,则G 的总点度上限为max(Σ(d(u)) ≤2 n ，根据握手定理，图边的上限为max(m) ≤ 2n/2=n 。与题设m = n+1，矛盾。因此，G 中存在顶点u ，d （u ）≥3。■ 3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）； （2）（6，3，3，2，2） （3）（4，4，2，2，4）； （4）（7，6，8，3，9，5） 解：除序列（1）不是图序列外，其余的都是图序列。因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。 可以按如下方法构造满足要求的图：序列中每个数字ai 对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。最后，将奇数序列对应的点两两一组，添加连线即可。下面以（2）为例说明： (6 , 3, 3, 2, 2 ) 对应图G 的点集合V= { v 1,v 2,v 3,v 4,v 5} 每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1)
集合论与图论习题册
集合论与图论习题册 软件基础教研室 刘峰 2015.02
第一章 集合及其运算 8P 习题 1. 写出方程2210x x ++=的根所构成的集合。 2.下列命题中哪些是真的，哪些为假 a)对每个集A ，A φ∈； b)对每个集A ，A φ?； c)对每个集A ，{}A A ∈； d)对每个集A ，A A ∈； e)对每个集A ，A A ?； f)对每个集A ，{}A A ?； g)对每个集A ，2A A ∈； h)对每个集A ，2A A ?； i)对每个集A ，{}2A A ?； j)对每个集A ，{}2A A ∈； k)对每个集A ，2A φ∈； l)对每个集A ，2A φ?； m)对每个集A ，{}A A =； n) {}φφ=； o){}φ中没有任何元素； p)若A B ?，则22A B ? q)对任何集A ，{|}A x x A =∈； r)对任何集A ，{|}{|}x x A y y A ∈=∈； s)对任何集A ，{|}y A y x x A ∈?∈∈； t)对任何集A ，{|}{|}x x A A A A ∈≠∈。 答案： 3.设有n 个集合12,,,n A A A 且121n A A A A ???? ，试证：12n A A A === 。 4.设{,{}}S φφ=，试求2S ？ 5.设S 恰有n 个元素，证明2S 有2n 个元素。
16P 习题 6.设A 、B 是集合，证明:(\)()\A B B A B B B φ=?= 。 7.设A 、B 是集合，试证A B A B φ=?=?。 9.设A ，B ，C 为集合，证明：\()(\)\A B C A B C = 。 10.设A ，B ，C 为集合，证明：()\(\)(\)A B C A C B C = 。 11.设A ，B ，C 为集合，证明：()\(\)(\)A B C A C B C = 。 12.设A ，B ，C 都是集合，若A B A C = 且A B B C = ，试证B=C 。 15.下列命题是否成立？说明理由（举例）。 (1)(\)\(\)A B C A B C = ；(2)(\)()\A B C A B C = ； (3)\()()\A B C A B B = 。（答案：都不正确）
图论习题参考答案
二、应用题 题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)={, ,
集合论与图论
《集合论与图论》课程示范性教学设计 1 本课程教学方法 （一）教学方法 在这里，仅总结一下我的教学方法，不细展开，因此不涉及专业术语和与专业有关的例子。以下仅是一些指导思想： （1 ）启发式、由浅入深、从直观到抽象。要用些生动的例子帮助学生理解抽象概念的含义，但要做到生动而有趣又不失概念的准确性和推理的严格性，使学生易于接受，又了解直观背景。 （2 ）突出基本思想及方法，强调规律性，提高学生的抽象能力。要从哲学的高度强调概念是第一位的，引导学生思考问题时必须清楚理解所涉及的概念，使问题有一个明确的提法，引导学生掌握从问题到建立数学模型这一抽象过程的方法。 （3 ）利用集合论某些概念和理论与方法总结已学过的知识（如微积分、线性代数）找出本质的规律或主线，使学生认识事物内部的深刻规律。其次，随时指出在后继课如何应用这些知识、在科技论文中将怎样出现这些知识的应用。这不仅提高了学习的积极性，也使学生增强了学习的目的性。 （4 ）只要有可能就要以建立数学模型组织教学，讲习题也不例外。这样，能使学生加深印象—任何时候都要抓住事物的本质与事物之间的联系。 （5 ）鼓励学生多问为什么，为什么会是这样子而不是那个样子。不是教会学生怎样去使用工具、去模仿或复制，而是要教会学生独立思考，发现问题，提出问题和解决问题的思考，否则思维会退化。 （5 ）适当地提出一些未解决的问题。尚无答案的问题是摆在我们及学生面前的有无限价值的东西，因为支持大学的最高准则是探究未知领域。事实上，在每年教此课时，提一些问题确实有学生在思考。 （6 ）注意每个学科（内部）的美。如果某部分很丑或太复杂，人们倾向于认为是不清楚的和暂时的，它没有真正反映客观规律，因为我们相信，越接近终极真理，我们的解释中的不自然的东西就越少。科学是以越来越完美、有力的理论向终极真理发展的。 （二）关于素质教育、培养创新精神的人才的思考 素质教育应该是各类教育的核心，而培养创新人才则是高等教育的任务（见高等教育法，第五条）。在这里讨论这个题目不太合适，因为题太大。其实，在（五）中就本课的特点贯穿了素质教育和培养创新人才的思想。以下只扼要地总结一下。 1 ）教会学生如何进行逻辑推理，如何进行正确地思维，如何在纷繁的事物中抓住主要的联
电子科技大学2017年图论期末试卷
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 的度序列，该度序列是一个图序列吗？。
集合论图论 期中考试试题及答案
08信安专业离散数学期中考试试题 1.设A, B, C, D为4个集合. 已知A?B且C?D.证明: A∪C?B∪D; A∩C?B∩D . (15分) 2.化简以下公式: A∪((B―A)―B) (10分) 3.设R是非空集合A上的二元关系.证明:R∪R-1是包含R的 最小的对称的二元关系. (15分) 4.设A={1,2,…,20},R={
期中考试试题解答 1.证明: ?x, x∈A∪C x∈A∩C ?x∈A∨x∈C ?x∈A∧x∈C ?x∈B∨x∈D (A?B,C?D) ?x∈B∧x∈D (A?B,C?D) ?x∈B∪D ?x∈B∩D ∴A∪C?B∪D ∴A∩C?B∩D 2.解: A∪((B―A)―B) =A∪((B∩∽A)∩∽B) =A∪(∽A∩(B∩∽B)) =A∪(∽A∩φ) =A∪ф =A . 3.证明:首先证R∪R-1是对称关系. ?