离散数学7习题解答.docx

资源描述

离散数学7习题解答.docx

《离散数学7习题解答.docx》由会员分享，可在线阅读，更多相关《离散数学7习题解答.docx（15页珍藏版）》请在冰点文库上搜索。

离散数学7习题解答.docx

离散数学7习题解答

第7章习题解答

7.1

（1）,

（2）,（3）,（5）都能构成无向图的度数列,其中除⑸外又都能构成无向简单图的度数列.

分析1°非负整数列d!

d2,…，dn能构成无向图的度数列当且仅当di为

偶数,即d!

d2,…，dn中的奇数为偶数个.

（1）,

（2）,（3）,（5）中分别有4个,0个,4

个,4个奇数，所以，它们都能构成无向图的度数列，当然，所对应的无向图很可能是非简单图.而⑷中有3个奇数，因而它不能构成无向图度数列.否则就违背了握手定理的推论.

2°（5）虽然能构成无向图的度数列,但不能构成无向简单度数列.否则,若存在无向简单图G,以1,3,3,3为度数列,不妨设G中顶点为v!

v2,v3,v4,且

d（Vi）=1,于是d（V2）=d（V3）=d（V4）=3.而V!

只能与v?

""之一相邻,设w与v?

相邻，这样一来，除V2能达到3度外，V3,V4都达不到3度,这是矛盾的.

在图7.5所示的4个图中,

（1）以1为度数列,

（2）以2为度数列,（3）以3为度数列,（4）以4为度数列（非简单图）.

7.2设有几简单图D以2,2,3,3为度数列，对应的顶点分别为v1,v2,v3,v4,由

于d（v）二d（v）d_（v）,所示，d（vj-d-（y）=2-0=2,d（V2）=d（V2）-d“2）

=2—0=2,d（vj=d（Vs）_d—（V3）=3_2=1,d（V4）=d（Vq）_d^v。

）=3_3=0

由此可知，D的出度列为2,2,1,0,且满足add-（Vi）.请读者画出

一个有向图•以2,2,3,3为度数列,且以0,0,2,3为入度列,以2,2,1,0为出度列.

7.3D的入度列不可能为1,1,1,1.否则,必有出度列为2,2,2,2（因为d（v）=d（v）d~（v））,）此时,入度列元素之和为4,不等于出度列元素之和8,这违背握手定理.类似地讨论可知，1,1,1,1也不能为D的出席列.

7.4不能.N阶无向简单图的最大度厶_n一1.而这里的n个正整数彼此不同因而这n个数不能构成无向简单图的度数列，否则所得图的最大度大于n,这与最大度应该小于等于n-1矛盾.

7.5

（1）16个顶点.图中边数m=16,设图中的顶点数为n.根据握手定理可

知2m=32二'd（vj=2n

所以，n=16.

（2）13个顶点.图中边数m=21,设3度顶点个数为x,由握手定理有

2m=42=343x

由此方程解出x=10.于是图中顶点数n=310=13.

（3）由握手定理及各顶点度数均相同，寻找方程

224=nk

的非负整数解，这里不会出现n,k均为奇数的情况.其中n为阶级，即顶点数,k为度数共可得到下面10种情况.

1个顶点，度数为48.此图一定是由一个顶点的24个环构成，当然为非简单

22个顶点,每个顶点的度数均为

非简单图.

33个顶点,每个顶点的度数均为

44个顶点,每个顶点的度数均为

56个顶点，每个顶点的度数均为

24.这样的图有多种非同构的情况，一定为

16.所地应的图也都是非简单图.

12.所对应的图也都是非简单图.

8,所对应的图也都是非简单图.

6个顶点，每个顶点的度数均为6.所对应的非同构的图中有简单图，也有非简单图.

712个顶点，每个顶点的度数均为4.所对应的非同构的图中有简单图，也有非简单图•

816个顶点,每个顶点的度数均为3,所对应的非同构的图中有简单图，也有非简单图•

924个顶点,每个顶点的度数均为2.所对应的非同构的图中有简单图，也有非简单图•

1048个顶点,每个顶点的度数均为1,所对应的图是唯一的,即由24个K2构成的简单图•

分析由于n阶无向简单图G中,：

