文档库 最新最全的文档下载
当前位置:文档库 › 图论及其应用答案电子科大

图论及其应用答案电子科大

图论及其应用答案电子科大
图论及其应用答案电子科大

习题三:

● 证明: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)}

()25G κ= 最小点割{6,7,8,9,10}

2()5G λ= 最小边割{(2,7)…(1,6)}

13.设H 是连通图G 的子图,举例说明:有可能k(H)>

k(G).

解:

通常k (H )

整个图为G ,割点e 左边的图H 为G 的的子图,k (H )=3 k (G )=1,则k (H )>k(G). e

H

答案(电子科大版)图论及其应用第一章

习题一: ● 。 证明:作映射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

西安电子科技大学人工智能试题

1.(该题目硕士统招生做)请用框架法和语义网络法表示下列事件。(10分) 2015年2月20日上午11点40分,广东省深圳市光明新区柳溪工业园附近发生山体滑坡,经初步核查,此次滑坡事故共造成22栋厂房被掩埋,涉及公司15家,截至目前已安全撤离900人,仍有22人失联。 答:框架表示法(5分):(给分要点:确定框架名和框架槽,根据报道给出的相关数据填充,主要内容正确即可给分,不必与参考答案完全一致) <山体滑坡> 时间:2015年2月20日上午11点40分 地点:广东省深圳市光明新区柳溪工业园附近 掩埋厂房:22栋 涉及公司数目:15家 安全撤离人数:900人 失联人数:22人 语义网络表示法(5分):(给分要点:确定语义网络的节点及其连接关系,根据报道内容进行填充,主要内容正确即可给分,不必与参考答案完全一致) 1. (该题目全日制专业学位硕士做)请用一种合适的知识表示方法来表示下面知识。(10分) How Old Are YOU是微软推出的一款测年龄应用,该应用架设在微软服务平台Azure上,该平台具有机器学习的开发接口,第三方开发者可以利用相关的接口和技术,分析人脸照片。

(给分要点:采用合适的知识表示方法,正确即可给分,不必与参考答案完全一致) 答: 类属(继承):<应用程序> 用途:测年龄 开发者:微软 服务平台: 开发接口:机器学习 用途:分析人脸照片 2.(该题目硕士统招生做)请用归结反演的方法求解下述问题。(15分) 已知:张和李是同班同学,如果x和y是同班同学,则x的教室也是y的教室,现在张在302教室上课。 问:现在李在哪个教室上课? 解:第一步:定义谓词;(谓词不一定与参考答案完全相同,只要正确表示即可给分)(3分)C(x, y) x和y是同班同学; At(x, u) x在u教室上课。 第二步:根据定义的谓词写出上述知识的谓词表示,并化成子句集;(6分) 把已知前提用谓词公式表示如下: C(zhang, li) (?x) (?y) (?u) (C(x, y)∧At(x, u)→At(y,u)) At(zhang, 302) 把目标的谓词公式表示如下: (?v)At(li, v) 把上述公式化为子句集: (1) C(zhang, li) (2) ﹁C(x, y)∨﹁At(x, u)∨At(y, u) (3) At(zhang, 302) 把目标的否定化成子句式: (4) ﹁At(li,v) ∨Answer(v) 第三步:使用归结原理对子句集进行归结;(6分)(注意:具体的归结顺序不一定和参考答案完全一致,只要归结过程正确,最后得到的答案正确即可给分)

图论及其应用答案电子科大

图论及其应用答案电子科 大 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)}

西安电子科技大学单片机考试试卷

西安电子科技大学本科课程考试试卷2008—2009学年第一学期《单片机原理与接口技术》 课程A卷 专业年级:07电信命题教师:郭文川审题教师: 考生班级:学号:考生姓名: 一、填空题:(每空1分,共20分) 1、MCS—5l单片机的最大程序寻址空间是64 KB,该空间的地址范围从0000H 至0FFFFH,系统上电及复位后,程序入口地址为0000H。 2、若由程序设定PSW中的RS1、RS0=01,则工作寄存器R0~R7的直接地址为08H~0FH。 3、MCS-51单片机的I/O端口采用统一编址方式。、 4、一个8位D/A转换器其分辨率为_ 1/256 ,若该8位D/A转换器的基准电压为5V, 则数字量100对应得模拟量为 1.953V(5*100/256V)。 5、单片机系统中经常采用的地址译码技术包括线选法和译码法。 6、INTEL 8051 CPU 是8 位的单片机,其内部有4 KB的ROM。 7、指出下列各指令中源操作数的寻址方式。 (1)MOVC A,@A+DPTR (变址寻址) (2)XCH A,@R0;(寄存器间接寻址) (3)MOV C,P1.0 (位直接寻址) (4)JC LOOP (相对寻址) 8、判断下列各条指令的书写格式是否有错,并指出原因。 (1)MUL R0,R1 (错,乘法指令用A×B ) (2)MOV A, @R7 (错,@R7非法)

