当前位置：文档库 › 第三次图论作业

第三次图论作业

第六章

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.

4.证明：

(1)∵G 是极大平面图，

∴G 的每个面的次数为3，

由次数公式：2m==3φ,

由欧拉公式：φ=2-n+m,

∴2m=6-3n+3m,即m=3n-6.

(2)又由欧拉公式m=n+φ-2,即 3n-6=n+φ-2,从而φ=2n-4.

(3)对于n>3的极大可平面图的的每个顶点，有，即对任一一点或者子图，至少有三个邻点与之相连，要使这个点或子图与图G 不连通，必须把与之相连的点去掉，所以至少需要去掉三个点才能使

，由点连通度的定义知。

6.31(G3) v ()3d v ≥()(H)w G w G <-()3G κ≥

第七章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)。

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}。

图论作业(1)

第三章 1.证明：必要性： v 是连通图G 的割边，则，至少有两个连通分支。设其中一个连通分支顶点集合为V1,另外连通分支顶点集合为V2,即V1与V2构成V 的划分。对于任意的u ∈V1, v ∈V2，如果割边e 不在某一条（u ，v ）路上，那么，该路也是连接G-e 中的u 与v 的路，这与u,v 处于G-v 的不同分支矛盾。 “充分性” 若e 不是图G 的割边，那么G-v 连通，因此在G-v 中存在u,v 路，当然也是G 中一条没有经过边e 的u,v 路。矛盾。 7.证明： v 是单图G 的割点，则G-v 至少两个连通分支。现任取 , 如果x,y 在G-v 的同一分支中，令u 是与x,y 处于不同分支的点，那么，通过u ，可说明，x 与y 在G-v 的补图中连通。若x,y 在G-v 的不同分支中，则它们在G-v 的补图中邻接。所以，若v 是G 的割点，则v 不是其补图的割点。 9.连通图G 的一个子图B 称为是G 的一个块，如果(1), 它本身是块；(2), 若没有真包含B 的G 的块存在。又由于对于阶数至少是3的 ()()G e G ωω->

图G是块当且仅当G无环并且任意两点都位于同一圈上。根据题意，对于阶数至少是3的图G，由于G没有偶圈，所以G的每个块的点可以在奇圈上，如果不在奇圈上，则块只能是K2，否则如果不是K2的话，该子图将存在割点，该子图就不是块。得证。 16.（1）（2）（3）

第四章3. （1）既是欧拉闭迹又是哈密尔顿圈（2）（3）

（4） 7.由于图没有奇度顶点，所以是欧拉图，又定理1可得，图G的边集可以划分为圈C1，C2，。。。。Cm，所以E（G）可以表示成C1，C2.。。Cm的并。 10.若图不是二连通，则存在割点，由于哈密尔顿图不存在割点，因而G是非哈密尔顿图。若G是具有二分类（X,Y）的偶图，且|X|不等于|Y|，设X中所有点为x1，x2.。。。。xm，Y中的所有点为y1，y2.。。。。yn，若存在哈密尔顿图，则在哈密尔顿圈中必然存在X中的点与Y中的点相互交替出现，但是|X|不等于|Y|，则必然出现某两个点同属于|X|或者|Y|，但是G是偶图，属于同一集合的这样的两个点不可以相连，所以存在哈密尔顿圈矛盾，因而不存在哈密尔顿圈。 12. 证明：在G之外加上一个新点v,把它和G的其余各点连接得图G1

电大离散数学作业答案05作业答案

离散数学作业5 离散数学图论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月5日前完成并上交任课教师（不收电子稿）。并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。一、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ． 2．设给定图G (如右由图所示)，则图G 的点割集是 {}f {}c e ,． 3．设G 是一个图，结点集合为V ，边集合为E ，则 G 的结点度数之和等于边数的两倍． 4．无向图G 存在欧拉回路，当且仅当G 连通且不含奇数度结点． 5．设G=是具有n 个结点的简单图，若在G 中每一对结点度数之和大于等于︱V ︱，则在G 中存在一条汉密尔顿回路． 6．若图G=中具有一条汉密尔顿回路，则对于结点集V 的每个非空子集S ，在G 中删除S 中的所有结点得到的连通分支数为W ，则S 中结点数|S|与W 满足的关系式为 S W ≤ ． 7．设完全图K n 有n 个结点(n 2)，m 条边，当n 为奇数时，K n 中存在欧拉回路． 8．结点数v 与边数e 满足 e= v －1 关系的无向连通图就是树． 9．设图G 是有6个结点的连通图，结点的总度数为18，则可从G 中删去条边后使之变成树． 10．设正则5叉树的树叶数为17，则分支数为i = 4 ．二、判断说明题（判断下列各题，并说明理由．） 1．如果图G 是无向图，且其结点度数均为偶数，则图G 存在一条欧拉回路．．答：错误。应叙述为：“如果图G 是无向连通图，且其结点度数均为偶数，

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

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

