离散数学测验题图论部分.docx

离散数学测验题图论部分.docx

《离散数学测验题图论部分.docx》由会员分享，可在线阅读，更多相关《离散数学测验题图论部分.docx（18页珍藏版）》请在冰点文库上搜索。

离散数学测验题图论部分

离散数学图论单元测验题

一、单项选择题（本大题共10小题，每小题2分，共20分）

1、在图G＝中，结点总度数与边数的关系是（）

（A）deg（vi）=2E（B）deg（vi）=E（C）

（D）

2、设D是n个结点的无向简单完全图，则图D的边数为（）

（A）n（n－1）（B）n（n+1）（C）n（n－1）/2（D）n（n+1）/2

3、设G＝为无向简单图，V=n，（G）为G的最大度数，则有

（A）（G）n（D）（G）n

4、图G与G的结点和边分别存在一一对应关系，是G≌G（同构）的（）

（A）充分条件（B）必要条件（C）充分必要条件（D）既非充分也非必要条件

5、设

，则与V能构成强连通图的边集合是（）

（A）

（B）

（C）

6、有向图的邻接矩阵中，行元素之和是对应结点的（），列元素之和是对应结点的（）

（A）度数（B）出度（C）最大度数（D）入度

7、设图G的邻接矩阵为

则G的边数为（）．

A．5B．6C．3D．4

8、设

为连通平面图且有r个面，则r＝（）

（A）m－n+2（B）n－m－2（C）n+m-2（D）m+n+2

9、在5个结点的二元完全树中，若有4条边，则有（）片树叶。

（A）2（B）3（C）5（D）4

10、图2是（）

（A）完全图（B）欧拉图（C）平面图（D）哈密顿图

二、填空题（本大题共10小题，每题2分，共20分）

1、设图G＝和G＝,若，则G是G的真子图，若，则G是G的生成子图.

2、设G是完全二叉树，G有15个结点，其中有8个是树叶，则G有条边，G的总度数是，G的分支点数是，G中度数为3的结点数是.

3、一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，问它有几个度数为1的结点。

4、画出满足下列条件的图：

（1）画一个有一条欧拉回路和一条哈密顿回路的图；

（2）画一个有一条欧拉回路，但没有哈密顿回路的图；

（3）画一条没有欧拉路，但有一条哈密顿回路的图.

5、设G是n个结点的简单图，若G中每对结点的度数之和，则G一定是哈密顿图.

6、一个有向树T称为根树，若，其中称为树根，

称为树叶.

7、设G是平面图，G有8个面，每个面的度数都是3，则G有__________条边，G有__________个顶点。

8、设G是有n个结点，m条边的连通图，要确定G的一棵生成树，必须删去G的条边.

9、在下图中，哪些是欧拉图？

哪些是哈密顿图？

哪些是平面图？

（1）

（2）

10、设G是n阶无向带权边连通图，各边的权均为a（a>0）,设T是G的一棵最小生成树，则T的权W（T）=________（n-1）*a_______________。

三、计算题（本大题共4小题，每小题10分，共40分）

1、设G＝是一个无向图，

（1）G＝的V，E各是多少？

（2）画出G的图示；

（3）指出与v3邻接的结点，以及与v3关联的边；（4）指出与e1关联的结点；

（5）该图是否有孤立结点和孤立边？

（6）求出各结点的度数；

2、设图G是具有3个顶点的无向完全图，试问

（1）G有多少个子图？

（2）G有多少个生成子图？

（3）如果没有任何两个子图是同构的，则G的子图个数是多少？

将它们构造出来.

3．图G=，其中V={a,b,c,d,e,f}，E={（a,b）,（a,c）,（a,e）,（b,d）,（b,e）,（c,e）,（d,e）,（d,f）,（e,f）}，对应边的权值依次为5，2，1，2，6，1，9，3及8．

（1）画出G的图形；

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

（3）求出G权最小的生成树及其权值．

4．设有一组权为2,3,5,7,11,13,17,19,23,29,31,试

（1）画出相应的最优二叉树；

（2）计算它们的权值．

四、证明题（本大题共3小题，任选2题，每小题10分，共20分）

1．若无向图G中只有两个奇数度结点，则这两个结点一定是连通的．

