第三章 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
离散数学作业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=
第四章 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=
《图论及其应用》大作业 指导老师郝荣霞 知行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 。 ?即证
图论第二次作业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：
课本习题一： ● 。 证明:作映射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）是图序列 非负整数组12121(,,,),,2n n n i i d d d d d d d m π==≥≥≥=∑L L 是图序列的充要条件是： ? 11 12312(1,1,,1,,,)d d n d d d d d π++=---L L 是图序列 （5,4,3,2,2,0）是图序列，然而（5,4,3,2,2,0）不是图序列，所以（6,6,5,4,3,3,1）不是图序列。 ● 12.证明：若δ≥2，则G 包含圈。 证明：下面仅对连通图的下的条件下进行证明，不连通的情形可以通过分成若干个连通的情形来证明。设V (G )={V 1，V 2,V 3,?V n },对于G 中的路V 1，V 2,V 3,?V n 若V k 与V 1邻接，则构成一个圈。若V i1，V i2,V i3,?V in 是一条路，由于δ≥2，因此，对于V in ，存在V ik 与之邻接，则V ik ，,?V in V ik 构成一个圈。 ● 17.证明：若G 不连通，则G ?连通。 证明：对于任意的u,v ∈(G ?),若u 与v 属于G 的不同连通分支，显然u 与v 在G ?中连通；若u 与v 属于g 的同一连通分支，设w 为G 的另一个连通分支中的一个顶点， 则u 与w ，v 与w 分别在G ?中连通，因此，u 与v 在G ?中连通。 ● 18.证明：若e ∈E(G),则w (G )≤w (G ?e )≤w (G )+1. 证明：若e 为G 的割边，则w (G ?e )= w (G )+1，若e 为G 的非割边，则w (G ?e )=w (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 ，有 .
图论第二次作业 一、第四章 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 的正整数
习 题 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
习题四： 3. (1)画一个有Euler闭迹和Hamilton圈的图； (2) 画一个有Euler闭迹但没有Hamilton圈的图； (3) 画一个有Hamilton圈但没有Euler闭迹的图； (4) 画一个即没有Hamilton圈也没有Euler闭迹的图; 解：找到的图如下： (1)一个有Euler闭迹和Hamilton圈的图； (2)—个有Euler闭迹但没有Hamilton圈的图; ⑶一个有Hamilton圈但没有Euler闭迹的图; (4)一个即没有Hamilton圈也没有Euler闭迹的图. 4. 设n阶无向简单图G有m条边，证明：若2 ) * ',则G是血加此"图。证明：G是H图。 若不然，因为G是无向简单图，则n芝3,由定理％若G是n芝3的非单图，则G 、一 ...C … 度弱丁某个阵".于是有：
- - 1 2 E(G)| E(C m,n ) - m (n 2m)(n m 1) m(m 1) 1. 这与条件矛盾！所以G 是H 图 若G 有个奇点，则存在k 条边不重的迹Q1?Q 矿心，使得 E(G) = E(Q 】)U E(Q J U E(Q 3) U …U E(Q k ) 证明：不失一般性，只就 G 是连通图 进行证明。设 G=(n, m)是连通图。令 虬 V 2,…,v,V k+1,…,v 是G 的所有奇度点。在V i 与v i+k 问连新边e i 得图G* (1三隹k). 则G*是欧拉图，因此，由Fleury 算法得欧拉环 游C 在C 中删去e i (1m M k).得 k 条边不重的迹Qi (1 MiMk): E(G) E(Q1^E(Q2^^E(Qk) 10. 证明：若： (1) G 不是二连通图，或者 (2) G 是具有二分类|(X,Y)的偶图，这里|X” |Y| 则G 是非Hamilton 图。 证明：(1) G|不是二连通图，则G 不连通或者存在割点v ,俨任-v) >2 ,由丁课本 上的 相关定理：若G 是Hamilton 图，则对丁*勇)的任意非空顶点集S,有： w(G- S) < |S|,则该定理的逆否命题也成立，所以可以得出：若不是二连通图， 则G 是非 Hamilton 图 (2)因为是具有二分类(XI)的偶图，乂因为|X|丰1丫1,在这里假设|X| < |Y|,则有 w(G- X) = |Y|>|X|，也就是说：对北(G)|的非空顶点集S,有：w(G-S)>||S|成 立，则可以得出 则G 是非Hamilton 图。 11. 证明：若有Hamilton 路，则对丁 V 的每个真子集S,有w(G - S) ' |S | +】. 证明：G 是H 图，设C 是G 的H 圈。则对V(G)的任意非空子集S,容易知道： (C S) S 1 1 -(m 1)(m 2) (m 1)(n 2m 1) 8.证明
离散数学作业4 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。 一、填空题 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=
图论及其应用第二次作业 要求：1、交电子档给助教【助教给每个班设置邮箱，助教设置提交回复】； 2、第7章授课结束前均可以提交； 3、希望能够独立完成。 1．判断图4-43所示的四个图是否可以一笔画。 上面四个图都是连通图，看是否能一笔画成问题本质上看图是否存在欧拉迹；连通图有欧垃迹当且仅当G 最多有两个奇点。 （a ）不可以 有4个奇点 （b ）可以 一个奇点 （c ）可以 两个奇点 （d ）可以 没有奇点 2.（1）画一个有欧拉闭迹和哈密尔顿圈的图； （2）画一个有欧拉闭迹但没有哈密尔顿圈的图； (3) 画一个有哈密尔顿圈但没有欧拉闭迹的图； （4）画一个既没有欧拉闭迹也没有哈密尔顿圈的图。 3. 设n 阶无向简单图G 有m 条边。证明：若m ≥??? ? ??-21n +2，则G 是哈密尔顿图。 (b ) (c ) (d ) 图4-43
证明：G 是H 图。若不然，因为G 是无向简单图，则n ≥3，由定理1：若G 是n ≥3的非单图，则G 度弱于C m,n 。于是有： 2,1()()(2)(1)(1)2 1111(1)(2)(1)(21) 1.222m n E G E C m n m n m m n n n m m m n m ??≤= +---+-??--????=+-------≤+ ? ????? 这与条件矛盾！所以G 是H 图。 4. 在图4-45中，哪些图是哈密尔顿图？哪些图中有哈密尔顿路？ (a)非哈密尔顿图，没有哈密尔顿路 (b)哈密尔顿图 （abcdejhfiga) (c)哈密尔顿图 （kjdhbagciefk) (d)非哈密尔顿图 有哈密尔顿路（hjaidebcgf) (e)不是哈密尔顿图，因为有割点a ，有哈密尔顿路（jaibcedkgfh ） 5. 证明：若G 没有奇点，则存在边不重的圈C 1, C 2,…, C m ，使得，E (G ) = E (C 1)∪E (C 2)∪…∪E (C m )。 证明：将G 中孤立点除去后的图记为G 1，则G 1也没有奇点，且δ（G 1)，则G 1含圈C 1，在去掉()11G E C -的孤立点后，得图G 2，显然G 2仍无奇度点，且δ（G 2）≥ 2，从而G 2含圈C 1，如此重复下去，直到圈C m ，且G m －E (C m )全为孤立点为止，于是得到E (G ) = E (C 1)∪E (C 2)∪…∪E (C m )。 e （a ） （b ） e （c ） h （d ） 图4-45 （e ）
2014离散数学作业5答案
离散数学作业5 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第15周末前完成并上交任课教师（不收电子稿）。并在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=
习题 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)
图论第三次作业 一、第六章 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.
电大离散数学作业答案作 业答案 RUSER redacted on the night of December 17,2020
离散数学作业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=
习题四 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闭迹的图. 7. 将G中的孤立点去掉后的图为G1，则G1也是没有奇度点的，且G1的最小度大于等于2.则G1存在一个圈S1，在G1 –S1中去除孤立的点，得到一个新的图G2，显然G2也没有奇度的点，且G2的最小度大于等于2.这样G2中也存在一个圈S2，这样一直下去，指导Gm中有圈Sm，且Gm-Sm都是孤立的点。这样E(G) = E(G1)并E(G2)…并E(Gm).命题得证。 10．证明：若： （1）不是二连通图，或者 （2）是具有二分类的偶图，这里,
则是非Hamilton图。 证明：（1）不是二连通图，则不连通或者存在割点,有,由于课本上的相关定理：若是Hamilton图，则对于的任意非空顶点集，有：,则该定理的逆否命题也成立，所以可以得出：若不是二连通图，则是非Hamilton图 (2)因为是具有二分类的偶图，又因为，在这里假设,则有 ,也就是说：对于的非空顶点集，有：成立，则可以得出则是非Hamilton图。 习题五 1.(1)证明：每个k方体都有完美匹配(k大于等于2) (2) 求K2n和K n,n中不同的完美匹配的个数。 证明一：证明每个k方体都是k正则偶图。 事实上，由k方体的构造：k方体有2k个顶点，每个顶点可以用长度为k的二进制码来表示，两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同。如果我们划分k方体的2k个顶点，把坐标之和为偶数的顶点归入X，否则归入Y。显然，X中顶点互不邻接，Y中顶点也如此。所以k方体是偶图。又不难知道k方体的每个顶点度数为k,所以k方体是k正则偶图。 由推论：k方体存在完美匹配。 证明二：直接在k方体中找出完美匹配。 设k方体顶点二进制码为(x1,x2,…,x k),我们取(x1,x2,…,x k-1,0),和(x1 ,x2,…,x k-1,1) 之间的全体边所成之集为M.显然，M中的边均不相邻接，所以作成k方体的匹配，又容易知道：|M|=2k-1.所以M是完美匹配。 (2) 我们用归纳法求K2n和K n,n中不同的完美匹配的个数。 K2n的任意一个顶点有2n-1种不同的方法被匹配。所以K2n的不同完美匹配个数等于(2n-1)K2n-2,如此推下去，可以归纳出K2n的不同完美匹配个数为：(2n-1)!!同样的推导方法可归纳出K n, n的不同完美匹配个数为：n! 6．证明：K2n的1-因子分解的数目为(2n)!/(2^n*n!)。 因为 K2n的不同完美匹配的个数为(2n-1)!!。所以，K2n的一因子分解数目为(2n-1)!!个，即2n)!/(2^n*n!)，命题得证。