图论第二次作业

第四章 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的二进制码来表示，两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同。若划分k方体的2k个顶点，把坐标之和为偶数的顶点归入X，否则归入Y。显然，X中顶点互不邻接，Y中顶点也如此。所以k方体是偶图。又k方体的每个顶点度数为k,所以k方体是k正则偶图。所以由推论可知：k方体存在完美匹配。 (2).解K 2n 的任意一个顶点有2n-1中不同的方法被匹配。所以K 2n 的不同完美匹配个数等于(2n-1)K 2n-2,如此推下去，可以归纳出K 2n 的不同完美匹配个数为： (2n-1)!!。同理，K n, n 的不同完美匹配个数为：(n)!。 2：若不然，设M 1与M 2 是树T的两个不同的完美匹配，那么M 1 ΔM 2 ≠Φ,且T[M 1 ΔM 2 ] 每个顶点度数为2，即它存在圈，于是推出T中有圈，矛盾。故一棵树中最多只有一个完美匹配。 7：解：设作如下四条路：故其四个生成圈如下：

电大离散数学作业答案(图论部分)

离散数学作业5 离散数学图论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2018年12月5日前完成并上交任课教师（不收电子稿）。并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。一、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是15． 2．设给定图G (如右由图所示)，则图G 的点割集是 {f}． 3．设G 是一个图，结点集合为V ，边集合为E ，则 G 的结点度数之和等于边数的两倍． 4．无向图G 存在欧拉回路，当且仅当G 连通且等于出度． 5．设G=是具有n 个结点的简单图，若在G 中每一对结点度数之和大于等于n-1，则在G 中存在一条汉密尔顿路． 6．若图G=中具有一条汉密尔顿回路，则对于结点集V 的每个非空子集S ，在G 中删除S 中的所有结点得到的连通分支数为W ，则S 中结点数|S|与W 满足的关系式为W(G-V1)≤∣V 1∣． 7．设完全图K n 有n 个结点(n ≥2)，m 条边，当n 为奇数时，K n 中存在欧拉回路． 8．结点数v 与边数e 满足e=v-1关系的无向连通图就是树． 9．设图G 是有6个结点的连通图，结点的总度数为18，则可从G 中删去 4条边后使之变成树． 10．设正则5叉树的树叶数为17，则分支数为i =5．二、判断说明题（判断下列各题，并说明理由．） 1．如果图G 是无向图，且其结点度数均为偶数，则图G 存在一条欧拉回

图论第二次作业

图论第二次作业Newly compiled on November 23, 2020