2．设G是一个n阶无向简单图，n是大于等于2的奇数．证明图G与它的补图

中的奇数度顶点个数相等．

3．设连通图G有k个奇数度的结点，证明在图G中至少要添加

条边才能使其成为欧拉图．

补充

1、若图G是不连通的，则G的补图G是连通的。

2、当且仅当G的一条边e不包含在G的回路中时，e才是G的割边。

3、设G是简单平面图，则它—定有一个度数≤5的结点。

解答：

一、单项选择题（本大题共10小题，每小题2分，共20分）

1、在图G＝中，结点总度数与边数的关系是（）

（A）deg（vi）=2E（B）deg（vi）=E（C）

（D）

答案：

（C）

2、设D是n个结点的无向简单完全图，则图D的边数为（）

（A）n（n－1）（B）n（n+1）（C）n（n－1）/2（D）n（n+1）/2

答案：

（C）

3、设G＝为无向简单图，V=n，（G）为G的最大度数，则有

（A）（G）n（D）（G）n

答案：

（A）

解答：

因为G中无平行边和环，任何结点最多有n－1条边与其相关联，最大度数小于或等于n－1.故选择（A）

4、图G与G的结点和边分别存在一一对应关系，是G≌G（同构）的（）

（A）充分条件（B）必要条件（C）充分必要条件（D）既非充分也非必要条件

答案：

（B）

解答：

见图的同构定义.

5、设

，则与V能构成强连通图的边集合是（）

（D）

（E）

（F）

（G）

答案：

（A）

解答：

有向图G任何一对结点间都互相可达，称该图是强连通的.（A）所给的边的集合存在一个通过所有结点的通路.故选择（A）.

6、有向图的邻接矩阵中，行元素之和是对应结点的（），列元素之和是对应结点的（）

（A）度数（B）出度（C）最大度数（D）入度

答案：

（B），（D）

解答：

见邻接矩阵的定义.

7、设图G的邻接矩阵为

则G的边数为（）．

A．5B．6C．3D．4

答案：

（D）

8、设

为连通平面图且有r个面，则r＝（）

（A）m－n+2（B）n－m－2（C）n+m-2（D）m+n+2

答案：

（A）

解答：

见欧拉公式.

9、在5个结点的二元完全树中，若有4条边，则有（）片树叶。

（A）2（B）3（C）5（D）4

答案：

（B）

解答：

二元完全树，即每个结点只有0个或2树枝的树，树根必有2个树枝，于是2个树枝只能其一又有2个树枝，而另一个就无树枝.满足5个结点4条边.可见有3片树叶.选择（B）正确.

10、图2是（）

（A）完全图（B）欧拉图（C）平面图（D）哈密顿图

答案：

（D）

解答：

因为n=6,每对结点度数之和

大于或大于6，满足存在哈密顿回路的条

件，故为哈密顿图.选择（D）正确.

二、填空题（本大题共10小题，每题2分，共20分）

1、设图G＝和G＝,若，则G是G的真子图，若，则G是G的生成子图.

答案：

解答：

见真子图和生成子图的定义.

2、设G是完全二叉树，G有15个结点，

其中有8个是树叶，则G有条边，G的总度数是，G的分支点数是，G中度数为3的结点数是.

答案：

14；28；7；6.

解答：

可画图如图3.有8个树叶，15个结点的完全

3、一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，问它有几个度数为1的结点。

解：

设有x个度数为1的结点，结点数v＝2+1+3+x＝6+x，边数e＝v-1=5+x。

而2e＝∑deg（vi），故2（5+x）=2·2+1·3+3·4+x·1，x＝9。

4、画出满足下列条件的图：

（1）画一个有一条欧拉回路和一条哈密顿回路的图；

（2）画一个有一条欧拉回路，但没有哈密顿回路的图；

（3）画一条没有欧拉路，但有一条哈密顿回路的图.

5、设G是n个结点的简单图，若G中每对结点的度数之和，则G一定是哈密顿图.

答案：

大于或等于n

6、一个有向树T称为根树，若，其中称为树根，

称为树叶.

答案：

若有向图T恰有一个结点的入度为0，其余结点入度为1；入度为0的结点；入度为1的结点.

