图论第二章作业
5、生成树：包含了图中所有节点，且是不含回路的连通图。树枝数（m-1）与余树边（n-m+1）之和等于边数n，由n-m+1条余数弦形成n-m+1个基本回路。
9、基本关联矩阵的特征表示：矩阵内每行的非零元素表示与相应节点关联的分支，1表示流出该节点的分支，-1为流入节点的分支。矩阵每列仅有-1和1组成，分别对应该边的终点和始点，列中仅含有一个非零元素的对应边，即为与该参考点相连的分支。
与生成树的关系：连通图G的基本关联矩阵B的一个大子阵是非奇异的充要条件为与这个大子阵的列相应的边，组成G的一棵生成树。
10、基本回路矩阵的每行对应一个独立回路，一个连通图（m，n）的基本回路数为（n-m+1），互异回路数为（2^n-m+1）。
11、基本割集矩阵表示出了生成树的基本割集，基本割集矩阵S的一个大子阵是非奇异的充要条件是这个大子阵的列对应于图的某生成树的树枝。
14、试述破圈法、加边法、收缩法求最小生成树的思路与步骤，并比较其优缺点和使用条件。
破圈法：
一、思路
在一个连通图中，逐次去掉一些边，以破除图中所有回路，则剩下的不含回路的连通图就是图的一棵生成树。如需选择最小树，每次去掉的边应是被破回路中权最大者；如需选最大树，则逐次去掉的边应是被破回路中权最小者；若每次去掉的是任意的一条边，则最后得到一棵任意树。
二、步骤
(1) 画网路图，将点、边编号，标出风向。
(2) 确定图的余树弦数(即独立回路数)
(3) 将分支按权大小排序。
(4) 从权最大的分支起，依次从图中除去，移去后被破坏的回路，即可能是独立回路。若被破坏的回路中，有一条以上高阻分支，应重选；
(5) 重复(4)，直到移去n－m＋1条余树弦，剩余的分支即组成最小风阻树T min；
三、优缺点
该法简单、易懂
四、使用条件
适于不太复杂的图
加边法：
一、思路
在图中任取一条边，找一条不与构成回路的边相连，然后再找一条不与构成回路的边相连，如此继续，直到此过程不能进行，这时所得的图就是一棵生成树，若加入的边总是权小的边，可得一最小树；若加入的边总是权大的边，则得最大树；如任意加边，则得一任意树。
二、步骤
(1) 将图去边留点；
(2) 将分支按权排序；
(3) 加边，即按一定顺序将边加到图中原位置。选最大树时，按权从大到小依次将边加入；选最小树时，按权从小到大依次将边加入。每加入一条边都要判断是否构成回路，若新加入的边与已有边构成回路，则这条边就是余树弦，将它取走，计入余树弦集合；若新加入的边与已加入的边未构成回路，说明它是树枝，计入树枝集合；
(4) 重复(3)，将所有边都加过后，取走n－m＋1条余树弦，剩余的(m—1)条边，即构成一棵生成树。
三、优缺点
该法方便易行，简单易懂。
四、使用条件
可以手工解算，也可以计算机解算。
收缩法：
一、思路及步骤
(1) 绘网路图，将节点、分支编号，并标出风向；
(2) 计算生成树枝数和独立回路数，并将边按权大小排序；
(3) 从权最小的分支起，由始点向终点收缩(始点与最小权分支被收缩)，将此分支号授于所有与其始点连接的分支，如某分支号重复出现，则消去此分支号；(4) 如收缩边始末点合一，即构成一个回路。此始末点合一的分支，即为余树弦，将其计入余树弦集；
(5) 如未形成回路，则依次收缩权较小的分支；
(6) 重复(5)，直到最后一个节点。收缩过程中始末点合一的分支即为余树弦，去掉余树弦后剩余的子图即为最小生成树。收缩过程中形成的回路，即为相应的独立回路。
如需选择最大树，应从最大权分支开始，依次收缩高权分支即可。对任意连通图，如其顶点为m，则需收缩(m－1)次。
二、优缺点
此法较复杂，不适于手算
三、使用条件
适用于较为额复杂的网络图，适用于电脑解算。
电大离散数学作业答案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=
图论作业(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
图论第二次作业
第四章 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：解：设 作如下四条路： 故其四个生成圈如下：
图论大作业
《图论及其应用》大作业 指导老师郝荣霞 知行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 )，
图论讲义第2章-连通性
第二章 图的连通性 在第一章中已经定义连通图是任二顶点间都有路相连的图。对于连通图，其连通的程度也有高有低。例如，下列三个图都是连通图。对于图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 ，有 .
图论第二次作业
图论第二次作业 一、第四章 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答案
离散数学作业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答案
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)
电大离散数学作业答案作业答案
电大离散数学作业答案作 业答案 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=
电子科大图论-第二次作业(4、5章)-答案
习题四 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!)，命题得证。
图论讲义2连通性
第二章 图的连通性 连通图：任二顶点间有路相连。 例 可见在连通图中，连通的程度也是有高有低。 本章的目的就是定义一种参数来度量连通图连通程度的高低。 §2.1 割边、割点与连通度 一、割点： 定义2.1.1 设)(G V v ∈，如果)()(G w v G w >?，则称v 为G 的一个割点。（该定义与某些著作有所不同，主要是在有环边的顶点是否算作割点上有区别）。 例 定理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 是割点。证毕。 推论2.1.2 每个非平凡无环连通图至少有两个顶点不是割点。 证明：设T 是G 的生成树，则T 至少有两个叶子u ,v ，由上一定理知，u ,v 都不是T 的割点，即1)()(==?T w u T w 。由于u T ?是图u G ?的生成树，故 )(1)()()(G w T w u T w u G w ===?=?，