图论第二次作业一、第四章（1）画一个有Euler 闭迹和Hamilton 圈的图；（2）画一个有Euler 闭迹但没有Hamilton 圈的图；（3）画一个有Hamilton 圈但没有Euler 闭迹的图；（4）画一个既没有Euler 闭迹也没有Hamilton 圈的图；解：（1）一个有Euler 闭迹和Hamilton 圈的图形如下：（2）一个有Euler 闭迹但没有Hamilton 圈的图形如下：（3）一个有Hamilton 圈但没有Euler 闭迹的图形如下：（4）一个既没有Euler 闭迹也没有Hamilton 圈的图形如下：证明：若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 ???=。证明：若（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 图。设G 是有度序列),,,(21n d d d ???的非平凡简单图，这里n d d d ≤???≤≤21，证明：若不存在小于2 )1(+n 的正整数m ，使得m d m <且m n d m n -<+-1，则G 有Hamliton 路。证明：在G 之外加上一个新点v ，把它和G 的其余各点连接，得图G 1：

图论大作业

《图论及其应用》大作业指导老师郝荣霞知行1503 徐鹏宇 15291200

2.1.9证明：若G是森林且恰有2k个奇点，则在G中有k条边不重的路P1,P2......P K,使得E(G)=E(P1) E(P2) ...... E(P K)。证明：对奇点数k使用数学归纳法。 ①当k=1时，G是森林，且有且只有2个奇点 ?G只能为一颗树，且G的所有奇度顶点为两个1度顶点 ?G是一条路 ?满足题设 ②假设当k=t时，结论成立。接下来考虑k=t + 1时的情况。在G中一个分支中取两个叶子点u与v，令P是连接该两个顶点的唯一路。由于P上除u，v以外的点均被P经过两次，即G-P后除u，v以外的点奇偶性不变。 ?则G–P是有2t个奇度顶点的森林 ?由归纳假设知，G–P可以分解为t条边不重合的路之并，即E(G-P)=E(P1) E(P2) ...... E(P t)。 ?则G可分解为t+1条边不重合的路之并，即E(G)=E(P1) E(P2) ...... E(P t) E(P)。 ?即证。

2.4.4证明：若e 是K n 的边，则τ（K n -e ）=（n-2）n n-3 证明：由定理2.9：τ（K n ）=n n-2 由于τ（K n -e ）=τ（K n ）-τ（含有e 的生成树棵树）现在需要求含有e 的生成树棵树， τ（含有e 的生成树棵树）=)1(2 1n 1-n 2-n n n ）（=2n n-3 τ（K n -e ）=τ（K n ）-τ（含有e 的生成树棵树）=（n-2）n n-3

3.2.4证明：不是块的连通图至少有两个块，其中每个恰有一个割点。证明：设G 为不是块的连通图，由于G 连通且不是块 ?G 有割点 ①当G 只有1个割点v 时，延割点分开，G1，G2内无割点，且连通，由块的定义知?G1,G2是块，且分别含一个割点v 。 ②当G 含有2个及2个以上割点时，取相距距离最远的两个割点u 和v ，此时分G 为三部分G1,G2,G3 。由于u ，v 是相距最远的两割点?G1和G3不含割点。又由于G 连通，G1,G3为G 的一部分?故G1,G3连通。 ?G1，G3内无割点，且连通。 ?G1，G3是块，且分别含割点u ，v 。 ?即证

电子科技大学-图论第一次作业-

课本习题一： ● 。证明:作映射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）是图序列 11 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的不同连通分支，显然与在中连通；若与属于的同一连通分支，设为G的另一个连通分支中的一个顶点，则与

电子科技大学-图论第二次作业

习题四： 3.（1）画一个有Euler 闭迹和Hamilton圈的图；（2）画一个有Euler闭迹但没有Hamilton圈的图；（3）画一个有Hamilton圈但没有Euler闭迹的图；（4）画一个即没有Hamilton圈也没有Euler闭迹的图；解：找到的图如下： (1)一个有Euler 闭迹和Hamilton圈的图； (2)一个有Euler闭迹但没有Hamilton圈的图； (3) 一个有Hamilton圈但没有Euler闭迹的图; (4)一个即没有Hamilton圈也没有Euler闭迹的图. 4.设n阶无向简单图G有m条边，证明:若,则是图。证明: G是H图。若不然，因为G是无向简单图，则,由定理1：若G是的非单图，则G 度弱于某个.于是有：

2,1()()(2)(1)(1)2 11 1(1)(2)(1)(21)221 1.2m n E G E C m n m n m m m n m m m n m n ??≤= +---+-??-??=+------- ? ?? -??≤+ ??? 这与条件矛盾！所以G 是H 图。 8.证明：若G 有个奇点，则存在条边不重的迹 ,使得 . 证明：不失一般性，只就G 是连通图进行证明。设G=(n, m)是连通图。令v l ，v 2，…,v k ,v k+1,…,v 2k 是G 的所有奇度点。在v i 与v i+k 间连新边e i 得图G*（1≦i ≦k).则G*是欧拉图，因此，由Fleury 算法得欧拉环游C.在C 中删去e i （1≦i ≦k).得k 条边不重的迹Q i （1≦i ≦k): 12()() () ()k E G E Q E Q E Q = 10.证明：若：（1）不是二连通图，或者（2）是具有二分类的偶图，这里 , 则是非Hamilton 图。证明：（1）不是二连通图，则不连通或者存在割点,有,由于课本上的相关定理：若是Hamilton 图，则对于的任意非空顶点集，有： ,则该定理的逆否命题也成立，所以可以得出：若不是二连通图，则是非Hamilton 图 (2)因为是具有二分类的偶图，又因为，在这里假设 ,则有,也就是说：对于的非空顶点集，有：成立，则可以得出则是非Hamilton 图。 11.证明：若有Hamilton 路，则对于V 的每个真子集S ，有 .

