2023年7月19日发(作者：)

《离散数学》第四部分---图论练习题答案

一、选择或填空

1、设G是一个哈密尔顿图，则G一定是( )。

(1) 欧拉图 (2) 树 (3) 平面图 (4) 连通图

答：(4)

2、下面给出的集合中，哪一个是前缀码？( )

(1) {0，10，110，101111} (2) {01，001，000，1}

(3) {b，c，aa，ab，aba} (4) {1，11，101，001，0011}

答：（2）

3、一个图的哈密尔顿路是一条通过图中( )的路。

答：所有结点一次且恰好一次

4、在有向图中，结点v的出度deg+(v)表示( )，入度deg-(v)表示(

答：以v为起点的边的条数， 以v为终点的边的条数

5、设G是一棵树，则G 的生成树有( )棵。

(1) 0 (2) 1 (3) 2 (4) 不能确定

答：1

6、n阶无向完全图Kn

的边数是( )，每个结点的度数是( )。答：n(n1)2, n-1

7、一棵无向树的顶点数n与边数m关系是( )。

)。

答：m=n-1

8、一个图的欧拉回路是一条通过图中( )的回路。

答：所有边一次且恰好一次

9、有n个结点的树，其结点度数之和是( )。

答：2n-2

10、下面给出的集合中，哪一个不是前缀码( )。

(1) {a，ab，110，a1b11} (2) {01，001，000，1}

(3) {1，2，00，01，0210} (4) {12，11，101，002，0011}

答：(1)

11、n个结点的有向完全图边数是( )，每个结点的度数是( )。

答：n(n-1),2n-2

12、一个无向图有生成树的充分必要条件是( )。

答：它是连通图

13、设G是一棵树，n,m分别表示顶点数和边数，则

