离散数学作业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=
离散数学作业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=
图论及其应用答案电子科 大 Newly compiled on November 23, 2020
习题三： ● 证明：e 是连通图G 的割边当且仅当V(G)可划分为两 个子集V1和V2，使对任意u ∈V 1及v ∈V 2, G 中的路（u ，v ）必含e . 证明：充分性: e 是G 的割边，故G ?e 至少含有两个连通分支，设V 1是其中一个连通分支的顶点集，V 2是其余分支的顶点集，对12,u V v V ?∈?∈，因为G 中的u,v 不连通， 而在G 中u 与v 连通，所以e 在每一条(u,v)路上，G 中的(u,v)必含e 。 必要性：取12,u V v V ∈∈，由假设G 中所有(u,v)路均含有边e ，从而在G ?e 中不存在从 u 与到v 的路，这表明G 不连通，所以e 是割边。 ● 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 （1）→（2）： G 是块，任取G 的一点u ，一边e ，在e 边插入一点v ，使得e 成为两条边，由此得到新图G 1，显然G 1的是阶数大于3的块，由定理，G 中的u,v 位于同一个圈上，于是G 1中u 与边e 都位于同一个圈上。 （2）→（3）： G 无环，且任意一点和任意一条边都位于同一个圈上，任取G 的点u ，边e ，若u 在e 上，则三个不同点位于同一个闭路，即位于同一条路，如u 不在e 上，由定理，e 的两点在同一个闭路上，在e 边插入一个点v ，由此得到新图G 1，显然G 1的是阶数大于3的块，则两条边的三个不同点在同一条路上。
第四章 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：解：设 作如下四条路： 故其四个生成圈如下：
图论第二次作业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：
习 题 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
课本习题一： ● 。 证明:作映射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的另一个连通分支中的一个顶点，则与
第二章 图的连通性 在第一章中已经定义连通图是任二顶点间都有路相连的图。对于连通图，其连通的程度也有高有低。例如，下列三个图都是连通图。对于图G 1，删除一条边或一个顶点便可使其变得不连通；而对于图G 2，至少需要删除两条边才能使其不连通，也可以删除一个顶点使其不连通；对于图G 3，要破坏其连通性，则至少需要删除三条边或三个顶点。 本章主要讨论如何通过图的顶点集、边集和不交的路集合的结构性质来获知图的连通性程度。通过研究割边和割点来刻画1连通图的特性；定义连通度和边连通度来度量连通图连通程度的高低；通过不交路结构和元素的共圈性质来反映图的2连通和k 连通性。 §2.1 割点和割边 定义2.1.1 设)(G V v ∈，如果)()(G w v G w >?，则称v 为G 的一个割点。 （注：该定义与某些著作中的定义有所不同，主要是在环边的顶点是否算作割点上有区别）。 例如，下图中u , v 两点是其割点。 定理2.1.1 如果点v 是简单图G 的一个割点，则边集E (G)可划分为两个非空子集1E 和2E ，使得][1E G 和][2E G 恰好有一个公共顶点v 。 证明留作习题。 推论2.1.1 对连通图G ，顶点v 是G 的割点当且仅当v G ?不连通。 定理2.1.2 设v 是树T 的顶点，则v 是T 的割点当且仅当1)(>v d 。 证明：必要性：设v 是T 的割点，下面用反证法证明1)(>v d 。 若0)(=v d ，则1K T ?，显然v 不是割点。 若1)(=v d ，则v T ?是有1)(??v T ν条边的无圈图，故是树。从而)(1)(T w v T w ==?。因此v 不是割点。 以上均与条件矛盾。 充分性：设1)(>v d ，则v 至少有两个邻点u ,w 。路uvw 是T 中一条),(w u 路。因T 是树，uvw 是T 中唯一的),(w u 路，从而)(1)(T w v T w =>?。故v 是割点。证毕。
习题四： 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 ，有 .
学号：0441 姓名：张倩 习题1 4．证明图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 ，则有： m=0: m=1 ： (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)
m=2：m=3：
m=4：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 123121,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)=｛v1,v2,…,vn ｝,对于G 中的路v1v2…vk,若vk 与v1邻接，则构成一个圈。若vi1vi2…vin 是一条路，由于 2，因此，对vin ，存在点vik 与之邻接，则vik vinvik 构成一个圈 。 17.证明：若G 不连通，则G 连通。 证明 对)(,_ G V v u ∈?,若u 与v 属于G 的不同连通分支，显然u 与v 在_ G 中连通；若u 与v 属于g 的同一连通分支，设w 为G 的另一个连通分支中的一个顶点，则u 与w ，v 与w 分别在_ G 中连通，因此，u 与v 在_ G 中连通。 18.证明：若()e E G ∈,则()()()1G G e G ωωω≤-≤+. 证明：若e 为G 的割边，则()()1G e G ωω-=+，若e 为G 的非割边，则 ()()G e G ωω-=，所以，若()e E G ∈，则有()()()1G G e G ωωω≤-≤+. 习题2 1.证明：每棵恰有两个1度顶点的树均是路。 证明：设树T 为任意一个恰有两个1度顶点的树，则T 是连通的，且无圈，
图论第一次作业 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)={, ,
习题四： 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.证明
离散数学数理逻辑部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分．作业应手工书写答题，字迹工整，解答题要有解答过程，完成后上交任课教师（不收电子稿）． 一、填空题 1．命题公式() →∨的真值是 1 ． P Q P 2．设P：他生病了，Q：他出差了．R：我同意他不参加学习.则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为P∨Q→R ． 3．含有三个命题变项P，Q，R的命题公式P∧Q的主析取范式是(P∧Q∧┐R)∨(P∧Q∧R) ． 4．设P(x)：x是人，Q(x)：x去上课，则命题“有人去上课．”可符号化为?x ( P ( x) ∧Q ( x))． 5．设个体域D＝{a, b},那么谓词公式) xA? ∨ x ?消去量词后的等值式为 yB ( ) (y (A(a)∨A(b))∨(B(a) ∧B(b))． 6．设个体域D＝{1, 2, 3}，A(x)为“x大于3”，则谓词公式(?x)A(x) 的真值为0 ． 7．谓词命题公式(?x)((A(x)∧B(x)) ∨C(y))中的自由变元为y ．8．谓词命题公式(?x)(P(x) →Q(x) ∨R(x，y))中的约束变元为x ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 解：
离散数学作业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=
习题三： ● 证明：e 是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意u ∈V 1及v ∈V 2, G 中的路（u ，v ）必含e . 证明：充分性: e 是G 的割边，故G ?e 至少含有两个连通分支，设V 1是其中一个连通分支的顶点集，V 2是其余分支的顶点集，对12,u V v V ?∈?∈，因为G 中的u,v 不连通，而 在G 中u 与v 连通，所以e 在每一条(u,v)路上，G 中的(u,v)必含e 。 必要性：取12,u V v V ∈∈，由假设G 中所有(u,v)路均含有边e ，从而在G ?e 中不存在从u 与到v 的路，这表明G 不连通，所以e 是割边。 ● 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 （1）→（2）： G 是块，任取G 的一点u ，一边e ，在e 边插入一点v ，使得e 成为两条边，由此得到新图G 1，显然G 1的是阶数大于3的块，由定理，G 中的u,v 位于同一个圈上，于是G 1中u 与边e 都位于同一个圈上。 （2）→（3）： G 无环，且任意一点和任意一条边都位于同一个圈上，任取G 的点u ，边e ，若u 在e 上，则三个不同点位于同一个闭路，即位于同一条路，如u 不在e 上，由定理，e 的两点在同一个闭路上，在e 边插入一个点v ，由此得到新图G 1，显然G 1的是阶数大于3的块，则两条边的三个不同点在同一条路上。 （3）→（1）： G 连通，若G 不是块，则G 中存在着割点u ，划分为不同的子集块V 1, V 2, V 1, V 2无环，12,x v y v ∈∈，点u 在每一条(x,y)的路上，则与已知矛盾，G 是块。 ● 7.证明：若v 是简单图G 的一个割点，则v 不是补图G ?的割点。 证明：v 是单图G 的割点，则G ?v 有两个连通分支。现任取x,y ∈V(G ?v), 如果x,y 不在G ?v 的同一分支中，令u 是与x,y 处于不同分支的点，那么，x,与y 在G ?v 的补图中连通。若x,y 在G ?v 的同一分支中，则它们在G ?v 的补图中邻接。所以，若v 是G 的割点，则v 不是补图的割点。 ● 12.对图3——20给出的图G1和G2，求其连通度和边连通度，给出相应的最小点割和最小边割。 解：()12G κ= 最小点割 {6,8} 1()2G λ= 最小边割{（6,5），（8,5）}