图论第二次作业

图论第二次作业一、第四章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离散数学图论部分形成性考核书面作业本课程形成性考核书面作业共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=<V ，E >是具有n 个结点的简单图，若在G 中每一对结点度数之和大于等于 n-1 ，则在G 中存在一条汉密尔顿路．6．若图G=<V , E>中具有一条汉密尔顿回路，则对于结点集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. 习题：给定一个无向图G=(V,E)，其中V={1,2,3,4,5,6}，E={(1,2),(1,3),(2,3),(2,4),(3,4),(4,5),(4,6)}，求图G的邻接矩阵和关联矩阵。

答案：邻接矩阵是一个n×n的矩阵，其中n是图的顶点数。

对于无向图G，邻接矩阵的元素a[i][j]表示顶点i和顶点j之间是否存在边。

如果存在边，则a[i][j]=1，否则a[i][j]=0。

对于给定的图G，邻接矩阵为：0 1 1 0 0 01 0 1 1 0 01 1 0 1 0 00 1 1 0 1 10 0 0 1 0 00 0 0 1 0 0关联矩阵是一个n×m的矩阵，其中n是图的顶点数，m是图的边数。

对于无向图G，关联矩阵的元素b[i][j]表示顶点i和边j之间的关系。

如果顶点i是边j 的起点，则b[i][j]=-1；如果顶点i是边j的终点，则b[i][j]=1；否则b[i][j]=0。

对于给定的图G，关联矩阵为：-1 -1 0 0 0 01 0 -1 -1 0 00 1 1 0 0 00 0 0 1 -1 -10 0 0 0 1 00 0 0 0 0 12. 习题：给定一个有向图G=(V,E)，其中V={1,2,3,4,5}，E={(1,2),(1,3),(2,3),(2,4),(3,4),(4,1),(5,4)}，求图G的邻接表和深度优先搜索遍历结果。

答案：邻接表是一种图的表示方法，用于存储图中每个顶点的邻接顶点。

对于有向图G，邻接表中的每个元素表示该顶点的出边。

对于给定的图G，邻接表为：1: 2, 32: 3, 43: 44: 15: 4深度优先搜索（DFS）是一种图的遍历算法，用于遍历图中的所有顶点。

离散数学形成性考核作业（二） 图论部分本课程形成性考核作业共4次，内容由中央电大确定、内容由中央电大确定、统一布置。

统一布置。

本次形考作业是第二次作业，大家要认真及时地完成图论部分的形考作业，字迹工整，次作业，大家要认真及时地完成图论部分的形考作业，字迹工整，抄写题目，抄写题目，抄写题目，解答题有解答解答题有解答过程。

过程。

