离散数学课后答案_第1页
离散数学课后答案_第2页
离散数学课后答案_第3页
离散数学课后答案_第4页
离散数学课后答案_第5页
已阅读5页,还剩12页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

P146习题9.1

9.1.1解:⑴几何图表示如右。

⑵deg(vj=3deg(v2)=4deg(v3)=3deg(v4)=3/

V3

deg(v5)=ldeg(v6)=0奇度数结点数为4。£

⑶(v2,v2)为自环;(Vl,V3)与(v3,Vi)为平行边;

(V4,V5)为悬挂边;V5为悬挂点;V6为孤立点。该图为伪图。V5A

9.1.2证:⑴n个结点的所有图中,完全图边数最多。V

每点n-1度,n个点的总度数为:2m=£deg(%)=n(nT)m=n(n-l)/2

n个结点的任一图的边数W完全图的边数,mWn(n-l)/2

⑵:在简单有向完全图中,任二点之间有两条方向相反的边,

/.每点的度数为2(n-1),.•.总度数为2m=2(n-L)n,m=n(n-l)o

9.1.3解:⑴去掉v点后,有nT个结点,m-d条边。

⑵去掉e边后,有n个结点,mT条边。

9.1.4证:假设n个结点的度数皆不相同

在简单无向图中,一个结点的最大度数为n-1,最小度数为0。

它们只能为0,1,…,n-1n个值。

•/0度点不与其它任何结点相邻,而n-1度点与其它任何结点相邻,

,二者产生一个矛盾。X

⑶否。n个结点的简单无向图中,结点的最大度数为nT,5不可。

⑷否。后三点均与其它各点有边,故第一点也应三度。

⑸否。后二点均与其它各点有边,故第一点至少应为二度。

9.1.6解:2m=nkm=nk/2。

9.1.7证:⑴当图G中n个点的度数都为3(G)时,总度数为2m=nb(G)。

但一般情况下,5(G)为最小度数,而并非所有结点的度数都为3(G)时,

必有2m》n3(G),/.2m/n>8(G)。

(2)当图G中n个点的度数都为△&)时,总度数为2m=nA(G)

但一般情况下,△&)为最大度数,而并非所有结点的度数都为△4)时,

必有2m^nA(G),2m/n^A(G)。X

P148习题9.2

9.2.1解:同构的只给出其一。

(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)

补图对表

(16)(15)⑫(11)(13)(14)皆为自补图

9.2.2解:

H的补图H相对于G的补图

9.2.3解:

9.2.4解:

⑴

四点的自补图五点的自补图

⑵不存在3个结点或6个结点的自补图,因为他们的完全图边数为奇数。

⑶证明:设结点数和边数分别为n和m。

有n个结点的自补图,则n个结点的完全图边数必为偶数,

:.m=2ttel+,又■:完全图边数m=n(n-l)/2,/.n(n-l)=4t;

若n为偶数,则n-1必为奇数,n必为4的倍数,,n=4k,keL,

若n为奇数,n必为4的倍数,.,.n-l=4k,/.n=4k+l,kel+。X

“,„fl2345678910

9.2.5证:⑴构造置换f:V-V,f=

ab(12341059857

⑵经验证,V(x,y)eEa,(f(x),f(y))eEb,反之亦然。

根据同构的定义,两图同构。X

9.2.6证:假设两图同构,根据前面介绍的两途同构的必要条件,

在(a)中只有1和2两点间有平行边,在(b)中只有2和3两点间有平行边,

所以必然是(a)中的1和2两点与(b)中的2和3两点相对应。

又因在(a)中1点4度,2点3度,在(b)中2点3度,3点4度,

所以必然是(a)中2点对应(b)中2点,(a)中1点对应(b)中3点。

又在(a)中1点的3个邻接点的度数皆不超过3度,而在⑹中3点与4度点4邻接,

故出现了矛盾。所以原命题成立。

9.2.7证:因四个结点两条边的无向简单图,只有两种非同构的状态,

一种是这两条边邻接,另一种是这两条边不邻接,如右图所示。

所三个这样的图,必至少有两个图同构。X(a)(b)

P151习题9.3

9.3.1解:各举一例。

长度为9的迹长度为8的不是径的迹长度为5的圈

长度为6的圈长度为8的圈长度为9的圈:

(Vi,V2)或(V4,V1)均可。

9.3.5证:若从u到v存在径,则因径是迹,所以从u到v存在迹。

若从U到V存在迹,

⑴迹上点不重复,则该迹即为径。

(2)迹上有重复的点,如:u…ab…a…v,则将b…a这段路去掉,得到的仍是从u到v

的迹。如果还有重复结点,则继续重复作上述删除工作,直到迹上没有重复的点,便得到从u

到v的径。X

P165习题9.4

9.4.1解:

(1)V1-*V10;V1-*V21;V]-*V33;V1-V42;

