当前位置：文档之家› 电子科技大学图论第三次作业杨春

电子科技大学图论第三次作业杨春

图论第三次作业第六章习题

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.

8.证明：

(1)由握手定理()2()i d v m n G δ=≥∑和极大可平面图的性质36m n =-，可得

[6()]12G n δ-≥对4n ≥恒成立，又，所以6()3G δ-≤，即()3G δ≥。

(2)由定理5，对简单可平面图都有()5G δ≤，又图G 是3n ≥的简单连通平面

图，所以G 中至少有3个点的度数小于等于5.

(3)由定理5，对简单可平面图都有()5G δ≤，又图G 是4n ≥的简单连通平面

图，所以G 中至少有4个点的度数小于等于5.

17.证明：

利用反证法，假设存在6连通可平面图，设G 是6连通图，则：k(G)≧6 由惠特尼定理可得：δ(G)≧k(G)≧6, ∴m>3n-6,这与G 是简单平面图相矛盾，因此假设不成立，不存在6连通可平面图 19.证明：

假设不存在面f,使得deg(f)≦5,则：2m=≧6φ,

由欧拉公式得：φ=2-n+m≦,于是得：2m≦3n-6,

另一方面，由δ(G)≧3得：2m≧3n>3n-6与上面得到结果相矛盾，所以假设不成立，G至少存在一个面f,使得：deg(f)≦5.

第七章作业

2.证明：

设n=2k+1,∵G是Δ正则单图，且Δ>0,

∴m(G)==>kΔ,由定理5可知χˊ(G)=Δ(G)+1.

28.解：

(1)

又：

=k(k-1)(k-2)2(k-3)+k(k-1)2(k-2)=k(k-1)(k-2)(k2-4k+5)

=k(k-1)(k-2)2(k-3),

所以，原图色多项式为：k(k-1)(k-2)2(k2-4k+5)-k(k-1)(k-2)2(k-3) =k(k-1)(k-2)2(k2-5k+8)

(2)∵

原图与该图同构，又，同构的图具有相同的色多项式，

所以原图色多项式为：k(k-1)(k-2)2(k2-5k+8)。

31.证明：

(1)用归纳法来证明。当m=1时，直接计算P k(G)=k m-k m-1,得k m-1系数为-1，且P k(G)中具有非零系数的k的最小次数为1即G分支数，故m=1时命题成立；

设对于少于m条边的一切n阶单图命题均成立，考虑单图G=(n,m),由递推公式：P k(G)=P k(G-e)-P k(G·e),

由假设可令：P k(G-e)=k n+a1k n-1+…+a n-1k n-1,且a1=-m+1;

P k(G·e)=k n-1+b1k n-2+…+b n-2k n-2,且b1=-m+1,

∴P k(G)=k n+(a1+1)k n-1+(a1+b1)k n-2+…+b n-2k n-2,

∴P k(G)中k n-1的系数a1+1=-m；

P k(G)中具有非零系数的k的最小次数为n-2即为G的分支数。

(2)一个多项式，若是某个图的色多项式，那么也是该图对应的底图的色多项式。故我们仅需对单图来证明。若P k(G)=k4-3k3+3k2是某个单图G的色多项式，则由(1)可知，m(G)=3，从而χ(G)≧2,另一方面，

P1=1，这说明χ(G)≦1,与上面结论相矛盾，故P k不可能是任何单图的色多项式。

32.证明：因为G1和G2中分别有一个唯一的4度顶点：u1与v1.但是它们邻点状况不相同：u1有4个2度邻点，而v1只有两个2度顶点，所以G1与G2不同构。

利用直接计算方法可得：P k(G1)=P k(G2)=10k3+5k4+k5.

33.证明：

(1)当n=1时，P k(K1)=k,命题成立。

若n

P k(G)=P k(G-e)-P k(G·e)=k2(k-1)m-2-k(k-1)m-2=k(k-1)m-1,

故命题成立。

(2)∵P k(G-e)=P k(G)+P k(G·e),P k(G·e)≧0,所以P k(G-e)≧P k(G),另一方面由于G连通，设T是G的生成树，逐次用上述导出的公式将余数T的边从G中除去，于是最后有P k(G)≦P k(T),由(a)，P k(T)=k(k-1)m-1,所以，P k(G)≦k(k-1)m-1.

若连通图G的P k(G)=k(k-1)m-1时，则n=m-1,所以G是一棵树。即当且仅当G是树时等号才成立。

