离散数学测试（图论）

离散数学课程作业（图论）

一、 填空题 1. 2. 3. 4.

任意两点之间都有边相连的无向简单图称为 ；只有点，没有边的图称为 ；只有一个点的图称为 。 有n个顶点的连通无向图中至少有 条边。

无向图G有16条边，3个4度顶点，4个3度顶点，其余顶点的度数均小于3，问G的阶数n至少为 。（答案：11） 写出如下无向图的关联矩阵：

5. 对任何连通平面图恒有：顶点数－边数＋面数＝ 。 6. 一个连通的无向图G是欧拉图当且仅当G中有 个奇度点。 7. 任意一棵非平凡的无向树都恰有 片叶子。 8. 判断如下哪些说法是正确的？

（1） 无向简单图中，无向完全图是边数最多的简单图。 （2） 哈密顿图一定是连通图。 （3） 欧拉图中只有2个奇度点。 （4） 在简单图中，连通但删去一条边后就不连通的图一定是树。

8. 设Ｇ是一个有n个结点的有向完全简单图，则Ｇ的边数为 。 9. 设T为一棵树，边数为m ，顶点个数为n，则 。

A．n?m B．n?m?1 C．n?m?1 D.n?m?2 10. 下列所示图中， 既是平面图，又是二部图， 既是哈密尔顿图又是欧

拉图。

A B C D

二、判断题

1

1. 判断下列各非负整数列哪些是可图化的？哪些是可简单图化的？

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

(4) (d1,d2,…dn)，d1>d2>…>dn≥1 且 (5) (4,4,3,3,2,2)

为偶数

解 易知，除(1)中序列不可图化外，其余各序列都可图化。但除了(5)中序列外，其

余的都是不可简单图化的。(2)中序列有5个数，若它可简单图化，设所得图为G，则(G)=max{5,4,3,2,2}=5，这与定理14.4矛盾。所以(2)中序列不可简单图化。类似可证(4)中序列不可简单图化。

假设(3)中序列可以简单图化，设G=以(3)中序列为度数列。不妨设V={v1，v2，v3，v4} 且d(v1)= d(v2)=d(v3)=3,d(v4)=1，由于d(v4)＝1，因而v4只能与v1，v2，v3之一相邻，于是v1，v2，v3不可能都是3度顶点，这是矛盾的，因而(3)中序列也不可简单图化。

(5)中序列是可简单图化的，下图中两个6阶无向简单图都以(5)中序列为度数列。

2.判断下列命题是否为真？

2

(1)完全图Kn(n≥3)都是欧拉图。

(2)n(n≥2)阶有向完全图都是欧拉图。

(3)完全二部图Kr,s(r,s均为非0正偶数)都是欧拉图

3. 完全图Kn(n≥1)都是哈密顿图吗？

4. 设T是n阶非平凡的无向树，则T中至少有两片树叶。

5.判断下面三个图中哪些是平面图？哪些是二部图？哪些是欧拉图？哪些是Hamilton图？

三、简答与计算题

1. 设无向图G=，V={v1，v2，v3，v4}，E={（v1，v2），（v2，v2），（v2，v4），（v4，

v1），（v3，v4），（v1，v3）}。 （1） 写出G的邻接矩阵；

（2） 求出G中各顶点的度及奇数度顶点的个数。 2. 设有向图G如下图，

（1） 写出G的邻接矩阵；

（2） 求出图D中V1到V4长度为1，2，3，4的通路各有多少条？（0、0、2、2条）

3

（3） （4） （5） （6） （7） 求出图D中V1到V1长度为1，2，3，4的回路各为多少条？（1、1、3、5条） D中长度为4的通路（不含回路）有多少条？(33条) D中长度为4的回路有多少条?（11条） D中长度小于等于4的通路共有多少条？（88条）其中有几条是回路？（22条） 写出D的可达矩阵。

3. 求如下两个图中的最小生成树。

解 用避圈法算法，求出（1）中的生成树T1为图16.5中（1）中绿线边所示的生

成树，W(T1)=6.（2）中的最小生成树为图16.5中（2）中绿边所示的生成树T2，W(T2)=12.

（当然也可以采用破圈法求解）

4.

无向树T有ni个i度顶点，i=2,3,…,k，其余顶点都是树叶，求T的树叶数t。

4

答案:设T为n阶树，V(T)={v1,v2,…,vn}，则T的边数m=n-1。再设T有t片树叶，则

（1） n=n2+n3+…+nk+t=ni+t

（2） m=n-1=ni+t-1 （树的性质）

（3） 由握手定理得

2m=2由（3）解出

ni+2t-2=d(vi)=t+i*ni

t=

i*ni-2ni+2=(i-2)ni+2

5. 一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T有几个顶点？

6.

设7个字母在通信中出现的频率如下：

a：35% b：20% c：15% d：10% e：10% f：5% g：5%

用Huffman算法求传输它们的前缀码。要求画出最优树，指出每个字母对应的编码。并指出传输10n个按上述频率出现的字母，需要多少个二进制数字。 答案

（1）根据权为5,5,10,10,15,20,35画出的最优树为（可不唯一，但其权不变）

5

（2）a,b,…,g对应的编码分别为： a —— 01 b —— 11 c —— 001 d —— 101 e —— 100 f —— 0001 g —— 0000

（3）W(T)=255，这是传输100个按给定比例出现的字母所需要的二进制数字。于是

传输 10n（n≥2）个按给定比例出现的字母需要的二进制字个数为

五、 证明题

w(T)?10n?2.55?10n。 1001. 2.

在n个顶点的无向完全图中共有

n(n?1)条边。 2试证明一个不是孤立点的简单有向图G是强连通的，当且仅当G中有一个回路，它至少包含每个结点一次。

证明若G是每个区域至少由t条边（t≥3）围成的连通平面图，则m?n,m分别是图G的顶点数和边数。

3.

t(n?2)。这里t?2n24. 证明：若无向简单图G＝（n, m）为二部图，试证m?。

4

6

7

本文来源：https://www.bwwdw.com/article/so02.html