V1—V56;VLV64;VLV77;V1—V85;V9-V90

⑵D=8

⑶弱分图:{vi,V2,v3,V4,V5,v6,V7,V8,Viol,{vj

单分图:{vi,V2)V3,V4,V5)V6)V7,V8},{v5,V7)V8)Vifl},{v9}

强分图:{vi,V2,V3,V4,V6),{v5,V7,V8},{v9},{vto}

94.2解:%在Vi到Vk的短程线上。

9.4.3反证:假设两个奇度数结点u和v之间无路

则结点u和v必分居于两个不同的连通分支中,

于是u所在的连通分支中,奇度数结点的数目为1,与定理9.1-1的推论1矛盾!

9.4.4见P172,定理9.18的证明。

9.4.5反证:假设5(G)^0o

设|V|=no任取一点,•••8(G)#0,/.该点至少有一入度。沿提供入度的边反向走到该

边的起点。又因该点也至少有一入度,再沿提供入度的边反向走到该边的起点。如此走下去,

不外乎两种结果:①再向前走便回到已走过的点上,形成回路。②一路上走全了所有点,但

因最后一点仍有入度,再向前走必然回到已走过的点上,形成回路。两种情况都存在回路,与

前提无回路矛盾。X

P168习题9.5

0101

9.5.1解:⑴A=°°11⑵3条。⑶0条。⑷路65条。其中回路15条。

0101

0100

-10000-100oo-

1110001100

9.5.2解:p=11100P^pT=01100强分图为:{vj,{v2,V3},{v.1,V5}。

1111100011

1111100011

9.5.3解:⑴ei62036465©6

Vir-i

V211-1

V3-11-1

V411-1

-11

J

(2)degin(vi)=l;degOut(vi)=0;degin(v3)=2;degout(v3)=l

⑶矩阵中所有元素绝对值之和为12,而边数为6。

0121

9.5.4解:0001Idij=l说明从i点到j点存在一条边。

00101

00120

9.5.5解:(1)将距离矩阵中8项置为0,将非8项置为1,便得到可达矩阵。

⑵非主对角线上的元素丸表示从一点Vi到另外一点V」的距离,该距离值不是8说明

从Vi到V」存在通路。非主对角线上的所有元素不为8,说明从任一点Vi到其它任

一点都有路相通,所以该图是连通的。

9.5.6说明:⑴二元运算八和V定义于右面的运算表。邓1VTo

⑵。为布尔阵的布尔乘法,定义如下:°;°0。

设A为n行k列布尔阵,B为k行m列布尔阵,1——1

则C=AOB为n行m列布尔阵,

。「外西)0

P-1

⑶V为布尔阵的并运算,定义为:设X,Y,Z皆为n行m列布尔阵,

Z=XVY,Zij=XijAyij。

(4)。的一定义为:A°=I,An=An-*OA。

(5)。对V满足分配律。令£=人。①"0,D=BVC,R=AOB,S=AOC

kkk

eij=v(ajpAdpj)=v(ajpA(bpjV.))=.,(%Abpj)v(aipAc”))

kk

=v(aipAbpj)vv(aipAC^^IJVs^„

,E=RVS,即AO(BVC)=AOBVAOC

证:对n是以归纳证明。

当n=l时,IVA=IVA

当n=2时,(IVA)2=(IVA)O(IVA)=IOIVIOAVA0IVAG)A=I2VIOAVAOIVA2,

*/IOA=AOI=A,且101=1,且V运算满足嘉等律,二(IVA)2=IVAVA2,

假设当n=k(keN,k23)时成立,即(IVA)k=IVAV…VA14,

当n=k+l时,

(IVA)k+1=(IVA)kO(IVA)=((IVA)kOI)V((IVA)kOA)

=(IVA)kV((IVAV-VAk)OA)

=(IVAV-VAk)V(AVA2V-VAk+1)=IVAV-VAk+1派

P162习题9.6

9.6.1解:(a)否。:有4个奇度数结点。

(b)可。•••所有结点皆为偶度数。

9.6.4(1)证:•••G是欧拉图,,是连通的。欧拉图中必有欧拉回路,题9.6.3图

