当前位置：文档库 › 图论王树禾答案

图论王树禾答案

图论第一次作业

By byh

|E(G)|,2|E(G)|2G υυ??≤ ???

?? ???

1.1 举出两个可以化成图论模型的实际问题

略

1.2 证明其中是单图

证明：（思路）根据单图无环无重边的特点，所以最大的情形为任意两个顶点间有一条边相连，即极

端情况为。

?1.4 画出不同构的一切四顶单图

?0条边：1条边：

?2条边：3条边：

?4条边：5条边：?6条边：

1.10G?H当且仅当存在可逆映射θ:V G→V H，使得uv∈E G?θuθv∈E H，其中G和H是单图。（证明充分性和必要性）

?必要性

?若G?H，由定义可得，存在可逆映射θ:V G→V Hφ:E G→E(H)当且仅当ψ

G e=uv时，ψHφe=θuθ(v)，所以uv∈E G?

θuθv∈E H

?充分性

?定义?:E G→E(H)，使得uv∈E G和θuθv∈E(H)一一对应，于是?可逆，且ψ

e=uv的充要条件是ψHφe=θuθv，得G?H

1.12求证(a)?K m

,n =mn，(b)G是完全二分图，则?G≤1

v G2

?(a)对于K m

,n ，将顶集分为X和Y，使得X∪Y=V K

m,n，

X∩Y=

?，X=m，Y=n，对于X中的每一顶点，都和Y中所有顶点相连，所以?K

m,n

=mn

?(b)设G的顶划分为X,Y，X=m,Y=v?m，则?G≤

??K m

,v-m =v?m m≤v2

?证明：

?(a)第一个序列考虑度数7,第二个序列考虑6,6,1

?(b)将顶点v分成两部分v’和v’’

?v’ = {v|v= v i, 1≤ i≤ k},

?v’’ = {v|v= v i, k< i≤ n}

?以v’点为顶的原图的导出子图度数之和小于

?然后考虑剩下的点贡献给这k个点的度数之和最大可能为

?1.37：证明无环图G 含二分生成子图H ，使得d H v ≥1

2d G v 对每个v ∈V(G)成立。

?证明：

?任取X, Y 满足X U Y = V(G)，X ∩ Y = ?，且令X,Y 中的顶两两不相邻，所得的图是H 且是二分子图，令H 是G 边数最多的二分生成子图，若存在v ?V(G)，

使得d H (v) < d G (v)，不妨设v ?X ，则将v 所连的边取消，换成d G (v) -d H (v) 条边，且将v 加入Y 中，于是H 的边数增加了d G (v) -2d H (v)条，与H 边数最多矛盾，故原命题成立。21

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

电子科技大学研究生试题《图论及其应用》(参考答案) 考试时间：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

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