文档库 最新最全的文档下载
当前位置:文档库 › 图论第一次作业教学文案

图论第一次作业教学文案

图论第一次作业教学文案
图论第一次作业教学文案

习题一:

。 证明:作映射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 π

==≥≥

≥=∑是图序列的充要条件是:

1

1

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 的另一个连通分支中的一个顶点,

则 与 , 与 分别在

中连通,因此, 与 在 中连通。 ● 18.证明:若 ,则 . 证明:若 为 的割边,则 = ,若 为 的非割边,则 = ,所以,若 ,则有 .

习题二:

1.证明:非平凡树的最长路的起点和终点均是1度的。

证明设 是非平凡树T 中一条最长路,若 则 与 在 中的邻接点只能有一个,否则,若 与除了 中顶点之外的其他顶点相连,则 可以继续延长,这与 是最长路是相矛盾的。若 与 上的某顶点相连,则就构成了圈,这与数相矛盾,推出 不是最长路。即说明 与 是树叶,则 与 均是一度的。所以非平凡树的最长路的起点和终点均是 度的。

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

证明:证明:由于 是连通非平凡的且每个顶点度数为偶数,所以 中至少存在圈 ,从 中去掉 中的边,得到 的生成子图 ,若 没有边,则 的边集合能划分为圈。否则, 的每个非平凡分支是度数为偶数的连通图,于是又可以抽取一个圈。反复这样抽取, 最终划分为若干圈。

设 是 的边划分中的一个圈。若 仅由此圈组成,则 显然是闭迹。否则,由于 连通,所以,必然存在圈 ,它和 有公共顶点。于是, 是一条含有 与 的边的欧拉闭迹,如此拼接下去,得到包含 的所有边的一条闭迹.

16.Kruskal 算法能否用来求:

(1)赋权连通图中的最大权的树?

(2)赋权图中的最小权的最大森林?如果可以,怎样实现?

答:1、不能,由Kruskal 算法得到的任何生成树一定是最小生成树。

2、能

a.选择边e1使其权值最小

b.若已经选定边e1 e2 e3 ……ek ,则从E-{e1,e2,e3……ek},选择边ek+1 c .G[e1,e2,e3……ek]为无圈图,且可以不连通 d .ek+1的权值w (eK+1)尽可能小 e .当a 、b 、c 不能进行时,停止。

习题三:

1.证明: 是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2,使对任意 及 , G 中的路( , )必含 .

证明:必要性: 是 的割边,故 至少含有两个连通分支,设 是其中一个连通分支的顶点集, 是其余分支的顶点集,对12,u V v V ?∈?∈,因为 中的 不连通,而在 中 与 连通,所以 在每一条 路上, 中的 必含 。

充分性:取12,u V v V ∈∈,由假设 中所有 路均含有边 ,从而在 中不存在从 与到 的路,这表明 不连通,所以e 是割边。

3.设G 是阶大于2的连通图,证明下列命题等价: (1) G 是块

(2) G 无环且任意一个点和任意一条边都位于同一个圈上; (3)

图论作业(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

图论及其应用答案电子科大

图论及其应用答案电子科 大 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的块,则两条边的三个不同点在同一条路上。

电大离散数学作业答案(图论部分)

离散数学作业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 存在一条欧拉回

图论大作业

《图论及其应用》大作业 指导老师郝荣霞 知行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 。 ?即证

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

课本习题一: ● 。 证明:作映射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的另一个连通分支中的一个顶点,则与

图论第二次作业

第四章 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:解:设 作如下四条路: 故其四个生成圈如下:

图论 王树禾 答案

图论第一次作业 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个点的度数之和最大可能为

图论第二次作业

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

图论习题参考答案

二、应用题 题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)={, , , , } 试作图G 和图D ,写出各结点的度数,回答图G 、图D 是简单图还是多重图? 解: a d a d b c b c 图G 图D 例2图

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

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

图论第二次作业

图论第二次作业 一、第四章 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圈的图; (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 ,有 .

图论及其应用第三章答案电子科大

习题三: ● 证明: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)}

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

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

离散数学图论部分形成性考核书面作业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 是一个有孤立结点的图。

数学建模期末大作业

数学建模期末大作业论文 题目:A题美好的一天 组长:何曦(2014112739) 组员:李颖(2014112747)张楚良(2014112740) 班级:交通工程三班 指导老师:陈崇双

美好的一天 摘要 关键字:Dijkstra算法多目标规划有向赋权图 MATLAB SPSS