,所有的点都在此回路上,.•.任两点可互达,,该图是强连通的。

⑵不一定是欧拉图。右图是强连通的,但不是欧拉图。

9.6.5证:无向完全图每个结点的度数为n-1,任两个结点的度数之和为2n-2,

当n22时,2n-22n。但注意n=2时不存在汉密尔顿回路,

当n23时,根据推论9.5,无向完全图必是汉密尔顿图。X

9.6.6证:以人为结点,两点之间有边,表示两人互相认识,得到无向图G=(V,E)。

(1)当n=3,即V={a,b,c},a,b合起来认识c,/.a,b至少有一人认识c,不妨设a

认识c;又•:a,c合起来认识b,若a认识b,则b-a-c为所求;若c认识b,则b-c-a为所求。

⑵当n24,Va,beV,Va,b合起来认识其余n-2个人,:.deg(a)+deg(b)2n-2。

①若a与b互相认识,则deg(a)+deg(b)2(n-2)+2=n»

②若a与b互相不认识,则a认识其余n-2个人,b也认识其余n-2个人。

否则,若mdeV,a认识d,b不认识d,则a,d合起来不认识b,与题给条件矛盾。

此种情况下,deg(a)+deg(b)=2(n-2)2n

根据推论9.5,存在汉密尔顿回路。

9.6.7证:任选两个奇度数结点,在他们之间连一条边,于是这两个奇度数结点变成偶度数

结点。再选两个奇度数结点,在他们之间连一条边,显然第二条外加边与第一外加边

不相邻。在k个奇度数结点间共加入k/2条不相邻的边,使所有结点皆为偶度数结点。

根据推论9.3,存在一条欧拉回路。再将k/2条不相邻的外加边去掉,则必形成k/2

条不相邻的迹。由于可把一条及分成多条迹,所以迹的总数2k/2。X

9.6.8解:(a)4笔;(b)2笔。

P166习题9.7

9.7.1解:是。互补结点集如下图。

9.7.2解:⑴VI每点至少2度,

V2中每点至多2度,t=2o

⑵见下表。

⑶匹配如右上图。题9.7.1图题9.7.2图

st(S)ST(S)ST(S)

16,81,36,7,8,101,2,36,7,8,9,10

27,9,101,46,8,91,2,46,7,8,9,10

37,102,37,9,101,3,46,7,8,9,10

46,8,92,46,7,8,9,102,3,46,7,8,9,10

1.26,7,8,9,103.46,7,8,9,101,2,3,46,7,8,9,10

9.7.3解:如下图。9.7.4解:如下图。9.7.5解:如下图。

&8,23.435比8-73gHgSio

9.7.6证:设|Vj=m,则|V2|=n-nio*.*完全二分图时便数最多为m=|Vj|V21=ni(n-n。,

该式当ni=n/2时有极大值n2/4,,m^n2/4。

P168习题9.8

9.8.1证::每个面至少由k条边围成,,f个面至少由kf条边围成。

又;每条边在计算面的边界时都计了两次,...总边数m»kf/2。

又•••平面图的欧拉公式n-m+f=2,代入上式解得mWk(n-2)/(k-2)

9.8.2解

1

9.8.3证:⑴将粗红笔所画子图的6,7两点串联合并后如右图为K5。

...原图存在与K5同胚子图,根据库氏定理原图为非平面图。

⑵如右图,粗红笔所画子图为K3.3,根据库氏定理,,原图为非平面图。

9.8.4反证:假设G和不皆为平面图

n点完全图的边数应为m=n(n-l)/2.......①

G是平面图,,G的边数W3n-6。G是平面图,二3的边数W3n-6。

■n点完全图的边数=6的边数+G的边数,mW2(3n-6)=6n-12.......②

当n»ll时,①式结果为m255,而②式结果为mW54,矛盾!证毕

9.8.5反证1:假设G不连通,有k22个连通分支:Gi,G2)-,Gk«

在G与G2,G2与G3与G4,…,Gk-i与Gk之间分别各加一条边,

共加了kT条边,于是新图G,为连通的了,且仍为简单平面图。

/.m'=m+kTW3n-6,将n=7和m=15代入,得kWl,与k22矛盾!证毕

反证2:假设G不连通,有k22个连通分支:—2,…,Gk。

则每个连通分支均为简单平面图,miW3n「6,

m=(mi+ni2+…+nik)W(3n「6)+(3n2-6)+…+(3nk-6)

=3(ni+n2k+…+nk)-6k=3n-6k

