当前位置：文档之家 › 王博图论第一次作业(电子科技大学)

王博图论第一次作业(电子科技大学)

  • 格式：doc
  • 大小：152.20 KB
  • 文档页数：3

习题1
1.

证明 （1）若对)(GVv，有d(v)≥2,则：nmnvdm1)(2＞n-1，矛盾！
若G中有1度顶点，对顶点数n作数学归纳。
当n=2时，G显然至少有一条边，结论成立。
设当n=k+1,设d(v)=1，则G-v是k介连通图，因此至少有k-1条边，所以G至少
有k条边。
（2）考虑v1→v2→...→vn的途径，若该途径是一条路，则长为n-1，但图G的边数
大于n-1，因此存在vi,vj,使得vi adj vj,这样，vi→vi+1→...→vj并上vivj构成一条闭通道;若
该途径是一条非路，易知，图G有闭通道。

（3）若不然，对)(GVv,有d(v)≥2，则：2m=∑d(v)≥2nm≥n＞n-1,与已知
矛盾！
11.
证明：由于7个顶点的简单图的最大度不会超过6，因此序列（7,6,5,4,3,3,2）不是图序列;
(6,6,5,4,3,3,1)是图序列（5,4,3,2,2,0）是图序列，然（5,4,3,2,2,0）不是图序列，所以
（6,6,5,4,3,3,1）不是图序列。
12.
证明 只就连通图证明即可。设V(G)=｛v1,v2,…,vn｝,对于G中的路v1v2…vk,若vk与v1邻接，
则构成一个圈。若vi1vi2…vin是一条路，由于 2，因此，对vin，存在点vik与之邻接，则
vikvinvik构成一个圈 。
17.

证明 对)(,_GVvu,若u与v属于G的不同连通分支，显然u与v在_G中连通；若u与
v属于g的同一连通分支，设w为G的另一个连通分支中的一个顶点，则u与w，v与w

分别在_G中连通，因此，u与v在_G中连通。

习题2
2.
证明：假设T是一颗恰有两个1度顶点的树，两个1度顶点分别为u,v，则树T种至少包含
两个顶点，由于树中无圈存在，则除两个1度顶点外其余定点度必定为2，故顶点u到顶点
v有且仅有一条通路，所以，每棵恰有两个1度顶点的树均为路。
9.
证明：证明：由于错误！未找到引用源。是连通非平凡的且每个顶点度数为偶数，所以错误！
未找到引用源。中至少存在圈错误！未找到引用源。,从错误！未找到引用源。中去掉错误！
未找到引用源。中的边，得到错误！未找到引用源。的生成子图错误！未找到引用源。,若
错误！未找到引用源。没有边，则错误！未找到引用源。的边集合能划分为圈。否则，错
误！未找到引用源。的每个度数均为偶数的连通图，反复这样抽取，错误！未找到引用源。
最终划分为若干圈。
设错误！未找到引用源。是错误！未找到引用源。的边划分中的一个圈。若错误！未
找到引用源。仅由此圈组成，则错误！未找到引用源。显然是闭迹。否则，由于错误！未
找到引用源。连通，所以，必然存有公共顶点。于是，错误！未找到引用源。是一条含有
错误！未找到引用源。与错误！未找到引用源。的边的迹，如此拼接下去，得到包含错误！
未找到引用源。的所有边的一条闭迹.
16.

解：1、不能，由Kruskal算法得到的任何生成树一定是最小生成树。
2、能

习题3
3.

证明：
错误！未找到引用源。是块，任取错误！未找到引用源。的一点错误！未找到引用源。，
一边错误！未找到引用源。，在错误！未找到引用源。边插入一点错误！未找到引用源。，
使得错误！未找到引用源。成为两条边，由此得到新图错误！未找到引用源。，显然错误！
未找到引用源。的是阶数大于3的块，由定理，错误！未找到引用源。中的u,v位于同一个
圈上，于是错误！未找到引用源。中u与边错误！未找到引用源。都位于同一个圈上。

错误！未找到引用源。上，则三个错误！未找到引用源。无环，且任意一点和任意一条边
都位于同一个圈上，任取错误！未找到引用源。的点u，边e，若错误！未找到引用源。在
不同点位于同一个闭路，即位于同一条路，如错误！未找到引用源。不在错误！未找到引
用源。上，由定理，错误！未找到引用源。的两点在同一个闭路上，在错误！未找到引用
源。边插入一个点v，由此得到新图错误！未找到引用源。，显然错误！未找到引用源。的
是阶数大于3的块，则两条边的三个不同点在同一条路上。

错误！未找到引用源。连通，若错误！未找到引用源。不是块，则错误！未找到引用源。
中存在着割点错误！未找到引用源。，划分为不同的子集块错误！未找到引用源。,错误！

未找到引用源。,错误！未找到引用源。,错误！未找到引用源。无环，12,xvyv，点错
误！未找到引用源。在每一条错误！未找到引用源。的路上，则与已知矛盾，错误！未找
到引用源。是块。
7.
证明：错误！未找到引用源。是单图错误！未找到引用源。的割点，则错误！未找到引用
源。有两个连通分支。现任取错误！未找到引用源。, 如果错误！未找到引用源。不在错误！
未找到引用源。的同一分支中，令错误！未找到引用源。是与错误！未找到引用源。处于
不同分支的点，那么，错误！未找到引用源。与错误！未找到引用源。在错误！未找到引
用源。的补图中连通。若错误！未找到引用源。在错误！未找到引用源。的同一分支中，
则它们在错误！未找到引用源。的补图中邻接。所以，若错误！未找到引用源。是错误！
未找到引用源。的割点，则错误！未找到引用源。不是补图的割点。
12.
解：12G 最小点割 {6,8}

1
()2G
最小边割{（6,5），（8,5）}


2
5G
最小点割{6,7,8,9,10}

2
()5G
最小边割{（2,7）…（1,6）}

13.
解：
通常K(H)＜K(G)

整个图为错误！未找到引用源。，割点错误！未找到引用源。左边的图错误！未找到引用
源。为错误！未找到引用源。的的子图，错误！未找到引用源。 错误！未找到引用源。，
则错误！未找到引用源。。

合集下载

图论第二次作业

图论第二次作业

图论第二次作业一、 第四章4.3（1）画一个有Euler 闭迹和Hamilton 圈的图；（2）画一个有Euler 闭迹但没有Hamilton 圈的图；（3）画一个有Hamilton 圈但没有Euler 闭迹的图；（4）画一个既没有Euler 闭迹也没有Hamilton 圈的图；解：（1）一个有Euler 闭迹和Hamilton 圈的图形如下：（2）一个有Euler 闭迹但没有Hamilton 圈的图形如下：（3）一个有Hamilton 圈但没有Euler 闭迹的图形如下：（4）一个既没有Euler 闭迹也没有Hamilton 圈的图形如下：4.7 证明：若G 没有奇点，则存在边不重的圈C 1,C 1,···,C m ,使得)()()()(21m C E C E C E G E ••• 。

证明：将G 中孤立点除去后的图记为1G ，则1G 也没有奇点，且2)(1 G ，则1G 含圈1C ，在去掉)(11C E G 的孤立点后，得图2G ，显然2G 仍无奇度点，且2)(2 G ，从而2G 含圈2C ，如此重复下去，直到圈m C ，且)(m m C E G 全为孤立点为止，于是得到)()()()(21m C E C E C E G E 。

4.10 证明：若（1）G 不是二连通图，或者（2）G 是具有二分类),(Y X 的偶图，这里Y X ，则G 是非Hamilton 图。

证明：（1）因为G 不是二连通图，则G 不连通或者存在割点v ，有2)( v G w ，由相关定理得：若G 是Hamilton 图，则对于v(G)的任意非空顶点集S ，有：S S G w )(，则该定理得逆否命题也成立，所以可得：若G 不是二连通图，则G 是非Hamilton 图。

（2）因为G 是具有二分类),(Y X 的偶图，又因为Y X ，在这里假设Y X ，则有X Y X G w )(，也就是说：对于v(G)的非空顶点集S ，有：S S G w )(成立，则可以得出G 是非Hamilton 图。

图论第七次作业答案

图论第七次作业答案

图论第七次作业答案
6.11
求K n中无公共边的Hamilton圈的个数？
解答思路：
n-1
2
⎢⎥
⎢⎥
⎣⎦
，课本后有详细解答，构造法。

6.16
若G是二分图，但其二分图顶划分X与Y不均匀，即|X|≠|Y|，问G是否Hamilton图，为什么？解题思路：不是，假设|X|<|Y|,则ω(G-X) =|Y| >|X|,不满足Hamilton图的必要条件。

6.17
证明：若u,v∈V(G)，u与v不相邻，且d(u)+d(v) ≥|V(G)|,则G为Hamilton图的充分必要条件是G+uv是Hamilton图。

解题思路：课本后有详细解答。

7.2：
证明无向图G有一种定向方法，使得其最长有向轨不超过G的最大顶次数。

解题思路：χ(G)≤Δ+1 ,又因为有Ｌ=χ(G)-1的有向轨,所以Ｌ≤Δ.
7.3：
已知有向图G中无有向圈，求δ-与δ+。

解题思路：假如G中最长有向轨C的起始点有入边，则C要么不是最长有向轨，要么G中就存在圈，所以δ- =0，同理δ+=0。

图论第二次作业

图论第二次作业

第四章3(1).有欧拉闭迹和H圈(2).有欧拉闭迹但没有H圈(3).有H圈无欧拉闭迹(4).无欧拉闭迹且没有H圈4：证：若G不是H图，由chvatal定理知，G度弱于某个图，故：=这与题目已知条件相矛盾，故G是H图。

8：证：不失一般性，设G是连通图，是G的2k个奇点，连接，得到，则得到图，则是欧拉图，设C是中的欧拉闭迹，删除C中的，即可得到k条边不重复的迹，使得.10(1)若G不是二连通图，那么G不连通或者有割点u，则w，故G是非H图。

(2). 若G是具有二分类的偶图，且，若假设则，故G是非H图。

11：设R是G中的H路，则对于每个真子集S，有w，又：w w，故w.12：设u是G外一点，将u和G中的每个点连接得到图，则G的度序列为，故有题意知，不存在小于的正整数m，使得，故由Chvatal定理知，图是H图，则G有H路。

15：(1)由图的闭包定义可知，构作一个图的闭包，可以通过不断在度和大于等于n的非邻接顶点加边得到。

故图的闭包算法如下：第一步：令；第二步：在中求顶点，使得：第三步：如果,则转到第四步；否则，停止，则可得到G 的闭包。

第四步：令，转到第二步。

复杂性分析：由其算法我们可得出其总运算量为：故该算法能够在多项式时间内被解决，故该算法是一个好算法。

(2).设计算法如下：第一步：在闭包构造中，将加入的边依次加入次序记为，在中任意取出一个H圈，令k=N;第二步：若不在中，令；否则转到第三步。

第三步：设，令；求中两个相邻点u和v使得，u，v依序排列在上，且有：，令：第四步：若k=1，转到第五步；否则，令k=k-1,转第二步；第五步：停止。

为G的H圈。

算法的复杂性分析：因为该算法进行了N次循环，每次循环中找到满足要求的邻接顶点u和v至多需要n-3次判断，所以总的运算量：N(n-3)。

是一个好算法。

第五章1：(1)证：k方体有2k个顶点，每个顶点可以用长度为k的二进制码来表示，两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同。

电子科大研究生图论考试 附答案

电子科大研究生图论考试 附答案

1电子科技大学研究生试卷（考试时间： 至 ，共__2_小时）课程名称 图论及其应用 教师 学时 60 学分 教学方式 讲授 考核日期_2013__年_6__月__20__日 成绩 考核方式： （学生填写）一．填空题(每空2分，共20分)1． n 阶k 正则图G 的边数m =_____。

2．4个顶点的不同构单图的个数为________。

3．完全偶图,r s K (,2r s ≥且为偶数)，则在其欧拉环游中共含____条边。

4．高为h 的完全2元树至少有_______片树叶。

5. G 由3个连通分支124,,K K K 组成的平面图，则其共有_______个面。

6. 设图G 与5K 同胚，则至少从G 中删掉_______条边，才可能使其成为可平面图。

7. 设G 为偶图，其最小点覆盖数为α，则其最大匹配包含的边数为________。

8. 完全图6K 能分解为________个边不重合的一因子之并。

9. 奇圈的边色数为______。

10. 彼得森图的点色数为_______。

二．单项选择(每题3分，共15分) 1．下面说法错误的是( )学 号 姓 名 学 院…………………… 密……………封……………线……………以……………内……………答…… ………题……………无……………效……………………2(A) 图G 中的一个点独立集，在其补图中的点导出子图必为一个完全子图；(B) 若图G 连通，则其补图必连通； (C) 存在5阶的自补图； (D) 4阶图的补图全是可平面图. 2．下列说法错误的是（ ） (A) 非平凡树是偶图；(B) 超立方体图(n 方体,1n ≥)是偶图； (C) 存在完美匹配的圈是偶图； (D) 偶图至少包含一条边。

3.下面说法正确的是( )(A) 2连通图一定没有割点（假定可以有自环）； (B) 没有割点的图一定没有割边；(C) 如果3阶及其以上的图G 是块，则G 中无环，且任意两点均位于同一圈上；(D) 有环的图一定不是块。