第3章 图的基本概念与性质1．计算出下图2.1的结点数与边数，并说明其满足握手定理．的结点数与边数，并说明其满足握手定理．图2.1 习题1的图的图2．试分别画出下列图2.2(a )、(b )、(c )的补图．的补图．图2.2 习题2的图的图3．找出下图2.3中的路、通路与圈．中的路、通路与圈．图2.3 习题3的图的图4．设G 为无向图，|G |=9，且G 每个结点的度数为5或6，试证明G 中至少有5个6度结点或至少有6个5度结点．度结点．5．设有向图D =<V ,E >如图2.4所示，所示，图2.4 习题5的图的图 试问图中是否存在长度分别为3, 4, 5, 6的回路，如存在，试找出．的回路，如存在，试找出．的回路，如存在，试找出．6．若无向图G 有10条边，3度与4度结点均2个，其余结点的度数均小于3，试问G中至少有几个结点？若无向图G 中有6条边，3度与5度结点均有一个，其余结点的度数均是2，试问G 中有几个结点? 7．试求图2.5中有向图的强分图，单侧分图和弱分图．中有向图的强分图，单侧分图和弱分图．的图图2.5 习题7的图8．试说明图2.6中G1和G2同构．同构．G1G2图2.6 习题8的图9．试求图2.7中的邻接矩阵与可达矩阵．中的邻接矩阵与可达矩阵．图2.7 习题9的图10．有n个结点的无向完全图的边数为个结点的无向完全图的边数为 ．11．图中度数为奇数的结点为数个． ．图中度数为奇数的结点为 数个．12．已知图G的邻接矩阵为的邻接矩阵为，有（ ）．则G有（A．5点，8边B．6点，7边C．5点，7边D．6点，8边第4章几种特殊图1．试分别构造满足下列条件的无向欧拉图．试分别构造满足下列条件的无向欧拉图（1）有偶数个结点，奇数条边．）有偶数个结点，奇数条边．）有偶数个结点，偶数条边．（2）有偶数个结点，偶数条边．）有奇数个结点，偶数条边．（3）有奇数个结点，偶数条边．）有奇数个结点，奇数条边．（4）有奇数个结点，奇数条边．2．分别构造满足下列条件的四个汉密尔顿图．分别构造满足下列条件的四个汉密尔顿图）偶数个结点，奇数条边．（1）偶数个结点，奇数条边．（2）有偶数个结点，偶数条边．）有偶数个结点，偶数条边．）有奇数个结点，偶数条边．（3）有奇数个结点，偶数条边．（4）有奇数个结点，奇数条边．）有奇数个结点，奇数条边．3．试画出一个没有一条欧拉回路，但有一条汉密尔顿回路的图．．试画出一个没有一条欧拉回路，但有一条汉密尔顿回路的图． 4．如图2.8是否为欧拉图？试说明理由．是否为欧拉图？试说明理由．判断是否为欧拉图图2.8 判断是否为欧拉图5．如图2.9是否为汉密尔顿图？试说明理由．是否为汉密尔顿图？试说明理由．判断是否为汉密尔顿图图2.9 判断是否为汉密尔顿图6．试分别说明图4.3（a）、（b）与（c）是否为平面图．）是否为平面图．判断是否为平面图图2.10 判断是否为平面图7．试分别求出图2.11（a）、（b）与（c）的每个图的面的次数．）的每个图的面的次数．求面的次数图2.11 求面的次数8．试利用韦尔奇·鲍威尔算法分别对图2.12（a）、（b）与（c）着色．）着色．图2.12 图的着色中那些是树，那些是森林，并说明理由．．试指出图2.13中那些是树，那些是森林，并说明理由．图2.13 习题1的图中的一个生成树，并说明其中的树枝、弦，以及对应生成树的补．中的一个生成树，并说明其中的树枝、弦，以及对应生成树的补．图2.14 习题2的图的所有不同构的生成树．的完全图K5 的所有不同构的生成树．图2.15 习题3的图中的最小生成树及其权值．中的最小生成树及其权值．图2.16 习题4的图结点？结点？A．1 B．2 C．3 D．4 7．无向树T有3个3度结点,2个4度结点,其余的都是树叶，则T（有（ ）片树叶？）片树叶？A．3 B．7 C．9 D．11 8．无向树T有1个2度结点,3个3度结点,4个4度结点,1个5度结点,其余的都是树叶，）片树叶？有（ ）片树叶？则T有（A．12 B．14 C．16 D．20 9．无向树T有9片树叶,5个3度结点,其余的都是4度结点，则T有几个4度结点？度结点？A．0 B．1 C．2 D．3 。

)3( 题属中国邮路问题除第欧拉图与哈密尔顿图<1.>给定一个由16条线段构成的图形（见下图）.证明：不能引一条折线与每一线段恰好相交一次（折线可以是不封闭的和自由相交的，但他的顶点不在给定的线段上）证明：建立一个图G ：顶点i v 代表图形的区域(1,2,3,4,5,6)i X i ，顶点i v 与j v 之间连接的边数等于区域i X 与j X 公共线段的数目.于是，将上图的区域和边可转化成下图：由顶点度数知不存在欧拉路，从1X 到6X 只能相交于外面的两条线段.<2.>下列图形中哪些能一笔画成.解：只需考虑该图是否有欧拉路（即有两个奇点或者无奇点），故第一个和第三个可以一笔画成，第二个不能一笔画成.<4.>下图是某个展览馆的平面图，其中每个相邻的展览室有门相通.证明：不存在一条从A 进入，经过每个展览室恰好一次再从A 处出来的参观路线.证：用顶点代表展览室，两顶点相邻当且仅当这两点所对应的展览室有门相通，则可得一个连通简单图G （见下图）.因此，只要证明G 中不存在H —回路即可.具体理由如下：令}{1216,,,S y y y = ，则显然S 是G 的真子集，而()1816G S S ω-=>=（x 共18个，y 共16个），故由讲义中定理2.3知不存在H —回路.<5.>某次会议有20人参加，其中每个人都至少有10个朋友.这20人围一桌入座，要想使与每个人相邻的两位都是朋友是否可能？解:用顶点代表人，两人是朋友时相应顶点间连一边，得到一个无向图(,)G V E =.只要证明G 中存在H —回路即可. G 是10阶连通图，对于20n =，且()10,()10G G d u d v ≥≥，可得：()()20G G d u d v n +≥=，故由讲义中定理2.4知G 中存在H —回路.<6.>已知,,,,,,a b c d e f g 七个人中，a 会讲英语，b 会讲英语和汉语，c 会讲英语、意大利语和俄语，d 会讲汉语和日语，e 会讲意大利语和德语，f 会讲俄语、日语和法语，g 会讲德语和法语.能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈.解：用七个顶点表示这七个人.若两人能交谈（会讲同一种语言），就在这两顶点之间连一条边，得到图G .只要证明图G 中存在H -回路即可. 具体结果如下：c e g f d b a c 意大利语德语法语日语汉语英语英语 .<7.>设G 是分划为,X Y 的二部图，且X Y ≠，则G 一定不是H —图。

离散数学图论部分形成性考核书面作业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=<V ，E >是具有n 个结点的简单图，若在G 中每一对结点度数之和大于等于 n-1 ，则在G 中存在一条汉密尔顿路．6．若图G=<V , E>中具有一条汉密尔顿回路，则对于结点集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 关系的无向连通图就是树．姓 名： 学 号： 得 分： 教师签名：4．设G是一个有7个结点16条边的连通图，则G为平面图．解：(1) 错误假设图G是连通的平面图，根据定理，结点数v，边数为e，应满足e小于等于3v-6，但现在16小于等于3*7-6，显示不成立。

所以假设错误。

5．设G是一个连通平面图，且有6个结点11条边，则G有7个面．(2) 正确根据欧拉定理，有v-e+r=2，边数v=11，结点数e=6，代入公式求出面数r=7三、计算题1．设G=<V，E>，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，试(1) 给出G的图形表示；(2) 写出其邻接矩阵；(3) 求出每个结点的度数；(4) 画出其补图的图形．解：(1)οοοοvοv vv v(2) 邻接矩阵为⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛0110010110110110110000100(3) v 1结点度数为1，v 2结点度数为2，v 3结点度数为3，v 4结点度数为2，v 5结点度数为2(4) 补图图形为2．图G =<V , E >，其中V ={ a , b , c , d , e }，E ={ (a , b ), (a , c ), (a , e ), (b , d ), (b , e ),(c , e ), (c , d ), (d , e ) }，对应边的权值依次为2、1、2、3、6、1、4及5，试（1）画出G 的图形； （2）写出G 的邻接矩阵； （3）求出G 权最小的生成树及其权值． （1）G 的图形如下：οο ο οv οv v vv（2）写出G的邻接矩阵（3）G权最小的生成树及其权值3．已知带权图G如右图所示．(1) 求图G的最小生成树；(2)计算该生成树的权值．解：(1) 最小生成树为(2) 该生成树的权值为(1+2+3+5+7)=184．设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优二叉树的权．12357权为 2*5+3*5+5*4+7*3+17*2+31=131四、证明题1．设G 是一个n 阶无向简单图，n 是大于等于3的奇数．证明图G 与它的补图G 中的奇数度顶点个数相等．证明：设,G V E =<>，,G V E '=<>．则E '是由n 阶无向完全图n K 的边删去E 所得到的．所以对于任意结点u V ∈，u 在G 和G 中的度数之和等于u 在n K 中的度数．由于n 是大于等于3的奇数，从而n K 的每个结点都是偶数度的（ 1 (2)n -≥度），于是若u V ∈在G 中是奇数度结点，则它在G 中也是奇数度结点．故图G 与它的补图G 中的奇数度结点个数相等．35251717311362．设连通图G 有k 个奇数度的结点，证明在图G 中至少要添加2k条边才能使其成为欧拉图．证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k 是偶数． 又根据定理4.1.1的推论，图G 是欧拉图的充分必要条件是图G 不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G 的所有结点的度数变为偶数，成为欧拉图．故最少要加2k条边到图G 才能使其成为欧拉图．。

图论第二版答案【篇一：图论与代数结构第一二三章习题解答】厂为一结点；若两个工厂之间有业务联系，则此两点之间用边相联；这样就得到一个无向图。

若每点的度数为3，则总度数为27，与图的总度数总是偶数的性质矛盾。

若仅有四个点的度数为偶数，则其余五个点度数均为奇数，从而总度数为奇数，仍与图的总度数总是偶数的性质矛盾。

（或者利用度数为奇数的点的个数必须为偶数个） 2. 若存在孤立点，则m不超过kn-1的边数, 故m = (n-1)(n-2)/2, 与题设矛盾。

?－3. 记ai为结点vi的正度数，ai为结点vi的负度数，则nnnn? 2? 22－ai?[(n?1)?ai]?n(n?1)?2(n?1)ai＋ai－2， i?1i?1i?1i?1 nnn－2? 2 因为ai?cn?n(n?1)/2，所以ai?ai－ 2。

i?1i?1i?14. 用向量(a1,a2,a3)表示三个量杯中水的量, 其中ai为第i杯中水的量, i = 1,2,3.以满足a1+a2+a3 = 8 (a1,a2,a3为非负整数)的所有向量作为各结点, 如果(a1,a2,a3)中某杯的水倒满另一杯得到( a’1, a’2, a’3 ) , 则由结点到结点画一条有向边。

这样可得一个有向图。

本题即为在此图中找一条由( 8, 0, 0 )到( 4, 4, 0 )的一条有向路，以下即是这样的一条： ( 8, 0, 0 ) ( 5, 0, 3 ) ( 5, 3, 0 ) ( 2, 3, 3 ) ( 2, 5,1 )(7, 0, 1 ) ( 7, 1, 0 ) ( 4, 1, 3 ) ( 4, 4, 0 )5. 可以。

???????6 若9个人中没有4个人相互认识，构造图g，每个点代表一个点，两个人相互认识则对应的两个点之间有边。

1）若可以找到点v，d(v)5，则与v相连的6个点中，要么有3个相互认识，要么有3个相互不认识（作k6并给边涂色:红=认识，蓝=不认识，只要证图中必有同色三角形。

图论及其应用第二次作业要求：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)21111(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 )。