解答：

见根树、树根、树叶的定义.

7、设G是平面图，G有8个面，每个面的度数都是3，则G有__________条边，G有__________个顶点。

解答：

12条边，6个顶点

8、设G是有n个结点，m条边的连通图，要确定G的一棵生成树，必须删去G的条边.

答案：

m－n+1

解答：

见生成树的破圈或避圈求法.

9、在下图中，哪些是欧拉图？

哪些是哈密顿图？

哪些是平面图？

（1）

（2）

解答：

欧拉图：

5；哈密顿图：

4、5、6；平面图：

除6都是

10、设G是n阶无向带权边连通图，各边的权均为a（a>0）,设T是G的一棵最小生成树，则T的权W（T）=________（n-1）*a_______________。

三、计算题（本大题共4小题，每小题10分，共40分）

1、设G＝（V,E）是一个无向图，

（1）G＝的V，E各是多少？

（2）画出G的图解；

（3）指出与v3邻接的结点，以及与v3关联的边；（4）指出与e1关联的结点；

（5）该图是否有孤立结点和孤立边？

（6）求出各结点的度数；

解

（1）G=中，有V=8个结点，E=7条边的图，故又称是8阶图.

（2）所给图G的一个图解，如图4.

（3）结点v1,v2,v4与v3邻接，v3关联

的边为e1,e2,e3.

（4）与边e1关联的结点为v2,v3.

（5）结点v6是孤立点；e5是孤立边.

（6）deg（v1）=3，deg（v2）=2，deg（v3）=3，

deg（v4）=2＝deg（v5），deg（v6）=0，

deg（v7）=1=deg（v8）.

2、设图G是具有3个顶点的无向完全图，试问

（1）G有多少个子图？

（2）G有多少个生成子图？

（3）如果没有任何两个子图是同构的，则G的子图个数是多少？

将它们构造出来.

解

（1）因为只有1个结点的子图有

个（平凡子图）；

2个结点的子图有

个；3个结点的子图有

个；

所以，G共有3＋6＋8＝17个子图.

（2）G的生成子图，含有G的所有结点，G有3条边，构成子图时，每条边有选中或不选中两种可能，所以G的生成子图的个数是23＝8个.

（3）G的所有不同构的子图有7个，如图6所示.

G1G2G3G4G5G6G7

图6

3．图G=，其中V={a,b,c,d,e,f}，E={（a,b）,（a,c）,（a,e）,（b,d）,（b,e）,（c,e）,（d,e）,（d,f）,（e,f）}，对应边的权值依次为5，2，1，2，6，1，9，3及8．

（1）画出G的图形；

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

（3）求出G权最小的生成树及其权值．

解：

（1）因为V={a,b,c,d,e,f}

E={（a,b）,（a,c）,（a,e）,（b,d）,（b,e）,

（c,e）,（d,e）,（d,f）,（e,f）}，

权值依次为5，2，1，2，6，1，9，3及8

所以，G的图形如右图所示：

（2）分析：

设G=是一个简单图，其中V={v1，v2，…，vn}，则n阶方阵A（G）=（aij）称为G的邻接矩阵．其中

邻接矩阵：

（3）用避圈法：

第1步：

选（a,e）和（c,e）边；

第2步：

选（b,d）边；（为什么不选（a,c）？

）

第3步：

选（d,f）边；

第4步：

选（a,b）边．

这样，得到了最小的生成树，如右图中粗线所示．

最小的生成树的权为1+1+5+2+3=12．

上学期作业中的最小的生成树求的不对，主要是没有把握“取权数最小的边，且与前面取到的边不构成圈”，常常是只注意取权数最小的边了，而忽略“不构成圈”的要求。

问：

如果结点集是V={a,b,c,d,e}，边集E={（a,b）,（a,c）,（a,e）,（b,d）,（b,e）,（c,e）,（d,e）}，对应边的权值依次为5，2，1，2，6，1，9，那么会求吗？

4．设有一组权为2,3,5,7,11,13,17,19,23,29,31,试

（1）画出相应的最优二叉树；

（2）计算它们的权值．

解：

（1）最优二叉树如右图所示：

方法（Huffman）：

