图论及其应用第一章答案(电子科大版)
习题一(yangchun)：
4.证明下面两图同构。
证明:作映射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 的连通分支，显然与在中连通；
若与属于的同一连通分支，则与分别在中连通，因此，与在中连通。
18.证明：若,则
.
证明：若为的割边，则=，若为的非割边，则
=，所以，若，则有.
答案(电子科大版)图论及其应用第一章
习题一： ● 。 证明:作映射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 的连通分支，显然与在中连通；
电子科技大学研究生试题《图论及其应用》(参考答案)
电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：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
图论及其应用答案电子科大
图论及其应用答案电子科 大 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）}
专业光信息科学与技术光学与光电子基础实验授课计划表辅导模板
院( 系) 别: 光电工程学院/ 第二学期主讲: 丁松峰 专业: 光信息科学与技术光学与光电子基础实验授课计划表辅导: 丁松峰 班级: B080403 ( 考查) 审查(系、中心): 课程编号: B0402031C 学时: 24 学分: 1.5 批准(院系): 第1页填表日期: 2月 23 日
教材: 光学与光电子基础实验指导书．南京邮电大学光电工程学院( 自编) 参考书: [1] 周炳琨, 高以智等．激光原理( 第四版) ．北京: 国防工业出版社, [2] 石顺祥, 张海兴, 刘劲松．物理光学与应用光学．西安: 西安电子科技大学出版社, [3] 杨之昌, 马秀芳．物理光学实验．上海: 复旦大学出版社, 1993
院( 系) 别: 光电工程学院/ 第二学期主讲: 孙晓芸 专业: 光信息科学与技术光学与光电子基础实验授课计划表辅导: 孙晓芸 班级: B080404 ( 考查) 审查(系、中心): 课程编号: B0402031C 学时: 24 学分: 1.5 批准(院系): 第1页填表日期: 2月 23 日
教材: 光学与光电子基础实验指导书．南京邮电大学光电工程学院( 自编) 参考书: [1] 周炳琨, 高以智等．激光原理( 第四版) ．北京: 国防工业出版社, [2] 石顺祥, 张海兴, 刘劲松．物理光学与应用光学．西安: 西安电子科技大学出版社, [3] 杨之昌, 马秀芳．物理光学实验．上海: 复旦大学出版社, 1993
院( 系) 别: 光电工程学院/ 第二学期主讲: 沈骁 专业: 光信息科学与技术光学与光电子基础实验授课计划表辅导: 沈骁 班级: B080405 ( 考查) 审查(系、中心): 课程编号: B0402031C 学时: 24 学分: 1.5 批准(院系): 第1页填表日期: 2月 23 日
图论及其应用答案电子科大
图论及其应用答案电子科 大 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的块，则两条边的三个不同点在同一条路上。
离散数学试卷及答案(2)
一、填空 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 的关系图为
图论及应用第一章完整作业
习 题 1 1. 证明在n 阶连通图中 （1） 至少有n -1条边。 （2） 如果边数大于n -1，则至少有一条闭通道。 （3） 如恰有n -1条边，则至少有一个奇度点。 证明 (1) 若对?v ∈V(G),有d(v)≥2,则：2m=∑d(v)≥2n ? m ≥n >n-1,矛盾！ 若G 中有1度顶点，对顶点数n 作数学归纳。 当n=2时，G 显然至少有一条边，结论成立。 设当n=k 时，结论成立， 当n=k+1时，设d(v)=1，则G-v 是k 阶连通图，因此至少有k-1条边，所以G 至少有k 条边。 (2) 考虑v 1→v 2→?→v n 的途径，若该途径是一条路，则长为n-1,但图G 的边数大于n-1,因此存在v i ,v j ,使得v i adgv j ,这样，v i →v i+1→?→v j 并上v i v j 构成一条闭通道；若该途径是一条非路，易知，图G 有闭通道。 (3) 若不然，对?v ∈V(G),有d(v)≥2,则：2m=∑d(v)≥2n ? m ≥n >n-1,与已知矛盾！ 2. 设G 是n 阶完全图，试问 （1） 有多少条闭通道？ （2） 包含G 中某边e 的闭通道有多少？ （3） 任意两点间有多少条路？ 答 (1) (n-2)! (2) (n-1)!/2 (3) 1+(n-2)+(n-2)(n-3)+(n-2)(n-3)(n-4)+…+(n -2)…1. 3. 证明图1-27中的两图不同构： 证明 容易观察出两图中的点与边的邻接关系各不相同，因此，两图不同构。 4. 证明图1-28中的两图是同构的 证明 将图1-28的两图顶点标号为如下的(a)与(b)图 图 1-27 图1-28
07年研究生试卷(答案)
电子科技大学研究生试卷 （考试时间： 至 ，共_____小时） 课程名称 图论及其应用 教师 学时 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. 证明在n阶连通图中 （1）至少有n-1条边。 （2）如果边数大于n-1，则至少有一条闭通道。 （3）如恰有n-1条边，则至少有一个奇度点。 证明(1) 若对v V(G),有d(v)2,则：2m=d(v)2n m n n-1,矛盾！ 若G中有1度顶点，对顶点数n作数学归纳。 当n=2时，G显然至少有一条边，结论成立。 设当n=k时，结论成立， 当n=k+1时，设d(v)=1，则G-v是k阶连通图，因此至少有k-1条边，所以G至少有k条边。 (2) 考虑v 1v 2v n的途径，若该途径是一条路，则长为n-1,但图G的边数 大于n-1,因此存在v i,v j,使得v i adgv j,这样，v i v i+1v j并上v i v j构成一条闭通道； 若该途径是一条非路，易知，图G有闭通道。 (3) 若不然，对v V(G),有d(v)2,则：2m=d(v)2n m n n-1,与 已知矛盾！ 2.设G是n阶完全图，试问 （1）有多少条闭通道？ （2）包含G中某边e的闭通道有多少？ （3）任意两点间有多少条路？ 答(1) (n-2)! (2) (n-1)!/2 (3) 1+(n-2)+(n-2)(n-3)+(n-2)(n-3)(n-4)+…+(n-2)…1. 3.证明图1-27中的两图不同构： 图1-27 证明容易观察出两图中的点与边的邻接关系各不相同，因此，两图不同构。 4.证明图1-28中的两图是同构的 图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, 1j 10 ) 由图的同构定义知，图1-27的两个图是同构的。 5. 证明：四个顶点的非同构简单图有11个。 证明 m=0 1 2 3 4 5 6 由于四个顶点的简单图至多6条边，因此上表已经穷举了所有情形，由上表知：四个顶点的非同构简单图有11个。 6. 设G 是具有m 条边的n 阶简单图。证明：m =??? ? ??2n 当且仅当G 是完全图。 证明 必要性 若G 为非完全图，则 v V(G),有d(v) n-1 d(v) n(n-1) 2m n(n-1) m n(n-1)/2=??? ? ??2n , 与已知矛盾！ 充分性 若G 为完全图，则 2m= d(v) =n(n-1) m= ??? ? ??2n 。 7. 证明：（1）m (K l ,n ) = ln ， (a) v 1 v 2 v 3 v 4 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)
离散数学图论部分经典试题及答案
离散数学图论部分综合练习 一、单项选择题 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
离散数学图论部分经典试题及答案
离散数学图论部分综合练习 一、单项选择题 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=
离散数学试卷及答案
一、填空 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.
图论及其应用第三章答案电子科大
习题三： ● 证明：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）}
集合论图论 期中考试试题及答案
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是对称关系. ?
图论及其应用第一章答案(电子科大版)
习题一(yangchun)： 4.证明下面两图同构。 证明:作映射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 的连通分支，显然与在中连通；
物理光学与应用光学复习提纲西安电子科技大学研究生招生信息网
873物理化学复习提纲 一、考试总体要求 1．考试对象 考试对象为具有全国硕士研究生入学考试资格并报考西安电子科技大学理学院应用化学专业的考生。 2．考试总体要求 掌握物理化学中重要的基本概念与基本原理的含义及适用范围；掌握物理化学重要公式及其应用条件。掌握物理化学实验中常用物理量的测量，能正确使用常用物理化学仪器。 二、考试要点 1、气体的pVT 关系 理想气体状态方程、范德华方程、对应状态原理、压缩因子。 2、化学热力学基础 热力学第一、第二定律及其数学表达式；pVT变化、相变化与化学反应过程中W、Q、U、H、S、A与G的计算；熵增原理及三种平衡判据；热力学基本方程和麦克斯韦关系式；克拉贝龙方程及克-克方程。 3、多组分热力学及相平衡 偏摩尔量、化学势的概念；理想气体、理想稀溶液的化学势表达式；逸度、活度的定义；拉乌尔定律和亨利定律；稀溶液依数性的概念 及简单应用。 相律的应用；单组分相图；二组分气－液及凝聚系统相图。 4、化学平衡 等温方程；标准摩尔反应Gibbs函数、标准平衡常数与平衡组成的计算；温度、压力和惰性气体对平衡组成的影响；同时平衡的原则。 5、电化学 电解质溶液电导率、摩尔电导率、活度与活度系数的计算；电导测定的应用；德拜－许克尔极限公式。 原电池电动势与热力学函数的关系，Nernst方程；各类电极的特征和电动势测定的应用；原电池的设计。 电极的极化与超电势的概念；电解时的电极反应。 6. 化学动力学
反应速率、基元反应、反应分子数、反应级数的概念；一、二级反应的速率方程及其应用；阿累尼乌斯公式；对行、平行、连串反应的动力学特征，复杂反应的近似处理法；简单碰撞理论和经典过渡状态理论的基本思想和结果；链反应机理的特点及支链反应与爆炸的关系；光化反应的特征及光化学定律；催化作用的基本特征；多相催化反应； 7. 界面现象与胶体化学 弯曲液面的附加压力与Laplace方程；Kelvin方程与四种亚稳态；润湿与铺展；化学吸附与物理吸附；Langmuir单分子层吸附模型和吸附等温式。 胶体的光学性质、动力性质及电学性质；胶团结构的表示，电解质对溶胶的聚沉作用；乳状液的稳定与破坏。 8. 实验部分 要求考生掌握实验原理、实验装置、实验测定的影响因素。物理化学实验包含下列内容： ①热力学部分量热、相平衡实验； ②电化学部分用电位差计测量电池的电动势，电导测定的应用； ③化学动力学部分测定反应速率常数、反应级数及活化能； ④界面现象与胶体部分表面张力的测定。 三、考试形式与试卷结构 1、考试时间 180分钟。 2、试卷分值 150分。 3、考试方式 闭卷考试。 4、题型结构： 试题类型包括：选择题、填空题、是非判断题、简答题、计算题、分析或绘制相图题、证明题等，每年的试题类型从中选几类。 四、参考书目 1、物理化学（第5版）上、下册，天津大学物理化学教研室编，高教出版社， 2009年 2、物理化学实验，夏海涛编，南京大学出版社，2006年
《物理光学与应用光学》教学大纲
《物理光学与应用光学》教学大纲 一、说明 １、本课程设置目的和任务 《物理光学与应用光学》是光电子技术专业、电子科学与技术及光学工程专业等本科生的专业基础课。本课程以光的电磁理论为理论基础，以物理光学和应用光学为主体内容，着重讲授光在各向同性介质、各向异性介质中的传播规律，光的干涉、衍射、偏振特性，光的吸收、色散、散射等现象，以及几何光学基础知识和光在光学仪器中的传播、成像特性。在内容上，既要保持光学学科的理论完整性，又要突出它在光电子技术中的特色。考虑到激光技术的发展，光在实际应用中的要求，应加强有关光的相干性的内容，特别注意光学原理在光电技术中的应用，并尽量反映最新科技成果。 2、基本要求 （1）物理光学与应用光学是普通物理中的一门课程，应保持普通物理的特点，要重视现象的观察、实验及对实验结果的分析，帮助学生透过现象看到事物的本质，要通过对各种光学现象发生的特殊条件、实验定律的分析和归纳，认识到光是电磁波——本质上遵守电磁场的麦克斯韦方程组。 （2）物理光学与应用光学是基础课，应致力于对物理光学与应用光学运动的基本现象，基本概念和基本规律阐述的正确、严格。对某些难点作较详细的分析和深入的讨论。使学生具有一定的分析和解决问题的能力，并为学习后继课程打下必要的基础。 （3）要使学生了解物理光学与应用光学发展史上某些重大的发现及发现过程中的物理思想和实验方法，提高科学素养，培养学生的辩证唯物主义世界观。 3、学时建议 本课程总学时数：72学时。 二、课程内容与学时分配 第一篇物理光学（48学时） 第一章光的本质（8学时） 1、波是振动的传播。 2、波函数与波动方程。 3、光是电磁波。 4、光电效应与光量子。 5、热辐射与光束的统计性质。 基本要求： （1）让学生理解波是能量的传递，是振动状态的传递。 （2）重点讨论平面波，球面波和近轴求面波的波动方程及其运动状态与状态参量。 （3）强调相位概念在波动中的重要地位及意义。 第二章光波的干涉（8学时） 1、干涉的本质是振动的叠加。 2、分振幅干涉。 3、杨氏干涉仪。 4、两个球面波的干涉。 5、光束时间相干性。 6、光束空间相干性。
图论及其应用 答案电子科大
习题三： ● 证明：是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意及, G 中的路必含. 证明：充分性: 是的割边，故至少含有两个连通分支，设是其中一个连通分支的顶点集，是其余分支的顶点集，对12,u V v V ?∈?∈，因为中的不连通，而在中与连通，所以在每一条路上，中的必含。 必要性：取12,u V v V ∈∈，由假设中所有路均含有边，从而在中不存在从与到的路，这表明不连通，所以e 是割边。 ● 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 ： 是块，任取的一点，一边，在边插入一点，使得成为两条边，由此得到新图，显然的是阶数大于3的块，由定理，中的u,v 位于同一个圈上，于是 中u 与边都位于同一个 圈上。 ： 无环，且任意一点和任意一条边都位于同一个圈上，任取的点u ，边e ，若在上，则三个不同点位于同一个闭路，即位于同一条路，如不在上，由定理，的两点在同一个闭路上，在边插入一个点v ，由此得到新图，显然的是阶数大于3的块，则两条边的三个不同点在同一条路上。 ： 连通，若不是块，则中存在着割点，划分为不同的子集块,,,无环，12,x v y v ∈∈，点在每一条的路上，则与已知矛盾，是块。 ● 7.证明：若v 是简单图G 的一个割点，则v 不是补图的割点。 证明：是单图的割点，则有两个连通分支。现任取, 如果不在的
同一分支中，令是与 处于不同分支的点，那么，与在的补图中连通。若在的同一分支中，则它们在的补图中邻接。所以，若是的割点，则不是补图的割点。 ● 12.对图3——20给出的图G1和G2，求其连通度和边连通度，给 出相应的最小点割和最小边割。 解：()12G κ= 最小点割 {6,8} 1()2G λ= 最小边割{（6,5），（8,5）} ()25G κ= 最小点割{6,7,8,9,10} 2()5G λ= 最小边割{（2,7）…（1,6）} ● 13.设H 是连通图G 的子图，举例说明：有可能k(H)> k(G). 解： 通常. 整个图为，割点左边的图为的的子图， ，则. e H
- 电子科技大学研究生试题图论及其应用参考答案
- 图论及其应用1-3章习题答案(电子科大)
- 电子科技大学研究生试题《图论及其应用》(参考答案)
- 答案(电子科大版)图论及其应用第一章
- 图论及其应用1-3章习题答案(电子科大)(1)
- 图论及其应用第三章答案电子科大
- 电子科技大学研究生试题图论及其应用参考答案完整版
- 图论及其应用答案电子科大
- (完整版)图论及其应用1-3章习题答案(电子科大)
- 图论及其应用答案电子科大
- 电子科大图论 第二次作业(4、5章) 答案
- 图论及其应用 答案电子科大
- 电子科技大学研究生试题图论及其应用参考答案
- 图论及其应用答案电子科大
- 电子科技大学研究生试题《图论及其应用》(参考答案)
- 电子科技大学研究生试题《图论及其应用》 参考答案
- 电子科大图论答案
- 图论及其应用答案电子科大
- 答案(电子科大版)图论及其应用第2章
- 电子科大图论-第二次作业(4、5章)-答案