(1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。

答：（3）

14、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在( )片树叶。

答：2

15、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。 答：1，树

16、设G是有n个结点m条边的连通平面图，且有k个面，则k等于:

(1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。

答：（1）

17、设T是一棵树，则T是一个连通且( )图。

答：无简单回路

18、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。

(1) 10 (2) 4 (3) 8 (4) 16

答：（4）

19、设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。

(1) 10 (2) 4 (3) 8 (4) 12

答：(4)

20、设图G=，V={a，b，c，d，e}，E={,,,,},则G是有向图还是无向图？

答：有向图

21、任一有向图中，度数为奇数的结点有( )个。

答：偶数

22、具有6 个顶点，12条边的连通简单平面图中，每个面都是由( )条边围成？

(1) 2 (2) 4 (3) 3 (4) 5

答：（3）

23、在有n个顶点的连通图中，其边数（ ）。

(1) 最多有n-1条 (2) 至少有n-1 条

(3) 最多有n条 (4) 至少有n 条

答：（2）

24、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为（ ）。

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

答：（4）

25、若一棵完全二元（叉）树有2n-1个顶点，则它（ ）片树叶。

(1) n (2) 2n (3) n-1 (4) 2

答：（1）

26、下列哪一种图不一定是树（ ）。

(1) 无简单回路的连通图 (2) 有n个顶点n-1条边的连通图

(3) 每对顶点间都有通路的图 (4) 连通但删去一条边便不连通的图

答：（3）

27、连通图G是一棵树当且仅当G中（ ）。

(1) 有些边是割边 (2) 每条边都是割边 (3) 所有边都不是割边 (4) 图中存在一条欧拉路径

答：（2）

二、证明或解答题

1、证明在有n个结点的树中，其结点度数之和是2n-2。

证明：

设T=是任一棵树，则|V|=n，且|E|=n-1。

由欧拉握手定理，树中所有结点的度数之和等于2|E|.

从而结点度数之和是2n-2。

2、任一图中度数为奇数的结点是偶数个。

证明：

设G=〈V,E〉是任一图。设|V|=n。

由欧拉握手定理可得

vVdeg(v)=2|E|可得，图中所有结点度数之和是偶数。显然所有偶数度结点的度数之和仍为偶数，从而所有奇数度结点的度数之和也是偶数。因此，图中度数为奇数的结点一定为偶数个。

3、连通无向图G的任何边一定是G的某棵生成树的弦。这个断言对吗？若是对的请证明之，否则请举例说明。

证明：

不对。

反例如下：若G 本身是一棵树时，则G的每一条边都不可能是G的任一棵生成树（实际上只有惟一一棵）的弦。

4、设T=是一棵树，若|V|>1，则T中至少存在两片树叶。 证明：

（用反证法证明）设|V|=n。

因为T=〈V,E〉是一棵树，所以|E|=n-1。

由欧拉握手定理可得

vVdeg(v)=2|E|=2n-2。

假设T中最多只有1片树叶，则deg(v)2(n-1)+1>2n-2。

vV得出矛盾。

5、画一个使它分别满足：

(1) 有欧拉回路和哈密尔顿回路；

(2) 有欧拉回路，但无条哈密尔顿回路；

(3) 无欧拉回路，但有哈密尔顿回路；

(4) 既无欧拉回路，又无哈密尔顿回路。

解

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

6、设无向图G=，|E|=12。已知有6个3度顶点，其他顶点的度数均小于3。问G中至少有多少个顶点？ 解：

设G中度数小于3的顶点有k个，由欧拉握手定理

24=deg(v)

vV知，度数小于3 的顶点度数之和为6。故当其余的顶点度数都为2时，G的顶点最少。即G中至少有9个顶点。

7、设图G=，|V|=n，|E|=m。k度顶点有nk个，且每个顶点或是k度顶点或是k+1度顶点。证明：nk=(k+1)-2m。

证明：

由已知可知，G中k+1度顶点为n-nk个。再由欧拉握手定理可知

2m=deg(v)=knk+(k+1)(n-nk)=(k+1)n+-nk

vV故nk=(k+1)-2m。

8、设G=是一个连通且|V|=|E|+1的图，则G中有一个度为1的结点。

证明：

(用反证法证明）

设|V|=n，则|E|=n-1。

由欧拉握手定理可得

vVdeg(v)=2|E|=2n-2。

因为G连通，所以vV，deg(v)1。假设G中没有1片树叶，则vVdeg(v)2n>2n-2。

得出矛盾。

9、若n阶连通图中恰有n-1 条边，则图中至少有一个结点度数为1。

证明：

（用反证法证明）设G=有n-1条边且|V|=n。

由欧拉握手定理可得

vVdeg(v)=2|E|=2n-2。

因为G是连通图，所以G中任一结点的度数都大于等于1。

假设G中不存在度数为1 的结点，则G中任一结点的度数都大于等于2.故vVdeg(v)2(n-1)+1>2n-2,

得出矛盾。

10、若G有n个结点，m条边，f个面，且每个面至少由k(k3)条边围成，则 mk(ｎ－2)／(ｋ－2)。

证明：

设连通简单无向平面图G=〈V,E,F〉，则|V|=n,|E|=m,|F|=p。

由已知对任一fF, deg(f)k。

由公式deg(f)=2|E|可得，2|E|k|F|。

fF再由欧拉公式|V|-|E|+|F|=2可得|V|-|E|+即k(n-2)(k-2)m。

所以mk(ｎ－2)／(ｋ－2)。

2|E|2。

k11、设G=是连通的简单平面图，|V|=n3，面数为k,则k2n-4。

证明：

记|E|=m。因为G=是连通的简单平面图，故每个面的度数都不小于3。从而由公式deg(f)=2|E|可得

fF3k2m

再由欧拉公式|V|-|E|+|F|=2有

m=n+k-2

及

3kn+k-2

2故 k2n-4。

12、证明对于连通无向简单平面图，当边数e＜30时，必存在度数≤4的顶点。

证明：

若结点个数小于等于3时，结论显然成立。

当结点多于3 个时，用反证法证明。

记|V|=n,|E|=m,|F|=k。

假设图中所有结点的度数都大于等于5。

由欧拉握手定理得deg(v)=2|E|得 5n2m。

vV又因为G=〈V,E,F〉是一个连通简单无向平面图，

所以对每个面f,deg(f)3。

由公式deg(f)=2|E|可得，2m3k。

fF再由欧拉公式|V|-|E|+|F|=2可得2从而30m,这与已知矛盾。

221m-m+m=m

531513、在一个连通简单无向平面图G=〈V，E，F〉中若|V|3，则 |E|3|V|－6。

证明：

 |V|3，且G=〈V，E，F〉是一个连通简单无向平面图，

 d(f)

3，fF。

由公式deg (f)=2|E|可得，2|E|3|F|。

fF再由欧拉公式|V|-|E|+|F|=2可得|V|-|E|+2|E|2。

3|E|3|V|－6。

14、给定连通简单平面图G=，且|V|=6, |E|=12, 则对于任意fF,

d(f)=3。

证明：

因为|V|=63，且G=〈V,E,F〉是一个连通简单无向平面图，

所以对任一fF，deg(f)3。

由欧拉公式|V|-|E|+|F|=2可得|F|=8。

再由公式deg(f)=2|E|，deg(f)=24。

fFfF因为对任一fF，deg(f)3，故要使上述等式成立， 对任一fF，deg(f)=3。

15、设G=是n个顶点的无向图(n>2)，若对任意u,vV，有d(u)+d(v)n，则G是连通图。 证明：

用反证法证明。

若G 不连通，则它可分成两个独立的子图G1和G2，其中|V(G1)|+|V(G2)|-2=n ，且G1中的任一个顶点至多只和G1中的顶点邻接，而G2中的任一顶点至多只和G2中的顶点邻接。任取uV(G1),vV(G2),则

d(u)|V(G1)|-1, d(v)|V(G2)|-1。

故d(u)+d(v)

(|V(G1)|-1)+(|V(G2)|-1)|V(G1)|+|V(G2)|-2

=n-2

故G是连通图。

16、一次会议有20人参加，其中每个人都在其中有不下10个朋友。这20人围成一圆桌入席。有没有可能使任意相邻而坐的两个人都是朋友？为什么？

证明：

可以。

将每个人对应成相应的顶点，若两人是朋友，则对应的两个顶点间连上一条无向边，作出一个简单无向图。由已知，图中每个顶点的度数都大于等于10。即图中任两个不相邻的顶点的度数大于等于20，即顶点数。故这个图是一个哈密尔顿图，从而存在哈密尔顿回路。任取一条哈密尔顿回路，按回路经过的顶点的次序安排对应的人的座位，就可满足要求。

17、证明在任何两个或两个以上人的组内，存在两个人在组内有相同个数的朋友。

证明：

将每个人对应成相应的顶点，若两人是朋友，则对应的两个顶点间连上一条无向边，作出一个简单无向图。则原命题相当于在该无向图中一定存在两个顶点的度数相等。

设该简单无向图中有n个顶点，则图中n个顶点的度数只能为0，1，2，…，n-1。若图中有两个或两个以上的顶点度数为0，则结论显然成立。否则所有顶点的度数都大于等于1。现用反证法证明该无向图中一定存在两个顶点的度数相等。

设该简单无向图中n个顶点中任何一对顶点的度数都不相等，即这n个顶点的度数两两不同。但每个顶点的度数只能是1,2,…,n-1这n-1个数中的某一种，这显然产生了矛盾。

因此该无向图中一定存在两个顶点的度数相等。从而在任何两个或两个以上人的组内，存在两个人在组内有相同个数的朋友。

18、设有如下有向图G=，

（1）求G的邻接矩阵；（2）G中v1到v4的长度为4 的通路有多少条？（3）G中经过v1的长度为3 的回路有多少条？（4）G中长度不超过4 的通路有多少条？其中有多少条通路？

解：

11（1） A=0210，A2=0101

01332A=05314，A=0103

01（2） G中v1到v4的长度为4 的通路有4条；

（3） G中经过v1的长度为3 的回路有3条；

（4） G中长度不超过4 的通路有72条，其中有19条回路。

•v1

•v4

• v2

•v3

题104图

19、求下列无向图中每个顶点的度数；求下列有向图中每个顶点的出度、入度和度。

解：

a•

•d

•e

•c

•b

•f

在这个无向图中d(a)=3,d(b)=6, d(c)=4, d(d)=3, d(e)=0, d(f)=0。

c

b

a

在这个有向图中d(a)=3,d(b)=4, d(c)=3, dd(b)=2,d(c)=1, d(a)=2。

a•

(a)=2, d(a)=1, d(b)=2 ,

•d

•e

•c

•b

•f

题106图

20、求下列无向图的子图、生成子图、由边集诱导的子图和由顶点集诱导的子图。

解：

c

b

它的一个子图

d

a

e

c

b f

它的一个生成子图

d

a

c

b 由边集{(a,b),(a,c),(a,d),(b,d)}诱导出的子图

d

a

b f

由顶点集{a,b,d,f}诱导出的子图

21、求下列赋权图顶点间的距离。

• d

•

a

e

•

4

3 5

7

1 c•

b

•

14

•f

解：

d(a,b)=3, d(a,c)=3, d(a,d)=, d(a,e)=8, d(a,f)=16,

d(b,c)=1, d(b,d)=, d(b,e)=6, d(b,f)=13,

d(c,d)=, d(c,e)=5, d(c,f)=12,

d(d,e)=, d(d,f)=,

d(e,f)=7,

22、求下列赋权图中v1到其他顶点的距离。

v2 10 v4

3

v1 2 2

6

4

3 4 v6

v3 2 v5

解：

S l(v2) l(v3) l(v4) l(v5) l(v6) t l(t)

{v1} 3 4





 v2

3

{v1,v2} 4 13



 v3

4

{v1, v2, v3} 7 6

 v5

6

{v1,v2, v3, v5} 7 10 v4

7

{v1,v2, v3, v5, v4}

{v1,v2, v3, v5, v4, v6}

故v1到v2, v3, v4, v5, v6的距离分别是3，4，7，6，9。

23、求下图的可达矩阵。

d

a

e

b

c

解：

该图的邻接矩阵为

1100010100A=01000000

0100010则

9 v6

9

211000211010100200A2=10100 =000000101001000101000003310031200A3=1200

000001000106430045100A4=3100

00201000001

故图的可达矩阵为

1110011100P =10101000

1100011

24、求下列图的生成树。

解：

下面是它的两棵生成树：

000

01

25、已知一棵无向树中有2个2度顶点、1个3度顶点、3个4度顶点，其余顶点度数都为1。问它有多少个1度顶点？

解：

设它有k个1度顶点，则由欧拉握手定理

vVdeg(v)=2|E|

可得 2|E|=k+4+3+12=k+19。再由于它是一棵树，故

|E|=k+2+1+3-1=k+5

从而2(k+5)=k+19, k=9。故它有9个1度顶点。