(3)MOV A, #3000H (错,累加器A为8位存储器) (4)MOV R1, C (错,C为进位位不能送给寄存器R1) 二、选择题:(每题1分,共10分) 1.当MCS-51单片机接有外部存储器时,P2口可作为 D 。 A.数据输入口 B. 数据的输出口 C.准双向输入/输出口D.高8位地址线 2.单片机的并行接口中,作为数据线使用的并行口是 A 。 A.P0 B. P1 C. P2 D. P3 3.MCS—5l单片机的堆栈区是设置在 C 中。 A.片内ROM区B.片外ROM区 C.片内RAM区 D. 片外RAM区 4.片内RAM的20H~2FH为位寻址区,所包含的位地址是。 A.00H~20H B. 00H~7FH C.20H~2FH D.00H~FFH 5.在寄存器间接寻址方式中,间址寄存器中存放的数据是。 A.参与操作的数据B.操作数的地址值 C.程序的转换地址D.指令的操作码 6.当需要从MCS-51单片机程序存储器取数据时,采用的指令为。 A. MOV A, @R1 B.MOVC A, @A + DPTR C. MOVX A, @ R0 D.MOVX A, @ DPTR 7. 能够用紫外光擦除ROM中程序的只读存储器称为。 A.掩膜ROM B.PROM C.EPROM D.EEPROM 8. 在片外扩展一片2716程序存储器芯片要地址线。 A.8根 B.13根 C.11根 D.20根 9. 定时器/计数器工作方式1是。 A. 8位计数器结构 B. 2个8位计数器结构 C. 13位计数结构 D. 16位计数结构 10.T0中断的中断入口地址为。 A. 0003H B. 000BH C. 0013H D. 001BH 三、分析程序,写出结果(每空3分,共18分) 1、已知(A)=83H,(R0)=17H,(17H)=34H,执行下列程序段后(A)= 0CBH 。

图论及其应用答案电子科大

图论及其应用答案电子科 大 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。

西安电子科技大学试卷资料

西安电子科技大学试卷 考试时间120 分钟试卷编号参考答案 班级学号姓名任课老师姓名 请按下述要求正确答题: 1. 在试卷指定位置上正确写入你的班级、学号、姓名和任课老师姓名。 2.全部试卷共 11 页。试卷必须交回,否则以零分计。 3.试题解答必须写在试卷上,若试卷上写不下可以写在试卷的背面,写在草稿纸上的解答一律无效。 4.本试卷的试题共有五道大题,需要全部解答。 5.解答前务必阅读清楚题意,及解答要求,否则导致不能正确评分概由自己负责。 一、单项选择题(每小题1分,共10分) 1.访管指令所引起的中断属于( C )中断。 A.外中断B.I/O中断C.软中断D.程序中断2.资源静态分配法破坏了死锁产生的(B)条件来预防死锁的发生。 A.互斥控制B.保持和等待 C.不可剥夺控制D.循环等待 3.虚拟存储的基础是程序局部性理论,它的基本含义是( B )。 A.代码的顺序执行B.程序执行时对内存访问的不均匀性 C.变量的连续访问D.指令的局部性 4.关于SPOOLING系统(D)的描述是错误的。 A.不需要独占设备 B.加快了作业执行的速度 C.使独占设备变成了共享设备

D.利用了处理器与通道并行工作的能力 5.设系统中有m个同类资源数,n为系统中的并发进程数,当n个进程共享m个互斥资源时,每个进程的最大需求数是w,试问下列情况下系统会死锁的是(D)。 A.m=4,n=3,w=2 B.m=2,n=2,w=1 C.m=5,n=2,w=3 D.m=4,n=3,w=3 6.文件系统中实现按名存取的功能是通过查找(B)来实现的。 A.磁盘空间B.文件目录C.磁盘控制器D.位示图7.下面的叙述中,(D)不是设备管理中引入缓冲机制的主要原因。 A.缓和CPU和I/O设备间的速度不匹配问题 B.减少对CPU的中断频率和放宽对CPU响应时间的限制 C.提高CPU和I/O设备间的并行性 D.节省系统内存 8.下列操作系统强调交互性的系统是(B)。 A.批处理系统B.分时系统C.实时系统D.网络操作系统 9.响应比高者优先作业调度算法是通过计算时间和(D)来实现的。 A.输入时间B.完成时间C.周转时间D.等待时间10.在可变分区管理方案中,若采用“最佳适应”分配算法,通常将空闲区按(A )排列。 A.容量递增B.容量递减C.地址递增D.地址递减二、填空题(每空格1分,共15分) 1.把作业装入内存时完成地址变换的方式称静态地址再定位,而在作业执行期间(访问到指令或数据)才进行地址变换的方式称为动态地址再定位。 2.死锁产生的四个必要条件是互斥执行、保持和等待、不可剥夺和循环等待。

图论及应用第一章完整作业