（G）

7.6设G为n阶图，由握手定理可知

70=235八d（vj_3n,

i吕

所以，

|70

=23.

这里，乂为不大于x的最大整数，例如.2」=2,25」=2,空=23.

.3一

7.7由于：

（G）=n-1,说明G中任何顶点v的度数d（v）八（G）=n-1,可是

由于G为简单图，因而列G）乞n-1,这又使得d（v）岂n-1,于是d（v）二n-1,也就是说,G中每个顶点的度数都是n-1,因而应有"G）乞n-1.于是G为（n-1）阶正则图，即G为n阶完全图Kn.

7.8由G的补图G的定义可知，GG为Kn,由于n为奇数，所以，Kn中各

项顶点的度数n-1为偶数.对于任意的V（G）,应有vV（G）,且

dG（v）_dG（v）二dg（v）二n-1

其中dG（v）表示v在G中的度数，dG（v）表示v在G中的度数.由于n_1为偶数,所以,dG（v）与dG（v）同为奇数或同为偶数,因而若G有r个奇度顶点,则G也有r个奇度顶点.

7.9由于D'D,所以，m'空m.而n阶有向简单图中，边数m乞n（n一1）,所以,应有

n（n_1）=m\m乞n（n-d）

这就导致m=n（n-1）,这说明D为n阶完全图，且D'=D.

7.10图7.6给出了K4的18个非同构的子图,其中有11个生成子图（8-18）,其中连通的有6个11,12,13,14,16,17）.图7.6中,n,m分别为顶点数和边数.

7.11K4有11个生成子图，在图7.6中，它们分别如图8-18所示.要判断它们之中哪些是自补图，首先要知道同构图的性质，设G1与G2的顶点数和边数.若G1三G?

贝U门丄=门2「且m

①

-一

&■——G

乙

生

于

◎Q

◎4Y

O*1・

□

国7,6

（8）的补图为（14）-K4,它们的边数不同,所以，不可能同构.因而（8）与（14）均不是自补图类似地，（9）的补图为（13）,它们也非同构,因而它们也都不是自补图.（10）与（12）互为补图,它们非同构,因而它们都不是自补图.（15）与（17）互为补图,它们非同构，所以,它们都不是自补图•类似地,（16）与（18）互为补图且非同构，所以，它们也都不是自补图•

而（11）与自己的补图同构，所以,（11）是自补图•

7.123阶有向完全图共有20个非同构的子图，见图7.7所示，其中⑸-（20）

为生成子图，生成子图中（8）,（13）,（16）,（19）均为自补图.

分析在图7.7所示的生成子图中，（5）与（11）互为补图,（6）与（10）互为补图,（7）与（9）互为补图,（12）与（14）互为补图,（15）与（17）互为补图,（18）与（20）互为补图，以上互为补图的两个图边数均不相同，所以，它们都不是自补图.而

（8）,（13）,（16）,（19）4个图都与自己的补图同构，所以，它们都是自补图.

7.13不能.

分析在同构的意义下，G,G2,G3都中K4的子图，而且都是成子图.而K4的

两条边的生成子图中，只有两个是非同构的，见图7.6中（10）与（15）所示.由鸽巢原理可知，G,G2,G3中至少有两个是同构的，因而它们不可能彼此都非同构.

鸽巢原理m只鸽飞进n个鸽巢,其中m一n,则至少存在一巢飞入至少［凹］只

鸽子.这里x表示不小于x的最小整数.例如，|2=2,|2.5=3.

7.14G是唯一的，即使G是简单图也不唯一.

0■

生

子田

匕

込

匕

込

陡

©n

込

阻7.7

分析由握手定理可知2m=3n,又由给的条件得联立议程组

'2m=3n、2n—3=m.

解出n=6,m二9.6个顶点,9条边，每个顶点的度数都是3的图有多种非同构

的情况,其中有多个非简单图（带平行边或环）,有两个非同构的简单图，在图7.8中

（1）,

（2）给出了这两个非同构的简单图.

满足条件的非同构的简单图只有图7.8

中,

（1）,

（2）所示的图,

（1）与⑵所示的图,

（1）与

（2）是非同构的.