1 问题的重述 Hello!大家好,我是没头脑,住在西南宇宙大学巨偏远的新校区(节点22)。明天我一个外地同学来找我玩,TA叫不高兴,是个镁铝\帅锅,期待ing。我想陪TA在城里转转,当然是去些不怎么花钱的地方啦~~。目前想到的有林湾步行街(节点76)、郫郫公园(节点91),大川博物院(节点72)。交通嘛,只坐公交车好了,反正公交比较发达,你能想出来的路线都有车啊。另外,进城顺便办两件事,去老校区财务处一趟(节点50),还要去新东方(节点34)找我们宿舍老三,他抽奖中了两张电影票,我要霸占过来明晚吃了饭跟TA一起看。电影院嘛,TASHIWODE电影院(节点54)不错,比较便宜哈。我攒了很久的钱,订了明晚开心面馆(节点63)的烛光晚餐,额哈哈,为了TA,破费一下也是可以的哈。哦,对了,老三说了,他明天一整天都上课,只有中午休息的时候能接见我给我票。 我主要是想请教一下各位大神: 1)明天我应该怎么安排路线才能够让花在坐车上的时间最少? 2)考虑到可能堵车啊,TA比较没耐心啊,因为TA叫不高兴嘛。尤其是堵车啊,等车啊,这种事,万一影响了气氛就悲剧了。我感觉路口越密的地方越容易堵,如果考虑这个,又应该怎么安排路线呢? 3)我们城比较挫啊,连地图也没有,Z老师搞地图测绘的,他有地图,跟他要他不给,只给了我一个破表格(见附件,一个文件有两页啊),说“你自己画吧”。帮我画一张地图吧,最好能标明我们要去的那几个地方和比较省时的路线啊,拜托了~ 2 问题的分析 2.1 对问题一的分析 问题一要求安排路线使得坐车花费的时间最少。 对于问题一,假设公交车的速度维持不变,要使花费的时间最少,则将问题转化为对最短路径的求解。求解最短路径使用Dijkstra算法很容易进行求解,在运用MATLAB编程,得到最优的一条路径,则这条路径所对应的时间即为最少用时。 2.2 对问题二的分析 问题二要求在考虑堵车的情况下,路口越密越容易发生拥堵,安排路线是乘车时间最短。 对于问题二,在问题的基础上增加了附加因素,即公交车的速度会因道路的密集程度而发生改变,从而问题一建立的基本Dijkstra算法对于问题二就不再适用了,因此对问题一的基本Dijkstra算法进行改进,并结合蚁群算法的机理与特点,运用MATLAB求解出最短路径,保证了花费时间的最少性。 2.3 对问题三的分析 问题三要求根据提供的附件,画出一张地图,标明要去的那几个地方和比较省时的路线。 对于问题三,在问题一和问题二的基础上,根据求解的结果,运用SPSS软件画出地图。

2004图论复习题答案

图论复习题答案 一、 判断题,对打√,错打 1.无向完全图是正则图。( √ ) 2.零图是平凡图。( ) 3.连通图的补图是连通图. ( ) 4.非连通图的补图是非连通图。( ) 5.若连通无向简单图G中无圈,则每条边都是割边。( √ ) 6.若无向简单图G是(n,m)图,并且m=n-1,则G是树。( ) 7.任何树都至少有2片树叶。( ) 8.任何无向图G都至少有一个生成树。( ) 9.非平凡树是二分图。( √ ) 10.所有树叶的级均相同的二元树是完全二元树。( ) 11.任何一个位置二元树的树叶都对应唯一一个前缀码。( √ ) 12.3,3 K是欧拉图也是哈密顿图。( ) 13.二分图的对偶图是欧拉图。( ) 14.平面图的对偶图是连通图。( √ ) 15.设G*是平面图G的对偶图,则G*的面数等于G的顶点数。( )二、填空题 1.无向完全图K6有 15 条边。 2.有三个顶点的所有互不同构的简单无向图有 4 个。 3.设树T中有2个3度顶点和3个4度顶点,其余的顶点都是树叶,则T中有 10 片树叶。 4.若连通无向图G是(n,m)图,T是G的生成树,则基本割集 有 n-1 个,基本圈有 m-n+1 个。 5.设连通无向图G有k个奇顶点,要使G变成欧拉图,在G中至少要 加k / 2 条边。 6.连通无向图G是(n,m)图,若G是平面图,则G有m-n+2 个面。 三、解答题 1.有向图D如图1所示,利用D的邻接矩阵及其幂运算 求解下列问题: (1)D中长度等于3的通路和回路各有多少条。(2)求D的可达性矩阵。 (3)求D的强分图。 a b e 图1

解: (1) M=????????????????00010 1000000001 010******* M 2 =?? ?? ??? ? ??? ?????010******* 00010 1000001000 M 3=????????????????1000001000010000001010000 M 4=??????? ?????????0001001000100000100000010 由M 3可知,D 中长度等于3的通路有5条,长度等于3的回路有3条。 (2) I+M+M 2+M 3+M 4 =????????????? ???100000100000100 0001000001 +??????????? ?? ???000101000000001 010******* +??? ???? ? ??? ?? ???010000001000010 1000001000 + ????????????????1000001000010000001010000 +??? ?? ???????????0001001000100000100000010 = ??? ???? ? ????????21020 13010111110202011021 D 的可达性矩阵为 R=B (I+M+M 2+M 3+M 4 )=??? ???? ? ????? ???110101********* 1101011011 (3)R T =????????????????11111 1111100100 1111100101 R×R T =??? ???? ? ??? ?????11010 11010 001001101000001 由矩阵R×R T 可知,该有向图的强分图有:{a},{ b ,d ,e}, { c} a b e 图1

相关文档