从2,3,5,7,11,13,17

19,23,29,31中选2,3为最低层结点，并

从权数中删去，再添上他们的和数，即

5,5,7,11,13,17,19,23,29,31；

再从5,5,7,11,13,17,19,23,29,31中选

5,5为倒数第2层结点，并从上述数列中

删去，再添上他们的和数，即7,10,11,13,

17,19,23,29,31；

然后，从7,10,11,13,17,19,23,29,31中选7,10和11,13为倒数第3层结点，并从上述数列中删去，再添上他们的和数，即17,17,24,19,23,29,31；

……

（2）权值为：

26+36+55+74+114+134+173+193+233+293+312

=12+18+25+28+44+52+51+57+69+87+62=505

讲评：

作业中最优二叉树都画对了，但计算总权值时把有些权的层数计算错了，导致总权值计算错误。

问：

如果一组权为2,3,6,9,13,15,能否画出最优二叉树？

四、证明题（本大题共3小题，任选2题，每小题10分，共20分）

1．若无向图G中只有两个奇数度结点，则这两个结点一定是连通的．

证明：

用反证法．设G中的两个奇数度结点分别为u和v．假设u和v不连通，即它们之间无任何通路，则G至少有两个连通分支G1，G2，且u和v分别属于G1和G2，于是G1和G2各含有一个奇数度结点．这与定理3.1.2的推论矛盾．因而u和v一定是连通的．

2．设G是一个n阶无向简单图，n是大于等于2的奇数．证明图G与它的补图

中的奇数度顶点个数相等．

证明：

设

，

．则

是由n阶无向完全图

的边删去E所得到的．所以对于任意结点

，u在G和

中的度数之和等于u在

中的度数．由于n是大于等于2的奇数，从而

的每个结点都是偶数度的（

度），于是若

在G中是奇数度结点，则它在

中也是奇数度结点．故图G与它的补图

中的奇数度结点个数相等．

3．设连通图G有k个奇数度的结点，证明在图G中至少要添加

条边才能使其成为欧拉图．

证明：

由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k是偶数．

又根据定理4.1.1的推论，图G是欧拉图的充分必要条件是图G不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图．

故最少要加

条边到图G才能使其成为欧拉图。

1、若图G是不连通的，则G的补图G是连通的。

证明若图G＝是不连通的，可设图G的连通分支是G（V1），G（V2），…，G（Vm）（m≥2）。

由于任意两个连通分支G（Vi）与G（Vj）（i≠j）之间不连通，因此两个结点子集Vi与Vj之间的所有连线都在图G的补图G'中。

任取两个结点u和v,有两种情形：

a）u和v分别属于两个不同结点子集Vi与Vj。

由上可知G'包含边（u，v），故u和v在G'中是连通的。

b）u和v属于同—个结点子集Vi。

可在另一个结点子集Vj中取一个结点w,由上可知边（u，w）及边（v,w）均在G'中，故邻接边（u，w）和（w,v）组成的路连接结点u和v,即u和v在G'中也是连通的。

由此可知，当图G不是连通图时，G'必是连通图。

2、当且仅当G的一条边e不包含在G的回路中时，e才是G的割边。

证明必要性。

设e是连通图G的割边，e关联的两个结点

是u和v。

如果e包含在G的一个回路中，那么除边e＝（u，v）外

还有一条分别以u和v为端点的路，所以删去边e后，G仍为连通

图，这与e是割边相矛盾。

充分性。

如果边e不包含在G的任一回路中，那么连接结点

u和v只有边e，而不会有其它连接u和v的任何路。

因为如果连

接u和v还有不同与边e的路，此路与边e就组成一条包含边e

的回路，从而导致矛盾。

所以删去边e后，u和v就不连通，故边

e是割边。

3、设G是简单平面图，则它—定有一个度数≤5的结点。

证明不妨设G是连通的。

若不连通，就可考察G中的一个连通分支。

因G是简单图，所以每个面至少有三条边，所以，3r≤2e，即有r≤

。

如果每个结点的度数都≥6，则6v≤2e,即有v≤

。

由欧拉公式可得

2=v-e+r≤

-e+

=0

矛盾。

所以，G中至少有一个结点的度数≤5。