图论王树禾答案

图论第一次作业 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 G

1.12求证(a)?K m ,n =mn，(b)G是完全二分图，则?G≤1 4 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 4

?证明： ?(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个点的度数之和最大可能为

图论第二次作业

图论第二次作业一、第四章 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 图。 4.12 设G 是有度序列),,,(21n d d d ???的非平凡简单图，这里n d d d ≤???≤≤21，证明：若不存在小于 2 )1(+n 的正整数m ，使得m d m <且m n d m n -<+-1，则G 有Hamliton 路。证明：在G 之外加上一个新点v ，把它和G 的其余各点连接，得图G 1： G 1的度序列为：),1,,1,1(21n d d d n +???++，由已知：不存在小于2 )1(+n 的正整数

图论习题参考答案

二、应用题题0：（1996年全国数学联赛）有n （n ≥6）个人聚会，已知每个人至少认识其中的[n /2]个人，而对任意的[n /2]个人，或者其中有两个人相互认识，或者余下的n -[n /2]个人中有两个人相互认识。证明这n 个人中必有3个人互相认识。注：[n /2]表示不超过n /2的最大整数。证明将n 个人用n 个顶点表示，如其中的两个人互相认识，就在相应的两个顶点之间连一条边，得图G 。由条件可知，G 是具有n 个顶点的简单图，并且有（1）对每个顶点x ， )(x N G ≥[n /2]；（2）对V 的任一个子集S ，只要S ＝[n /2]，S 中有两个顶点相邻或V-S 中有两个顶点相邻。需要证明G 中有三个顶点两两相邻。反证，若G 中不存在三个两两相邻的顶点。在G 中取两个相邻的顶点x 1和y 1,记N G (x 1)＝{y 1,y 2,……,y t }和N G (y 1)={x 1,x 2,……,x k },则N G (x 1)和N G (y 1)不相交，并且N G (x 1)（N G (y 1)）中没有相邻的顶点对。情况一；n=2r ：此时[n /2]＝r ，由（1）和上述假设，t=k=r 且N G (y 1)＝V-N G (x 1)，但N G (x 1)中没有相邻的顶点对，由（2），N G (y 1)中有相邻的顶点对，矛盾。情况二；n=2r+1: 此时[n /2]＝r ，由于N G (x 1)和N G (y 1)不相交，t ≥r,k ≥r,所以r+1≥t,r+1≥k 。若t=r+1,则k=r ，即N G (y 1)=r ，N G (x 1)＝V-N G (y 1)，由（2），N G (x 1)或N G (y 1)中有相邻的顶点对，矛盾。故k ≠r+1，同理t ≠r+1。所以t=r,k=r 。记w ∈V- N G (x 1) ∪N G (y 1),由（2），w 分别与N G (x 1)和N G (y 1)中一个顶点相邻，设wx i0∈E, wy j0∈E 。若x i0y j0∈E ，则w ，x i0, y j0两两相邻，矛盾。若x i0y j0?E ，则与x i0相邻的顶点只能是(N G (x 1)-{y j0})∪{w},与y j0相邻的顶点只能是(N G (y 1)-{x j0})∪{w}。但与w 相邻的点至少是3，故N G (x 1)∪N G (y 1)中存在一个不同于x i0和y j0顶点z 与w 相邻，不妨设z ∈N G (x 1)，则z ，w ，x i0两两相邻，矛盾。题1：已知图的结点集V ={a ,b ,c ,d }以及图G 和图D 的边集合分别为： E (G )={(a ,a ), (a ,b ), (b ,c ), (a ,c )} E (D)={, , , , } 试作图G 和图D ，写出各结点的度数，回答图G 、图D 是简单图还是多重图？解： a d a d b c b c 图G 图D 例2图