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

图论第二次作业

图论第二次作业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：

G 1的度序列为：),1,,1,1(21n d d d n +???++，由已知：不存在小于2

)1(+n 的正整数m ，使得m d m ≤+1且m n m n d m n -+=+-<++-)1(111。于是由度序列判定定理知：G 1是Hamilton 路，则G 有Hamliton 路。

二、第五章作业

5.1 （1）证明：每个k 方体都有完美匹配（2≥k ）;

（2）求K 2n 和K n,n 中不同的完美匹配的个数。

证明：（1）证明每个k 方体都是k 正则偶图即可。

事实上，由k 方体的构造：k 方体有2k 个顶点，每个顶点可以用长度为k 的二进制码来表示，两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同。如果我们划分k 方体的2k 个顶点，把坐标之和为偶数的顶点归入X ，其余归入Y 。显然，X 中顶点互不邻接，Y 中顶点也如此。所以k 方体是偶图。又不难知道k 方体的每个顶点度数为k ，所以k 方体是k 正则偶图。

由推论得：k 方体存在完美匹配。

解：（2）利用归纳法求K 2n 和K n,n 中不同的完美匹配的个数。

K 2n 的任意一个顶点有2n-1中不同的方法被匹配。所以K 2n 的不同完美匹配个数等于(2n-

1)K 2n-2，如此递推下去，可以归纳出K 2n 的不同完美匹配个数为：(2n-1)!!；利用同样的方法可归纳出K n,n 的不同完美匹配个数为：n!。

证明：一棵树最多只有一个完美匹配。

证明：若不然，设M 1和M 2是树T 的两个不同的完美匹配，那么φ≠?21M M ，容易知道：][21M M T ?每个非空部分顶点度数为2，即它存在圈，于是推出T 中有圈，矛盾。所以一棵树最多只有一个完美匹配。

证明：K 2n 的1-因子分解的数目为

!2)!2(n n n ?。证明：由结论知：K 2n 不同完美匹配的个数为(2n-1)!!。所以，K 2n 的1-因子分解数目为

(2n-1)!!个。即：将K 9表示为四个生成圈之和。

解：K 4n+1=K 2(2n)+1，所以，可以分解成2n 个边不重的2因子之和。而K 9=K 2*4+1。所以K 9可以表示为四个边不重的2因子之和，对于每个分解出的因子的路径为：

则K 9的四条路径为：

则生成圈H i 是V 2n+1与P i 的两个端点连线生成的。所以可将K 9表示为四个生成圈之和。

所谓n

n 矩阵的一条对角线是指两两不同行不同列的n个矩阵元素组成的集。对角线的权是指它的n个元素的和。找出下列矩阵具有最小权的对角线：

解：首先从第一行第一列开始，找出矩阵中的最小元素，发现为坐标是(1,1)的4，将其所在的行和列删除，得到的矩阵为

再从此矩阵的第一行第一列开始，找出矩阵中的最小元素，发现为原坐标是(2,5)的4。依次类推，继续得到坐标是(3,2)的5，(5,3)的7，(4,4)的10。

所以最小权为：4+4+5+7+10=30。

图论作业(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 是无向连通图，且其结点度数均为偶数，

图论第二次作业

第四章 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 。 ?即证

基于图论的节点分析

2011年第2期青海师范大学学报(自然科学版)Journal of Qinghai Norm al U niversity(Natural Science) 2011No.2 收稿日期:2010-11-12 作者简介:黄湘宁(1964-),男(汉族),湖南邵阳人,副教授. 祝延波(1967-),男(汉族),河南洛阳人,副教授. 基于图论的节点分析黄湘宁1,祝延波2 (1.青海师范大学实验设备管理中心,青海西宁 810008;2.青海民族大学物理与电子信息工程学院,青海西宁 810007) 摘要:针对网络节点抗漏洞攻击能力弱造成网络鲁棒性差的情况,分析了基于图论的节点鲁棒性、节点重要性和节点多样性研究现状,提出了一些能够较好满足节点鲁棒性和多样性要求的方法;对节点鲁棒性测量的3个方法作了定义;对四种典型的测试网络用这些测量方法进行了对比分析,结果表明考虑了节点多样性的网络其节点连接鲁棒性、节点恢复鲁棒性和抗攻击性有了明显提高.这样的网络能有效增强节点的抗漏洞攻击能力,阻断各种可能的漏洞攻击在节点之间的渗透和传播,具有较强的鲁棒性.关键词:图论;网络;节点;多样性;漏洞中图分类号:TP393 文献标识码:A 文章编号:1001-7542(2011)02-0017-04 1 引言节点是构成网络的主要部分,节点安全性对网络安全有很大影响.随着网络规模的扩大和网络应用的扩展,针对各种节点特别是核心节点的漏洞攻击日趋频繁,这给网络管理和维护工作带来极大压力.针对节点漏洞攻击的鲁棒性研究显得尤为迫切和必要. 近年来图论在各种复杂网络如交通网、社会经济网、物流网络、传感器网络、因特网等领域得到了广泛应用.一些学者利用图论对节点鲁棒性、节点重要性和节点多样性进行研究取得了较好的效果.本文通过图论对节点鲁棒性、节点重要性以及节点多样性进行分析研究,并提出了一些提高节点鲁棒性、节点重要性以及节点多样性的方法,这些方法能够有效隔离节点漏洞攻击、阻止其渗透和传播,从而有效提高重要节点和网络的鲁棒性和安全性. 2 节点鲁棒性网络的鲁棒性通常指当网络中的部分节点或者链路被破坏,网络能够继续维持其功能的能力.毫无疑问,节点鲁棒性是网络鲁棒性的基础和重点.复杂网络研究表明,因特网是一个既有鲁棒性又有脆弱性(ro -bust y et frag ile)的无标度网络[1].研究表明,去掉1%的核心节点 ,网络的性能将下降一半;若去掉4%的核心节点 ,网络将不能保证任意节点的连通性.因此保证网络中这些重要节点的鲁棒性、当这些节点被攻击时隔离并阻断其传播是保证网络鲁棒性的关键. 文献[2]提出了基于全网平均等效最短路径数的网络抗毁评估模型,该模型反映了待评价网络和全连通网络的拓扑结构差异,导致了网络抗毁能力下降,能准确评价网络的抗毁性能.文献[3]提出了R.C.H 策略,这种针对协同攻击(coo rdinated attack)的策略考虑移除部分崩溃的核心节点来提高网络鲁棒性.文献 [4]指出降低相邻节点的相关度可以有效提高节点的抗漏洞攻击能力和阻止攻击的扩散,并提出了一种基于图论的节点鲁棒性增强算法,采用这种算法构建网络来提高节点的抗漏洞攻击能力和鲁棒性. 由于网络安全事件的不确定性,一些人为设计瑕疵和设置问题使得网络节点会有较多漏洞,这些漏洞引起的攻击会大大降低网络的鲁棒性.由于网络的内部结构和动态相关性,一个节点遇到攻击或内部错误时会将攻击或失效服务向其他节点传递. 影响节点鲁棒性的主要因素有:节点的软件漏洞(包括操作系统和应用软件)、节点设置问题、冗余节点

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

习题四： 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 ，有 .

基于图论的奖金分配问题

五、详细设计 #include #include using namespace std; //图结点 typedef struct Node { int to; Node* next; Node(int to_ = 0, Node* next_ = NULL) { to = to_; next = next_; } }Node; //判断图是否有环 bool isCircle(const vector &edges) { int i; //记录各个结点的入度 vector indegree(edges.size(), 0); for (i = 1; i < edges.size(); ++i) { Node* node = edges[i].next; while (node) { indegree[node->to] ++; node = node->next; } } //记录入度为0的结点 vector indegree0; for (i = 1; i < edges.size(); ++i) { if (indegree[i] == 0) { indegree0.push_back(i); }

} //利用队列实现是否存在环的判断 for (i = 0; i < indegree0.size(); ++i) { Node *node = edges[indegree0[i]].next; while (node) { indegree[node->to] --; if (indegree[node->to] == 0) { indegree0.push_back(node->to); } node = node->next; } } return indegree0.size() < edges.size() - 1; } //利用bfs计算各个员工的奖金 int solve(const vector &edges) { int i; //记录各个结点的入度 vector indegree(edges.size(), 0); for (i = 1; i < edges.size(); ++i) { Node* node = edges[i].next; while (node) { indegree[node->to] ++; node = node->next; } } //记录入度为0的结点 vector tmp; for (i = 1; i < edges.size(); ++i) { if (indegree[i] == 0) { tmp.push_back(i); } }

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

课本习题一： ● 。证明:作映射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 )，

图论第二次作业

图论第二次作业一、第四章 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 的正整数

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

习题四： 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答案

离散数学作业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=是具有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 存在一条欧拉回路．． (1) 不正确，缺了一个条件，图G 应该是连通图，可以找出一个反例，比如图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 ）

图论及应用第一章完整作业

习题 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

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=是具有n 个结点的简单图，若在G 中每一对结点度数之和大于等于 n-1 ，则在G 中存在一条汉密尔顿路． 6．若图G=中具有一条汉密尔顿回路，则对于结点集V 的每个非空子集S ，在G 中删除S 中的所有结点得到的连通分支数为W ，则S 中结点数|S|与W 满足的关系式为 W ≤|S| ． 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 存在一条欧拉回路．．姓名：翟伟铮学号：1337001258063 得分：教师签名：

电子科大图论答案

图论第三次作业一、第六章 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