图论第二次作业一、第四章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 ,使得E(G)=E(C 1) E(C 2) ..... E(C m )。

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

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

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

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

图论作业 1⼀、填空题1. ⾮同构的阶和阶树的个数分别为和⽅法：按照树中存在的最⻓路进⾏枚举 (从开始)注意：对于的树来说，路的最短⻓度为234 阶树2345 阶树2. 阶正则图的补图的边数为考点⼀：完全图每个点的度数是✨考点⼆：⼀个图和其补图的并是完全图⼀个点在原图和补图中的度数和为图是正则，那么图的补图为正则。

故补图的度数之和为根据握⼿定理：3. 设图中各顶点度数均为，且，则 n = ，m =考点：握⼿定理根据握⼿定理：4. 设简单图的邻接矩阵为，且则图的边数为考点：邻接矩阵的性质定理 10：令是⼀个有推⼴邻接矩阵的阶标定图，则的⾏列元素等于由到的⻓度为的途径的数⽬推论：设为简单图的邻接矩阵，则：的元素是的度数。

的元素是含的三⻆形的数⽬的两倍 （考过填空）5. 设是⼀个完全部图，是第部分的顶点数，则它的边数为考点：完全多部图的概念与结构完全部图的点数：；边数：（考过填空）6. 设是阶简单图，且不含完全⼦图，则其边数⼀定不会超过考点：Turán 定理定理 18 (T urán)：若是阶简单图，并且不包含，则边数。

