图论基础习题及答案

离散数学

习题5

1.给定下面4个图（前两个为无向图，后两个为有向图）地集合表示，画出1

示。

L

G]VpE]，其中V1V”V12VpV,4V5,1（vpV,）,（v2,V3）,（v3）V4）,（v2,v3）

G2E2，其中V2V”2G，丫），2（v，¥），3（V,¥），46,¥），5（v,*）

%%E3，其中V3V;13v,yv，¥3，v,y2，V,Y夕V,Y,

I)2ypE4，其中V4V,,

E4VI,V2,y，Y,y,y,y,

解答：

◎

D、2

2先将图1中各图地顶点标定顺序,然后写出各图地集合表示。

图1

解答:略。

111

第5章图地基本理论

3.写出图1中各图地度序列，对有向图还要写出出度列与入度列。

解答:图1各图地度序列分别为(4L232),(323,42),出度列(2Q21,0),入度列(2Q

2,1,0)。

4.设无向图G有12条边,3度与4度顶点各2个，其余顶点地度数均小于3,问中至少

有几个顶点？在最少顶点地情况下，写出G地度序列，(G),G)。

解答:根据握手定理，21232423(n4),得8。

当n=8时，上述式子取21232423311,因此度序列为(443,333

3,1)o(G)=4,(G)=1o

5.设无向图中有7条边3度与5度顶点各1个其余地都是2度顶点问该图有几个顶点？

解答：由握手定理，有(273523个2度顶点。因此该图有113=5个顶点。

6画以(1,23,4)为度序列地简单图与非简单图各一个。

解答：

7.设9阶无向图G中，每个顶点地度数不是5就是6,证明中至少有5个6度顶点或至

少有6个5度顶点。

证明：假设G中至多有4个6度顶点且至多有5个5度顶点。而G地顶点为9,所有顶点

度只能是5或6,因此G恰好有4个6度顶点与5个5度顶点。由握手定理，

2|E(G)|465549,矛盾！因此，结论得证。

&最大度等于最小度且都等于2地6阶无向图有几种非同构地情况？其中有几种是简

单图？

解答:总共有以下11种非同构地图：6C,14C,C,23clC,32c.2C,22c.C

C.C,C,C,C3c2，CC.,2c3，C6。其中简单图为2c3，C(其中,C

53(26o1

为一个带自环地顶点所成地图)

9.图2所示地六个图中哪几个是强连通图？哪几个是单向连通图？哪几个是连通图(弱连

112

离散数学

通图)？

图2

解答:第1,56图为强连通图,第2,4图为单向连通图，以上6个图均为弱连通图。

10.下面给出地两个正整数列表示顶点地度数列，哪个是可图化地？对于可图化地数列，试

给出3种非同构地无向图,其中至少有两个图是简单图。

(1)2233,445<2)2222,3344

解答：⑴不可图，因为奇度数顶点个数为奇数。

⑵可图。以下给出3种非同构地无向图，其中后两个图是简单图。

1L下列各数列中哪些是简单图化地？对于可简单图化地,试给出两个非同构地简单图。

(1)(2,3,3,5,5,6,6)(2)(1,1,2,2,3,3,5,5)(3)(2,2,2,2,3,3)

解答：(1)(2,3,355,6,6)不可简单图化(2)(1,1,2,2,3,355)可简单图化(3)

(2,2,2,2,3,3)可简单图化。

图略。

12画出无向完全图K4地所有非同构地子图,指出哪些是生成子图。

解答:生成子图如下图所示：

113

第5章图地基本理论

13.已知n阶无向简单图G有m条边，试求G地补图G耳边数m:

14.无向图G如图3所示，先标定顶点与边，然后

(1)求G地全部点割集与边割集，并指出其中地割点与桥(割边)。

⑵求G地点连通度G与边连通度G.

解答：⑵G)=1,⑹=1。

15求图4所示图G地G,G,G.

解答：(G)=2,(G)=3,⑹=4。

16设n阶无向简单图为3-正则图,且边数m与n满足2n3m,问这样地无向图有几种

非同构地情况？

114

离散数学

2n3m

解答:顶点数与边数地关系为2m3n，解得

17.n(nz3)阶竞赛图中至多有几种非同构地圈？

解答:至多有n-2种非同构地圈。

1&画出邻接矩阵A地无向图G地图形，其中

01010

11001

A00011

10101

01111

解答：图G如下:

19.有向图D如图5所示。

(1)D中看到长度为1,234地通路各为几条？

⑵D中看到%长度为1,234地回路各为几条？

⑶D中长度为4地通路有几条？其中长度为4地回路为多少条？

(4)D中长度小于或等于4地通路为多少条？其中有多少条为回路?

⑸写出D地可达矩阵。

1‘2V3

115

第5章图地基本理论

图5

解答：

1210123112431264

0010„0001„00100001

AA

000100100001

001000010010°086P

因此，⑴D中v到v首度为1,234地通路分别为QL34条。

⑵D中％到%长度为1,234地回路均为1条。

⑶D中长度为4地通路有1+2+6+4+1+1+1=16条,其中长度为4地回路为1+1+1=3条。

(4)D中长度小于或等于4地通路为多少7+10+13+16=46条淇中有1+3+1+3=8条为回路。

⑸D地可达矩阵为

1111

0111O

P

0011

0011

20.有向图D如图6所示。求

(1)V2到V5长度为1,234地通路数.

⑵v5到内长度为L234地回路数。

(3)D中长度为4地通路数(含回路)。

(4)D中长度小于或等于4地回路数。

⑸写出D地可达矩阵。

解答:

116

离散数学

1011010120

1010010120

A00010A2A3A400000。

0000000000

0002000000

因此

(1)v2到V5长度为1,234地通路数均为0o

⑵v5到v5长度为L234地回路数均为0。

⑶D中长度为4地通路数(含回路)为8。

(4)D中长度小于或等于4地