注意在⑴中不存在3个彼此相邻的顶点而在⑵中存在3个彼此相邻的顶点，因而⑴图与

（2）图非同构.下面分析满足条件的简单图只有两个是非同构的.首先注意到

（1）中与

（2）中图都是K6的生成子图，并且还有这样

的事实，设G,G2都是n阶简单图，则G^G2当且仅当G^eG2,其中G,G2分别

为G与G2的补图.满足要求的简单图都是6阶9条边的3正则图，因而它们的补图都为6阶6条边的2正则图（即每个顶点度数都是2）.而K6的所有生成子图中,6条边2正则的非同构的图只有两个，见图7.8中（3）,（4）所示的图，其中（3）为

（1）的补图,（4）为

（2）的补图，满足要求的非同构的简单图只有两个.

但满足要求的非同简单图有多个非同构的，读者可自己画出多个来.

7.15将K6的顶点标定顺序，讨论X所关联的边.由鸽巢原理（见7.13题）,

与V1关联的5条边中至少有3条边颜色相同，不妨设存在3条红色边,见图7.9中⑴所示（用实线表示红色的边）并设它们关联另外3个顶点分别为V2,v4,V6.若

V2,V4,V6构成的Kg中还有红色边，比如边（V2M）为红色，则Vj^M构成的Kg为

红色K3,见图7.9中⑵所示.若V2,V4,V6构成的K3各边都是蓝色（用虚线表示）,则V2,V4,V6构成的Ka为蓝色的.

珂

7.16在图7.10所示的3个图中，

（1）为强连通图，

（2）为单向连通图，但不是强连通的,（3）是弱连通的，不是单向连通的，更不是强连通的.

图7.10

分析在⑴中任何两个顶点之间都有通路，即任何两个顶点都是相互可达的,因而它是强连能的.

（2）中c不可达任何顶点，因而它不是强连通的，但任两个顶点存在一个顶点可达另外一个顶点，所以，它是单向可达的.（3）中a,c互相均

不可达，因而它不是单向连通的，更不是强连通的.

判断有向图的连通性有下面的两个判别法.

1°有向图D是强连通的当且仅当D中存在经过每个顶点至少一次的回路.

2°有向图D是单向连通的当且仅当D中存在经过每个顶点至少一次的通路.

（1）中abcda为经过每个顶点一次的回路,所以，它是强连能的.

（2）中abdc为经过每个顶点的通路，所以，它是单向连通的，但没有经过每个顶点的回路，所以,它不是强连通的.（3）中无经过每个顶点的回路，也无经过每个顶点的通路，所以,它只能是弱连通的.

7.17G-E'的连通分支一定为2,而G-V'的连通分支数是不确定的.

分析设E'为连通图G的边割集,则G-E'的连通分支数p（G-E'）二2,不可能大于2.否则，比如p（G-E'）=3,则G-E'由3个小图G「G2，G3组成，且E'中边的两个端点分属于两个不同的小图.设E"中的边的两个端点一个在G中,另一个

在G2中,则e"e',易知p（G一E"）=2,这与E'为边割集矛盾,所以,p（G一E"）=2.

但p（G-V'）不是定数,当然它大于等于2,在图7.11中,V二｛u,v｝为⑴的点

割集,p（G-V）=2，其中

G为

（1）中图.V=｛v｝为⑵中图的点割集，且v为割

tini

点,p（G-V）=4,其中G为⑵中图.

屛1

;■

<]>

£7.11

（2）

7.18解此题，只要求出D的邻接矩阵的前4次幕即可.

0110

1000A=

0101

.0000一

101

110

001

D中长度为4的通路数为A4中元素之和，等于15,其中对角线上元素之和为3,即D中长度为3的回路数为3.V3到V4的长度为4的通路数等于a34）=2.

分析用邻接矩阵的幕求有向图D中的通路数和回路数应该注意以下几点：

1°这里所谈通路或回路是定义意义下的，不是同构意义下的.比如,不同始点（终点）的回路

2°这里的通路或回路不但有初级的、简单的，还有复杂的.例如，V1,V2,w,V2,V1是一条长为4的复杂回路.

3°回路仍然看成是通路的特殊情况.