此外，仅当时，✨计算公式：，则例：阶简单图，，则最多有条边例： 9 阶简单图，，则最多有 27 条边7. 设阶图是具有个分⽀的森林，则其边数为树的边数 = 顶点数 - 1森林的边数 = 顶点数 - 连通分⽀数8. ⼀棵树有个度为的结点，，则它有个度数为的顶点考点：握⼿定理 + 树的性质（边数 = 顶点数 - 1），其中由握⼿定理：故：整理得：9. 完全图的⽣成树的个数为定理 27：⼆、不定项选择题1. 关于图的度序列，下列命题正确的是（ABCD）A. 同构的两个图的度序列相同B. ⾮负整数序列是图的度序列当且仅当是偶数C. 如果正整数序列是⼀棵树的度序列且，那么序列中⾄少有两个D. 正整数序列是⾮平凡树的度序列当且仅当E. 若图的顶点度数之和⼤于等于图的顶点度数之和，则图度优于图❌F. 如果⾮负整数序列是简单图的度序列，那么在同构意义下只能确定⼀个图❌考点：度序列 && 图序列关系：简单图的度序列简称图序列注意：判断⾮负整数序列是否为简单图的度序列暂⽆好的⽅法，只有等价转换的⽅法A 显然正确（已经默认递增或递减排列）B 正确：定理 3：⾮负整数组是图的度序列的充分必要条件是：为偶数C 正确：定理 20：每棵⾮平凡树⾄少有两⽚树叶D 正确：存在⼀棵⾮平凡树，以该序列为度序列的充要条件握⼿定理E 错误：先有度弱或度优，才有度数之和⼩于或⼤于；反过来不成⽴F 错误：不⽌确定⼀个图2. 对于序列，下列说法正确的是（BD）A. 可能是简单图的度序列❌B. ⼀定不是简单图的度序列C. 只能是简单图的度序列❌D. 只能是⾮简单图的度序列E. 不是任意图的度序列❌考点：度序列 && 图序列对于简单图，顶点的最⼤度顶点数 - 1A 错B 对C 错：对于该题，⻓度为 6，说明有 6 个点，同时最⼤度为 7，显然不是简单图！！D 对E 错：定理 3：⾮负整数组是图的度序列的充分必要条件是：为偶数3. 下列说法错误的是（ACE）A. 若⼀个图中存在闭途径，则⼀定存在圈❌B. 偶图中不存在奇圈C. 若图不含三⻆形，则为偶图❌D. 图的顶点之间的连通关系⼀定是等价关系E. 存在每个顶点的度数互不相同的⾮平凡简单图❌A 错误：闭途径（），但不存在圈B 正确：定理 9：⼀个图是偶图当且仅当它不包含奇圈C 错误：可能存在⻓度不为 3 的奇圈，如 5，7 等等D 正确：即便在有向图中，也存在弱连通E 错误：定理 5：⼀个简单图的个点的度不能互不相同4. 关于简单图的邻接矩阵，下列说法错误的是（C）A. 矩阵的⾏和等于该⾏对应顶点的度数B. 矩阵的所有元素之和等于该图边数的倍C. 矩阵的所有特征值之和等于该图边数的倍❌D. 矩阵的所有特征值的平⽅和等于该图边数的倍E. 矩阵的主对⻆线的元素之和等于该图边数的倍F. 若是⾮连通图，则相似于某个准对⻆矩阵考点：简单图邻接矩阵的性质A 正确：矩阵的「⾏和」或「列和」等于该「⾏」或「列」对应顶点的度数B 正确：所有元素之和等于度数之和，根据握⼿定理判断正确C 错误：矩阵的所有特征值之和等于矩阵的迹；矩阵的迹⼜是矩阵主对⻆线上的元素之和；对于简单图，邻接矩阵主对⻆线元素均为D 正确：所有特征值的平⽅和等于的所有特征值之和；的迹就是主对⻆线之和，也就是图的所有度数之和，就等于边数的两倍E 显然正确F 正确：⽆法解释，因为不懂5. 图⼀定是树的是（BDE）A. 连通图❌B. ⽆回路但任意添加⼀条边后有回路的图C. 每对顶点间都有路的图❌D. 连通且E. ⽆圈且考点：树的基本性质A 错误：树是连通的⽆圈图B 正确：回路是边不重圈的并；⽆回路肯定⽆圈，加⼀条边有回路，肯定就有圈C 错误：每对顶点间存在唯⼀的⼀条路DE 显然正确三、解答题1. 设⽆向图 有条边， 度与 度顶点各 个，其余顶点度数均⼩于 ，问 中⾄少有⼏个顶点？在顶点数最少的情况下，写出 的度序列，该度序列是⼀个图序列吗？考点：握⼿定理 + 图序列解：由于求顶点数量最少，故假设 0 度顶点为 0 个，1 度顶点为 0 个，同时设 2 度顶点有 个根据握⼿定理得：；解得：所以 中⾄少有 7 个顶点；图 的度序列为 根据 Havel-Hakimi 定理，可得下⾯推导过程：显然 是可图的，所以 是可图的2. 证明整数序列是简单图的度序列，并构造⼀个对应的简单图。