将n=7和m=15代入,得kWl,与k22矛盾!证毕

9.8.6反证:假设存在边界边数24的面

:.m>3f/2,再与n-m+f=2联立,解得m<3n-6o

将n=6代入,解得m<12,这与已知m=12矛盾!证毕

9.8.7证:对于2度点插入操作,点增加一个,边也增加一条。

对于2度点消去操作,点减少一个,边也减少一条。

对于2度点的操作,

按同胚的定义,若Gi与G2同构,则ni=n2,mi=m2,mi-ni=m2-n2o

,,

若Gi通过2度点操作后得到GJ与G2同构,ni-n2,•*.mi-ni=m2-n2,

mi,=mi+Ami,ni,=ni+Ani,(mi+Ami)-(ni+Ani)=m2-n2,

Am^Arii,/.m「ni=m2-n2。X

P170习题9.9

9.9.1解:

广一

/

9.9.2解:黑图的对偶图为红图。

(1)黑色图(a)到(b),点集之间的双射为f(x)=x。

经验证,边之间的对应关系也符合同构的定义,故两图同构。

(a)

(2)由于(b)的对偶图,即红图中有一5度点

所以两对偶图不同构。

9.9.3证:设图G的对偶图为G,,,G,是连通图,且gfo

•.•图G与图。同构,,G是连通图,且n=M=fo

又•••图G有对偶,图G是平面图,加之G是连通图,,n-f+m=2。

m=n+f-2=n+n-2=2n-2。证毕

9.9.5解:

9.9.6解:见上右两图。

9.9.7证:用数学归纳法证明。

当nW6时显然成立。

假设当n=k是成立,keN,k»7。

当n=k+l时,根据定理9.16,存在一点vdeg(v)W5。

将点v删去得到图G,,根据归纳假设,J可六色。

再将点v恢复,由于在G中与v邻接的点不超过5个,并且有六种颜色,

故取与所有邻结点不同的颜色给点v着色,二图G仍是6色的。X

9.9.8证:⑴反证:假设所有结点度数都24,...G的总度数24n,即2m24n,m>2n0

G是简单图,I.不含自环和平行边,二面的边界不能由1条或2条边构成。

又♦;G不含七,二面的边界不能由3条边构成,即有至少4条边构成。

又G是连通的平面图,根据推论9.7,mW2n-4,与m22n矛盾。

⑵证明方法与题9.9.7相同。X

P175习题9.10

9.10.1解:⑴设总结点数为n,1度结点数为n“边数为m。

总度数为3X3+2X1+IXn)=2m

总结点数为n=3+1+n,

树中点与边的关系m=n-1

三式联立解得n,=5o

9.10.2证:⑴反证:假设G不是一棵树

•••G是连通的,I.G必有回路。而删去此回路中任一边,图仍连通。

这与每一边都是割边的前提条件矛盾!G是一棵树。

⑵根据定理9.10-1(5),树是连通的,但删去任一边便不连通了。

再根据割边的定义,可知树上任一边都是割边。证毕

kk

9.10.3解:(1)2m=2(n-1)=2(-1)=/•«,,「・2(n1+n2+---+nki)=ni+2n2+---+knk)

;=1/=1

/.ni=n3+2n4+,--+(k-2)nk+2

kf(2—i)…

(2)(r-2)n.=V(2-i)n-2/.〃,,=?上---------。

)ir-2

9.10.4证:⑴:G是树,...m=n-l,,总度数=2m=2(nT)=2n-2。X

⑵构造算法:

①将个结点的度数从大到小排序,结果为:出,d2,…,d"。令i=l。

②画出一个5度的点,以及与它邻接的小个结点,及相应的边。

③i=i+l,若5=1,结束。

④将图的任一叶结点变为&度结点,画出与它邻接的其它d「l个结点,

及相应的边。转③。

证明:•.•构造出的图连通无回路,所以是树。又因非叶结点都按要求度数实

现了,也结点的树木必然也符合要求,该图即为满足各点度数条件的树。

⑶例:(dbd2)d8)=(4,3,2,1,1,1,1,1),n=8,di+d2+-+d8=14=2n-2。

9.10.5证:在T「{a}中,必形成两个不连通的部分,用结点集表示为%和V?。

对于丁2来说,必存在连接%和Vz的边,否则T?亦不连通,不妨设此边为b。

,/a",,boa。又{a}中的任一边都不在匕与V2之间,

T「{a}中的任一边都不为任b打。

将b加入T「{a}中,于

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论