第10章习题答案 下载本文

第10章 图

且有

?1??0A2??0??0?230001??12???3?00? A??00????000001??11043??12??10??00 A4???0001???0010???64??01? 10??01??(4)(2)由A4中a14D中v1到v4长度为4的路有4条,分别为:e1e1e4e6、e4e6e7e6、e1e2e5e6、?4可知,

e1e3e5e6。

(3)(3)由A3中a11?1可知,D中v1到自身长度为3的回路只有1条,为e1e1e1。

(4)D中长度为4的路总数为

??ai?1j?144(4)ij?16,其中对角元素之和为3,说明长度为4的回路为3条。

(5)D中长度小于等于4的路总数为A、A2、A3、A4中全体元素之和:7+10+13+16=46,其中回路数为:1+3+1+3=8。

?4??0234(6)由B4?A?A?A?A??0??0?8148??022?可知,D是单向连通图。

022??022??30.有向图G如图10-52所示,试求: (1)求G的邻接矩阵A。

(2)求出A、A和A,v1到v4长度为1、2、3和4的路有多少?

(3)求出ATA和AAT,说明ATA和AAT中的第(2,2)元素和第(2,3)元素的意义。 (4)求出可达矩阵P。 (5)求出强分图。

解 (1)求G的邻接矩阵为:

?0??0A??0??0?101??011?

101??100??2

3

4

v4v1v3v2图10-52(2)由于

?0??0A2??0??0?111??02??201?3?01A??

02111????02011???12??03??22??044A? ?0312????0101???23??13? 23??22??所以v1到v4长度为1、2、3和4的路的个数分别为1、1、2、3。 (3)由于

9

第10章 图

?0??0ATA??0??0?000??21??312??12TAA? ?21011????10213???21??10? 21??21??再由定理10.19可知,所以ATA的第(2,2)元素为3,表明那些边以v2为终结点且具有不同始结点的数目为3,其第(2,3)元素为0,表明那些边既以v2为终结点又以v3为终结点,并且具有相同始结点的数目为0。AAT中的第(2,2)元素为2,表明那些边以v2为始结点且具有不同终结点的数目为2,其第(2,3)元素为1,表明那些边既以v2为始结点又以v3为始结点,并且具有相同终结点的数目为1。

?0??0(4)因为B4?A?A2?A3?A4??0??0?101??0??011??0+

101??0???100???0111??0??201??0+

111??0???011???0212??03??122??04+

212??03???201???0123??13??23??22???0??0?0??0?741??747?,所以

747??434???0??0求可达矩阵为P??0??0?111??111?。

111??111??111??0??111??1∧??1111????111??1000??0??111??0=??1110????111??0000??111?,所以{v1},{v2,v3,v4}构成G的强分图。

111??111???0??0(5)因为P?PT??0??0?31.画一个无向欧拉图,使它具有: (1)偶数个顶点,偶数条边。 (2)奇数个顶点,奇数条边。 (3)偶数个顶点,奇数条边。 (4)奇数个顶点,偶数条边。

解 (1)n(n为偶数,且n≥2)阶圈都是偶数个顶点,偶数条边的无向欧拉图。 (2)n(n为奇数,且n≥1)阶圈都是奇数个顶点,奇数条边的无向欧拉图。

(3)在(1)中的圈上任选一个顶点,在此顶点处加一个环,所得图为偶数个顶点,奇数条边无向欧拉图。 (4)在(3)中的圈上任选一个顶点,在此顶点处加一个环,所得图为奇数个顶点,偶数条边无向欧拉图。 32.画一个无向图,使它是: (1)既是欧拉图,又是哈密尔顿图。 (2)是欧拉图,但不是哈密尔顿图。 (3)是哈密尔顿图,但不是欧拉图。 (4)既不是欧拉图,也不是哈密尔顿图。

解 (1)n(n≥3)阶圈,它们都是欧拉图,又是哈密尔顿图。

(2)给定k(k≥2)个长度大于等于3的初级回路,即圈C1,C2?,Ck。将C1中某个顶点和C2中的某个顶点重合,但边不重合,C2中某个顶点和C3中的某个顶点重合,但边不重合,续行此法,直到将Ck?1

10

第10章 图

中某个顶点和Ck中的某个顶点重合,但边不重合,设最后得到的连通图为G,则G是欧拉图,但不是哈密尔顿图。

(3)在n(n≥4)阶圈中,找两个不相邻的顶点,在它们之间加一条边,所得图是哈密尔顿图,但不是欧拉图。

(4)在(2)中的图中,设存在长度大于等于4的圈,比如C1,在C1中找,两个不相邻的顶点,在它们之间加一条边,然后按照(2)的方法构造图G,则G既不是欧拉图,也不是哈密尔顿图。

33.(1)n为何值时,无向完全图Kn是欧拉图?n为何值时,Kn仅存在欧拉路而不存在欧拉回路? (2)什么样的完全二部图是欧拉图? (3)n为何值时,轮图Wn为欧拉图?