离散数学作业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=<V ，E >是具有n 个结点的简单图，若在G 中每一对结点度数之和大于等于 n-1 ，则在G 中存在一条汉密尔顿路．姓 名： 学 号：得 分：6．若图G=<V, E>中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为W(G-V1) V1．有n个结点(n2)，m条边，当n为奇数时，7．设完全图KnK中存在欧拉回路．n8．结点数v与边数e满足e=v-1 关系的无向连通图就是树．9．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去4 条边后使之变成树．10．设正则5叉树的树叶数为17，则分支数为i = 5 ．二、判断说明题（判断下列各题，并说明理由．）1．如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路．．(1) 不正确，缺了一个条件，图G应该是连通图，可以找出一个反例，比如图G是一个有孤立结点的图。

2．如下图所示的图G存在一条欧拉回路．(2) 不正确，图中有奇数度结点，所以不存在是欧拉回路。

习题43．解：（1）：（2）：（3）：（4）：7.证明：将G中孤立点除去后的图记G1，则G1也无奇数度点，且δ（G1）>=2,从而可知G1有一个圈C1，在图G1-C1中去孤立点，得图G2；显然G2仍无奇数点，且δ（G2）>=2,所以G2中有一圈C2，如此下去,直至Gm中有圈Cm,且Gm-Cm全为孤立点为止。