第九章习题

1.解：∵每条边有2种定向方式，所以一个简单图共有2m(G)种定向。

2.证明：不失一般性，设G是连通图。G中奇度顶点个数必然为偶

数个，将偶数个奇度顶点配对，然后在每一对配对顶点间连一条边得到欧拉图G1，在G1中用Fluery算法求出G的一欧拉环游C，然后顺次在C上标上方向，由此得到C的定向图C1.

在C1中，去掉添加的边后，得到G的定向图D，显然：

对v∈V(D),有|d+(v)-d-(v)|≦1.

7.解：

强连通分支：{1}、{2,3,5,6,7}、{4}、{9}、{8}；

单向连通分支：{1,2,3,4,5,6,7}、{8,9}；

弱连通分支：{1,2,3,4,5,6,7,8,9}。

11.证明：设该树有i个分支点，由定理：(m-1)i=t-1得，

对于二元完全树，i=t-1

由树的性质可得，m=(i+t)-1=(t-1+t)-1=2t-2.原式得证。

12.证明：由树的性质，点数为n的树的边数m=n-1,

由11题可知m=2t-2=n-1,∴t=(n+1)/2.

电子科技大学研究生试题《图论及其应用》(参考答案)

电子科技大学研究生试题《图论及其应用》(参考答案) 考试时间：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.通信工程专业专业介绍：本专业培养具有扎实通信系统及通信网理论基础、利用现代电子技术，研究各种信息传输、存储、交换、处理、监测与显示等技术和系统，研究近代通信技术、通信系统、通信网络与各种媒体处理的人才。本专业方向口径宽、适应性强、服务面广。毕业生具有创新能力和工程实践能力，能够从事通信领域和信息系统的研究、设计、制造、分析和运行管理等工作。主修课程：电路分析基础、数字逻辑设计与应用、信号与系统、模拟电路基础、微机原理及应用、通信原理、程控交换原理、计算机通信网、宽带通信网、卫星通信、移动通信、无线网络技术、接入网技术、电磁场与电磁波、数字信号处理（DSP 技术）、ASIC 技术、EDA 技术等。 2.网络工程专业专业介绍：本专业培养具有扎实的现代网络工程理论与现代通信理论基础、计算机应用能力强，研究网络规划工程设计、运行管理和性能分析及网络维护的人才。本专业方向口径宽，适应性强、服2.务面广。毕业生具有创新能力和工程实践能力，能够从事网络的规划和组网规划、网络工程设计和建设、运行维护和管理、安全防护和性能分析等网络工程领域的研究、设计、开发、应用以及管理和教育工作。主修课程：电路分析基础、数字逻辑设计与应用、信号与系统、模拟电路基础、微机原理及应用、通信原理、程控交换原理、电磁场与电磁波、数字信号处理（DSP

技术）、TCP/IP 协议、软件技术基础宽带通信网、网络互联与路由技术、网络设备原理与技术、网络系统工程、网络规划与网络管理等。 3.物联网。。。资料暂缺电子工程学院 1.电子信息工程专业专业介绍：电子信息工程专业是我校最早设立的宽口径电子系统专业，是各发达国家中的热门专业之一，是四川省品牌专业。本专业旨在培养德智体全面发展、知识结构合理、基础扎实、勇于创新、个性突出、具有国际竞争力的优秀的电子信息工程领域内高级技术人才。有以下四个各具特色的培养方向：电子工程方向：培养学生掌握电子电路、信息系统的基本理论和工程技术，掌握信息获取与处理的基本理论及应用的一般方法，具备设计、开发、应用、集成电子设备和信息系统的能力。信息工程方向：培养学生掌握电子电路、信息系统的基本理论和工程技术，掌握信息系统中图像和语音信息的采集、存贮、处理、控制、识别等技术。遥测遥控方向：培养学生掌握电子电路、信息系统的基本理论和工程技术，掌握目标探测与识别技术、制导与控制控制技术等方面的基本理论和基本知识，具备测控系统的分析与综合、工程设计与计算、检测等方面的基本能力。集成电路方向：要求学生掌握电子电路、信息系统的基本理论和工程技术，掌握

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

习题一： ● 。证明:作映射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 的连通分支，显然与在中连通；

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

图论及其应用答案电子科大 Newly compiled on November 23, 2020

离散数学试卷及答案(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 的关系图为