解 (1)一般情况下,我们不考虑K1。n(n≥2)为奇数时,无向完全图Kn是欧拉图。Kn各结点的度均为n-1,若使Kn为偶拉图,n-1必为偶数,因而必n为奇数。K2仅存在欧拉路而不存在欧拉回路。

(2)设Kr,s为完全二部图,当r、s均为偶数时,Kr,s为欧拉图。

(3)设Wn(n≥4)为轮图,在Wn中,有n-1个结点的度数为3,因而对于任何取值的n(n≥4),轮图Wn都不是欧拉图。

34.证明:完全图K9中至少存在彼此无公共边的两条哈密尔顿回路和一条哈密尔顿通路。

证明 设C1为K9中一条哈密尔顿回路。令G1为K9删除C1中全部边之后的图,则G1中每个结点的度均为6。由定理10.26可知G1仍是哈密尔顿图,因而存在G1中的哈密尔顿回路C2(显然C2也是K9中的哈密尔顿回路,并且C1与C2无公共边)。再L设G2为G1中删除C2中的全部边后所得图,G2为4正则图。由定理10.26可知G2具有哈密尔顿通路。设L为G2中的一条存在哈密尔顿通路,显然C1、C2、L无公共边。

事实上,可以证明在K9中存在4条边不重的哈密尔顿回路。

可以证明:在K3中存在一条边不重合的哈密尔顿回路,K5中存在两条边不重合的哈密尔顿回路,K7

中存在3条边不重合的哈密尔顿回路,一般情况下,K2k+1(k≥1)中最多可存在条边不重合的哈密尔顿回路。

35.已知a、b、c、d、e、f、g 7个人中,a会讲英语;b会讲英语和汉语;c会讲英语、意大利语和俄语;d会讲汉语和日语;e会讲意大利语和德语;f会讲俄语、日语和法语;g会讲德语和法语。能否将他们的座位安排在圆桌旁,使得每个人都能与他身边的人交谈?

解 用a、b、c、d、e、f、g 7个结点代表7个人,若两人能交谈(会讲同一种语言),就在代表它们的结点之间连无向边,所得无向图如下图(1),此图中存在哈密尔顿回路:,如图(2)粗边所示,于是按图(3)所示的顺序安排座位即

11

第10章 图

可。

36.证明:对于每个竞赛图D,至多改变一条边的方向后就可以变成哈密尔顿图。

证明 由定理10.26可知D中存在哈密尔顿通路,设D为n(n≥3)阶竞赛图,v1v2?vn为中的一条哈密尔顿通路,若边在D中,则v1v2?vnv1为D中一条哈密尔顿回路,故D为哈密尔顿图。否则边在D中,将改变方向得到边,于是D就变成了哈密尔顿图。

237.给定简单无向图G=,且|V|=m,|E|=n。试证:若n≥Cm?1+2,则G是哈密尔顿图。

2证明 若n≥Cm?1+2,则2n≥m-3m+6 (1)。

2

若存在两个不相邻结点u、v使得d(u)+d(v)<m,则有2n=

w?V?d(w)<m+(m-2)(m-3)+m=m

2

-3m+6,与(1)矛盾。所以,对于G中任意两个不相邻结点u、v都有d(u)+d(v)≥m。由定理10.26可知,G是哈密尔顿图。

38.设G是无向连通图,证明:若G中有割点或割边,则G不是哈密尔顿图。

证明 若G中有割点v,则G-{v}中至少有两个连通分支,从而?(G-{v})>|{v}|,由定理10.25可知,G不是哈密尔顿图。

若G中有割边e,当G只有两个结点时,显然G不是哈密尔顿图。当G的结点数多余2时,从G中删除割边e之后至少有两个连通分支,其中一个连通分支含有割边e的一个端点v且其结点个数大于1,于是?(G-{v})>|{v}|,由定理10.25可知,G不是哈密尔顿图。

39.某次会议有20人参加,其中每个人都至少有10个朋友,这20人围一圆桌入席,要想使与每个人相邻的两位都是朋友是否可能?根据什么?

解 可能。依题意,若用结点代表人,两人是朋友时相应结点之间连一条边,则得到一个无向图G=,该题转化为求哈密尔顿回路问题。

由于对任意u、v∈V,有d(u)+d(v)≥10+10=20,根据定理10.26,G为哈密尔顿图,G中存在哈密尔顿回路,按此回路各点位置入席即为所求。

40.设G是具有k(k>0)个奇数度结点的无向连通图,证明G中边不重合的简单通路的最小数目是它们包含G的全部边。

证明 由握手定理的推论可知,k是偶数。对k做归纳法。 (1)当k=2时,由定理10.22可知,G中存在偶拉路,结论得证。 (2)设k≤2r(r≥2)时结论成立,要证k为2r+2时结论成立。

设v1,v2为G中任意二奇度结点,由G的连通性可知,从v1到v2存在路径P0,删除P0上的全部边,得连通分支G1,G2,?,Gs。这些连通分支共含2r个奇度结点,设Gi中含ri个奇度结点,则2ri≤2r(1≤r≤s),且

k,2?2r=2r。由归纳假设可知,G中存在r条边不重合的简单通路,它们含G中的所有边。

iiiisi?1 12