于是E(G)=E(C1)∪E(C2)∪....∪E(Cm).10.证明：（1）若G不是2连通的，则G不连通或存在割点v,有ω（G-X）>=2，由定理知G是非Hamilton 图（2）设G是2部图，其划分为（X,Y）,且|X|<|Y|,则有ω（G-X）=|Y|>|X|,由定理知G是非Hamilton图。

12.证明：对G 加入一个新顶点v ，它和G 中的每一个顶点均相连，所得之图记为G1，于是G1的度序列为（d1+1,d2+1,.....,dv+1,v ）,由已知条件可知，不存在m<(v+1)/2,它满足dm<=m 和dv-m+1<v-m,即不存在m<(v+1)/2,它满足dm+1<=m 和dv-m+1<v-m=（v+!）-m.由定理8知，G1中含有Hamilton 圈C ，显然G1-V 是G 中的Hamilton 路。

习题51.（1）证明：设k 方体顶点坐标为(x1 ,x2,…,xk),我们取(x1 ,x2,…,xk-1,0),和(x1 ,x2,…,xk-1,1) 之间的全体边所成之集为M.显然，M 中的边均不相邻接，所以M 是一个匹配，又容易知道：|M|=2k-1.因为k 方体的顶点数是2k ,所以k 方体中的每一个顶点都是M-饱和的，所以M 是完美匹配。

