资源描述：
《离散作业布置及讲评(5).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、闽南师范大学计算机学院2014年11月第五部分组合数学作业作业讲评14-5设无向图有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G中至少有几个顶点？在最少顶点情况下，写出G的度数列，(G),(G)解：设G的阶数为n,已知有2个3度顶点和2个4度顶点，其余n-4个顶点的度数均小于或等于2，由握手定理得2m=20<=2*3+2*4+(n-4)*2=2n+6解得n>=7,即G中至少有7个顶点，当D有7个顶点时，其度数列为2，2，2，3，3，4，4，(G)=4，(G)=3作业讲评14-15下列各数列中哪些是可简单图化的？对于简单图化的试给出两个非同构的简单图。(2)(1
2、,1,2,2,3,3,5,5)(3)(2,2,2,2,3,3)解：(2)可简单图化(3)可简单图化作业讲评14-21无向图G如图所示，求(1)求G图的全部点割集和边集，并指出其中的割点和桥（割边）(2)求G的点连通度k(G)和边连通度(G)解:(1)点割集2个：{a,c},{d},其中d是割点，边割集有7个：{e5},{e1e3}{e2e4}{e1e2}{e2e3}{e3e4}{e1e4}，其中是e5桥。(2)因为既有割点又有桥，所以k==1作业讲评14-15下列各数列中哪些是可简单图化的？对于简单图化的试给出两个非同构的简单图。(1)(2,3,3,5,5,6,6)解：(1)(2
3、,3,3,5,5,6,6)不可简单图化。（反证法）假设存在无向简单图G以它为度数列设d(v1)=2,d(v2)=d(v3)=3,d(v4)=d(v5)=5,d(v6)=d(v7)=6,由于只有7个顶点，v6，v7必与v1，…v5均相邻，v6与v7也相邻，因为d(v1)=2,故v1不能再与v2，…v5相邻，于是，要满足v4，v5的度数，它们必须与v2，v3均相邻，从而d(v2)>=4,d(v3)>=4,这与d(v2)=d(v3)=3矛盾作业讲评14-41设G是无向图简单图，(G)>=2,证明G中存在长度大于或等于(G)+1的圈。证明：用扩大路径法证明。设=v0v1…vl为极大路径
4、（可用扩大路径法得到），则l>=(G)由极大路径的性质（的两个端点v0与v0不与外顶点相邻）以及简单图的定义可知，v0要达到其度数d(v0)>=(G),必须与上至少(G)个顶点相邻，设其为vi1=v1,vi2,…,vi于是，圈v0vi1,…,vi2…,viv0,长度大于或等于(G)+1，式中=(G)，参见例14.8作业讲评14-25画出5阶3条边的所有非同构的无向简单图解：3条边产生6度，分配给5个顶点，按简单图度数的要求，有4种分配方案：(1)1,1,1,1,2(2)0,1,1,2,2(3)0,1,1,1,3(4)0,0,2,2,2在同构意义下，每种方案对应一
5、个简单图，4个非同构的图如下图实线边所示：作业讲评14-29设G是n阶n+1条边的无向图，证明G中存在顶点v，使得d(v)>=3解:反证法假设不然，∀vV(G),均有d(v)<=2,则由握手定理可得2n+2=2m<=2n,其中m为边数这显然是矛盾的。作业讲评14-43有向图D，如图所示(1)D中有多少种非同构的圈？有多少种非同构的简单回路？(2)求a到d的短程线和距离d(3)求d到a的短程线和距离d解:(1)有2种非同构的圈:ede,aeba,长度分别为2与3;有3种非同构的简单回路:ede,aeba,aedeba,长度分别为2，3，5(2)a到d的短程线为ae
6、d,d=2(3)d到a的短程线为deba,d=3作业讲评14-43(4)判断D中是哪类连通图？(5)对D的基图求解(1),(2),(3)解:(4)D中存在经过每个顶点的通路，但不存在经过每个顶点的回路，所以D是单向连通图。(5)I.D的基图中有4种非同构的圈:ede,aeba,aedba,aedcba，长度分别为2，3，4，5，有7种非同构的简单回路，其中除4种非同构的圈之外，还有3种非圈的简单回路:aedeba,aebdcba,aedebdcba,长度分别为5，6，8；II.a到d的短程线有3条，d=2 III.d到a的短程线有3条，d=2作
7、业讲评14-44有向图如图所示，(1)D中v1到v4长度为1,2,3,4的通路各为几条?(2)D中v1到v1长度为1,2,3,4的通路各为几条?(3)D中长度为4的通路有多少条，其中长为4的回路为多少条？(4)D中长度小于或等于4的通路为多少条？其中多少条为回路？(5)写出D的矩阵。作业讲评14-44解：利用D的邻接矩阵的前4次幂作业讲评(1)v1到v4长度为1,2,3,4的通路数分别为0,0,2,2.即a14=0,a14(2)=0,a14(3)=2,a1