读者可利用A2,A3,求D中长度为2和3的通路和回路数.

7.19答案A:

④.

分析G中有Nk个k度顶点，有（n—NQ个（k1）度顶点，由握手定理可知

、d（Vj）=kNk（k1）（n-Nk）=2m

=Nk=n（k1）-2n.

7.20答案A:

②；B:

③.

分析在图7.12中，图

（1）与它的补同构，再没有与图

（1）非同构的自补图了所以非同构的无向的4阶自补图只有1个.图⑵与它的补同构，图⑶与它的补也同构，而图⑵与图⑶不同构，再没有与

（2）,（3）非同构的自补图了，所以，非同械的5阶自补图有2个.

<1）（Z）⑶

圉7.12

7.21答案A:

④;B:

③;C:

④;D:

①.

分析

（1）中存在经过每个顶点的回路，如adcba..

（2）中存在经过每个顶点的通路，但无回路.（3）中无经过每个顶点至少一次的通路,其实,b,d两个顶点互不可达.（4）中有经过每个顶点至少一次的通路,但无回路，aedcbd为经过每个顶点的通路.（5）中存在经过每个顶点至少一次的回路,如aedbcdba.（6）中也存在经过每个顶点的回路,如baebdcb.由7.16题可知，

（1）,（5）,（6）是强连通的,

（1）,

（2）,（4）,（5）,（6）是单向连能的,

（2）,（4）是非强连通的单向连通图.注意,

强连通图必为单向连通图.6个图中,只有（3）既不是强连通的，也不是连通的，它只是弱连通图.

在⑶中，从a到b无通路，所以d,：

：

a,b「：

而b到a有唯一的通路ba,所以

db,a=1.

7.22答案A:

①;B:

⑥㈩C:

②;D:

④.

分析用Dijkstra标号法，将计算机结果列在表7.1中.表中第x列最后标定

y/Z表示b到x的最短路径的权为y,且在b到x的最短路径上,Z邻接到x,即x的前驱元为Z.由表7.1可知,a的前驱元为c（即a邻接到c）,c的前驱元为b,所以,b到a的最短路径为bca,其权为4.类似地计论可知,b到c的最短路径为be,其权为1.b到d的最短路径为bcegd,其权为9.b到e的最短路径为bee,其

权为7.

表7.1

顶点

〔a

肌

4/c

5/c

凶e

9/g

7.23答案A:

⑧；B:

⑩C:

③；D:

③和④.

分析按求最早、最晚完成时间的公式，先求各顶点的最早完成时间，再求

最晚完成时间，最后求缓冲时间

（1）最早完成时间：

TE（vJ=0

-_（V2）二{vM,

TE（v2）=max{03}=3

-_（V3）二{vz},

TE（v3）=max{02,3C}-3

厂（vj二{wm},TE（vJ=max{04,32}=5

-（V5）二Mm},TE（V5）=max{34,34}-7

-一山）={V4,V5},

TE（v7）=max{55,100}=10

（V8）={V6,V7},

TE（v8）=max{73,101}=11

-讥）二{V5,V8},

TE（v9）=max{76,111}=13

-_（V6）二“他},

TE（v6）=max{34,70}=7

（2）最晚完成时间:

TL（V9）=13

-（V8）二{V9},

TL（v8）=min{13_1}=12;

-（V6）={V8},

TL（v6）=min{12-3=9;

-（V7）二g},

TL（v7）=min{12—1}=11;

-（V5）={V6,V9},

TL（v5）=min{9-0,13-6}=7;

：

（V4）*7},

TL（V4）=min{11-5=6;

-（V3）二{V4,V5,V6},

TL（v3）=min{6-2.7-4.9-4二5;

（v2）={v3,V5},

TL（v2）=min{3-0.7-4}=3;

；（vj={V2,V3,V4},

TL（vJ=min{3—3.3—2,6—'4}=0;

（3）缓冲时间：

TS（Vi）二TS（V2）=TS（V3）=TS（V5）=TS（V9）=0TS（V4）=1,TS（V6）=2,TS（V7）=TS（V8）=1.

（4）关键路径有两条：

V1,V2,V5,V9和V1,V2,V3,V5,V9.

展开阅读全文