（2）解：K 2n 的任意一个顶点有2n-1种不同的方法被匹配，一旦选定某一边属于M 之后，剩下(2n-1)个顶点,它们的导出子图是K 2（n-1）如此推下去，可以归纳出K 2n 的不同完美匹配个数为：(2n-1)!!同样的推导方法可归纳出K n, n 的不同完美匹配个数为：n!2.证明：假设原命题不成立，设M1与M2是树T 的两个不同的完美匹配，那么M1ΔM2≠Φ,容易知道：T[M1ΔM2]每个非空部分顶点度数为2，即它包含圈，这和T 是树矛盾。

图论第二次作业一、第四章(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 l,C l, ・；C m，使得E(G) E(C i) EG) ??? E(C m)。

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

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

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

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

设G是有度序列(d1,d2, ,d n)的非平凡简单图，这里d1 d2 d n，证明：若不存在小于° U的正整数m，使得d m m且d n m 1 n m，则G有Hamliton2证明：在G之外加上一个新点v,把它和G的其余各点连接，得图G1：G i的度序列为：（d i 1,d2 1, ,d n 1,n），由已知：不存在小于卫的正整数m,使得2d m 1 m且d n m i 1 n m i （n i） m。

离散数学作业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=<V ，E >是具有n 个结点的简朴图，若在G 中每一对结点度数之和大于等于 n-1 ，则在G 中存在一条汉密尔顿路．姓 名：学 号：6．若图G=<V, E>中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为W(G-V1) ≤∣V1∣．7．设完全图Kn 有n个结点(n≥2)，m条边，当n为奇数时，Kn中存在欧拉回路．8．结点数v与边数e满足e=v-1 关系的无向连通图就是树．9．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去4 条边后使之变成树．10．设正则5叉树的树叶数为17，则分支数为i = 5 ．二、判断说明题（判断下列各题，并说明理由．）1．假如图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路．．(1) 不对的，缺了一个条件，图G应当是连通图，可以找出一个反例，比如图G是一个有孤立结点的图。

2．如下图所示的图G存在一条欧拉回路．(2) 不对的，图中有奇数度结点，所以不存在是欧拉回路。

图论及其应用第2章答案（电子科大版）
习题二(yangchun)：
7.证明：非平凡树的最长路的起点和终点均是1度的。

证明设是非平凡树T中一条最长路，若则与在中的邻接点只能有一个，否则，若与除了中顶点之外的其他顶点相连，则可以继续延长，这与是最长路是相矛盾的。

若与上的某顶点相连，则就构成了圈，这与数相矛盾，推出不是最长路。

即说明与是树叶，则与均是一
度的。

所以非平凡树的最长路的起点和终点均是度的。

9.证明：顶点度数为偶数的连通图本身可构成一个包含所有边的闭迹。

证明：证明：由于是连通非平凡的且每个顶点度数为偶数，所以中至少
存在圈,从中去掉中的边，得到的生成子图,若没有边，则的边集合能划分为圈。

否则，的每个度数均为偶数的连通图，反复这样抽取，最终划分为若干圈。

设是的边划分中的一个圈。

若仅由此圈组成，则显然是闭迹。

否则，由于连通，所以，必然存有公共顶点。

于是，是一条含有与的边的迹，如此拼接下去，得到包含的所有边的一条闭迹.
16.Kruskal算法能否用来求：
（1）赋权连通图中的最大权的树？
（2）赋权图中的最小权的最大森林？如果可以，怎样实现？
答：1、不能，由Kruskal算法得到的任何生成树一定是最小生成树。

2、能。