习题 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 =,则下列结论成立的是 ( ). A .deg(V )=2∣E ∣ B .deg(V )=∣E ∣ C .E v V v 2)deg(=∑∈ D .E v V v =∑∈)deg( 4.图G 如图一所示,以下说法正确的是 ( ) . A .{(a , d )}是割边 B .{(a , d )}是边割集 C .{(d , e )}是边割集 D .{(a, d ) ,(a, c )}是边割集 5.如图二所示,以下说法正确的是 ( ). A .e 是割点 B .{a, e }是点割集 C .{b , e }是点割集 D .{d }是点割集 6.如图三所示,以下说法正确的是 ( ) . A .{(a, e )}是割边 B .{(a, e )}是边割集 C .{(a, e ) ,(b, c )}是边割集 D .{(d , e )}是边割集 ο ο ο ο ο c a b e d ο f 图一 图二

图三 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 =,则下列结论成立的就是 ( ). A.deg(V )=2∣E ∣ B.deg(V )=∣E ∣ C.E v V v 2)deg(=∑∈ D.E v V v =∑∈)deg( 4.图G 如图一所示,以下说法正确的就是 ( ) . A.{(a , d )}就是割边 B.{(a , d )}就是边割集 C.{(d , e )}就是边割集 D.{(a, d ) ,(a, c )}就是边割集 5.如图二所示,以下说法正确的就是 ( ). A.e 就是割点 B.{a, e }就是点割集 C.{b , e }就是点割集 D.{d }就是点割集 6.如图三所示,以下说法正确的就是 ( ) . A.{(a, e )}就是割边 B.{(a, e )}就是边割集 C.{(a, e ) ,(b, c )}就是边割集 D.{(d , e )}就是边割集 ο ο ο ο ο c a b e d ο f 图一 图二

图三 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=中具有一条汉密尔顿回路, 则对于结点集V 的每个非空子集S ,在G 中删除S 中的所有结点得到的连通分支数为W ,则S 中结点 数|S|与W 满足的关系式为 . 4.无向图G 存在欧拉回路,当且仅当G 连通 且 . 5.设有向图D 为欧拉图,则图D 中每个结点的入度 . ο ο ο ο ο c a b e d ο f 图四

离散数学试卷及答案

一、填空 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.

西安电子科技大学电院微机原理试题2.

西安电子科技大学微机原理试题 姓名学号总分 一.填空题(每空1分,共30分 115的8位二进制补码为00001111B ,-15的8位二进制补码为11110001B 。2某8位二进制补码为80H,其十进制表示为-128 。 3字符B的ASCII码为42H ,字符0的ASCII码为30H 。 48086CPU总线按功能可分为数据总线,地址总线和控制总线。 58086CPU数据总线包含16 条数据线,最多可寻址的存储器容量为1MB 。 6CPU内部用于计算的部分为C ,用于保存下一条要执行的指令地址的为B 。 A 程序状态字 B 程序计数器 C ALU D 工作寄存器 7经常用作循环次数的寄存器是C ,用于I/O端口寻址的寄存器是D 。 A AX B BX C CX D DX 8指令MOV CX, 1000的结果是CH= 03H 。 9将0D787H和4321H相加后,标志位CF= 1 ,SF= 0 ,ZF= 0 , OF= 0 ,AF= 0 ,PF= 0 。 10寄存器SI中能够表示的最大有符号数为32767 ,最小有符号数为-32768 。

11设(DS=4000H,(BX=0100H,(DI=0002H,(4002=0A0AH,(40100=1234H,(40102 =5678H,求以下指令分别执行后AX寄存器的值。 MOV AX , [2] (AX= 0A0AH 。 MOV AX , [BX] (AX= 1234H 。 MOV AX , [BX][DI] (AX= 5678H 。 MOV AX , 1[BX] (AX= 7812H 。 12用一条指令将AX寄存器低四位清零,其余位不变:。 13用一条指令将AX寄存器高四位取反,其余位不变:。 14用一条指令将AX高8位与低8位交换:。 15用一条指令将AL中的大写字母变成相应的小写:。 二.判断题(每题1分,共10分 以下语句是语法正确的打√,语法错误打×,其中TABLE和TAB为两个字节类型的变量。 1MOV DS , 1000H × 2MOV DS , TABLE √ 3MOV [1200H] , [1300H] × 4ADD AX , BX , CX × 5XCHG AL , CL √ 6CALL AL ×

图论及其应用第三章答案电子科大

习题三: ● 证明: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={|x,y∈A∧x≡y(mod 5)}.证 明:R为A上的等价关系. 并求商集A/R. (15分) 5.给出下列偏序集的哈斯图,并指出A的最大元,最小元,极 大元和极小元. A={a,b,c,d,e},?A= I A∪{,, ,,,,} (15分) 6.设g:A→B, f:B→C.已知g f是单射且g是满射,证明:f 是单射. (10分) 7.设S={0,1}A, 其中A={a1,a2,…,a n}.证明:P(A)与S等势. (10分) 8.证明:任何一组人中都存在两个人,他们在组内认识的人 数恰好相等(假设,若a认识b,则a与b互相认识). (10分)

期中考试试题解答 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是对称关系. ?, ∈R∪R-1 ?∈R∨∈R-1 ?∈R-1∨∈R ?∈R-1∪R ?∈R∪R-1

相关文档
相关文档 最新文档