电大离散数学图论部分期末综合练习题25
上亿文档资料，等你来发现
电大离散数学图论部分期末综合练习题25
一、单项选择题；1．设图G＝&V,E&，v?V，则下；C．?deg(v)?2ED．?deg(v)?E；v?V；v?V；2．设无向图G的邻接矩阵为；?0?1??1??0?0?；1；0?0??1?0??；则G的边数为()．；A．6B．5C．4D．3；e3．如右图所示，以下说法正确的是()．A．{(；adB．{(a
一、单项选择题1．设图G＝&V, E&，v?V，则下列结论成立的是 (
A．deg(v)=2?E?
B． deg(v)=?E?C．?deg(v)?2E
D．?deg(v)?Ev?Vv?V2．设无向图G的邻接矩阵为?0?1??1??0?0?1001110000010010??1?0??1?0??，则G的边数为(
3．如右图所示，以下说法正确的是 (
) ． A．{(a, e)}是割边a
B．{(a, e)}是边割集C．{(a, e) ,(b, c)}是边割集
c bD．{(d, e)}是边割集注：如果只给出图的结点和边，也应该会做．如：
若图G=&V, E&，其中V={ a, b, c, d, e }，E={ (a, b), (a, c) , (a, e) , (b,c) , (b, e) , (c, e) , (e, d)}，则该图中的割边是什么？4．设有向图（a）、（b）、（c）与（d）如下图所示，则下列结论成立的是(
)． A．（a）是强连通的
B．（b）是强连通的C．（c）是强连通的
D．（d）是强连通的 问：上图中，哪个仅为弱连通的？5．设完全图Kn有n个结点(n?2)，m条边，当（
）时，Kn中存在欧拉回路．A．m为奇数
B．n为偶数
C．n为奇数
D．m为偶数 6．设G是连通平面图，有v个结点，e条边，r个面，则r= (
A．e－v＋2
B．v＋e－2
C．e－v－2
D．e＋v＋2
本题主要检查大家是否掌握了欧拉定理．问：如果连通平面图G有4个结点，7条边，那么图G有几个面？7．无向简单图G是棵树，当且仅当(
)．A．G连通且边数比结点数少1
B．G连通且结点数比边数少1C．G的边数比结点数少1
D．G中没有回路． 问当树T有6个结点，那么它有多少条边？8．已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为（
D．3握手定理
?deg(v)?2|E|，树e?v?1v?V二、填空题1．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结a
b点，则G的边数是
． 握手定理
2e??deg(v)?1?1?2?2?3?3?4?4?30，v?Vf
d2．设给定图G (如右图所示)，则图G的点割集是 ．提示：若f是图G的割点，则{f}是图G的点割集，删除f点后图G是连通吗？3．无向图G存在欧拉回路，当且仅当G连通且．
4．若图G=&V, E&中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为
W(G-S)? |S|
．5．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去条边后使之变成树．（??边后，可以确定图G的一棵生成树）由握手定理（定理3.1.1）知道图G有18?2=9 条边，树的等价定义要求“图T连通且e=v-1=6-1=5”，所以应该去掉9-5=4条边．三、判断说明题1．如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路．
分析：先复习欧拉图的判别定理：解：不正确．因为题中的图G没有“连通”的条件．问：“如果图G是无向连通图，则图G存在一条欧拉回路”a是否正确？（还需要满足无奇数度结点）．b d 2．如右图所示的图G不是欧拉图而是汉密尔顿图． 解：正确．图G有4个3度结点a，b，d，f，所以图G不是 e g f欧拉图．图G有汉密尔顿回路abefgdca，所以图G是图G汉密尔顿图．注意：汉密尔顿图不一定是欧拉图，为什么？． 3．设G是一个有7个结点16条边的连通图，则G为平面图．利用定理4.3.3 设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．解：不正确．因为题中的连通简单平面图有v=7个结点，e=16条边，那么16?3?7-6=15，由定理4.3.3知道，图G不是平面图．
问：“完全图K6是平面图”是否正确？不正确．因为完全图K6有6个结点n(n?1)2?6(6?1)2?15条边，且15?3?6-6=12，即e ? 3v-6对K6不成立，所以K6不是平面图． 四、计算题 1．设G=&V，E&，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，试(1) 给出G的图形表示；
(2) 写出其邻接矩阵； (3) 求出每个结点的度数；
(4) 画出其补图的图形． 解：(1) 因为V={ v1，v2，v3，v4，v5}，v1
E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，所以G的图形表示为：v2
v5 ?00100??0?(2)邻接矩阵： ?1??0?0?011010111101??1?
?1?0??0v3 v4(3) 由G的图形可知，v1，v2，v3，v4，v5结点的度数依次为1，2，4，3，2 (4)补图（见图2）如下：v1 v1 v2 v2v5
v5?v4 v4 vv3 3图1
图2 注意：补图中，如果没有标出结点v3，则是错的． 2．图G=&V, E&，其中V={ a, b, c, d, e}，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) }，对应边的权值依次为2、1、2、3、6、1、4及5，试（1）画出G的图形；
（2）写出G的邻接矩阵；a （3）求出G权最小的生成树及其权值．解 （1）因为V={ a, b, c, d, e}，
E={ (a, b), (a, c), (a, e), (b, d),b
(b, e), (c, e), (c, d), (d, e)}，
所以G的图形如右图表示． 1（2）由图得图G的邻接矩阵为：e d 5?0?1?A??1??0?1?110001100111101?1?1??1 ??1?0?（3）图G有5个结点，其生成树有4条边，用Kruskal算法（避圈法）求其权最小的生成树T：a 第1步，取具最小权1的边(a, c)；第2步，取剩余边中具最小权1的边(c, e)； 第3步，取剩余边中不与前2条边构成回路b
c 的具最小权2的边(a, b)；第4步，取剩余边中不与前3条边构成回路的具最小权3的边(b, d)．e 所求最小生成树T如右下图，其权为． dW(T)?1??1?2?33．设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优二叉树的权．解：方法（Huffman）：从2, 3, 5, 7, 17, 31中选2, 3为最低层结点，并从权数中删去，再添上他们的和数，即5, 5, 7, 17, 31；65 再从5, 5, 7, 17, 31中选5, 5为倒数第2层结点，并从 上述数列中删去，再添上他们的和数，即7, 10, 17, 31；34
然后，从7, 10, 17, 31中选7, 10为倒数第3层结点， 3117 并从上述数列中删去，再添上他们的和数，即17, 17, 31；17?? 10 7 最优二叉树如右图所示．5
最优二叉树权值为：2?5+3?5+5?4+7?3+17?2+31?15=10+15+20+21+34+31=1312 3五、证明题1．设G是一个n阶无向简单图，n是大于等于3的奇数．证明图G与它的补图G中的奇数度顶点个数相等．证明：设G??V,E?，G??V,E??．则E?是由n阶无向完全图Kn的边删去E所得到的．所以对于任意结点u?V，u在G和G中的度数之和等于u在Kn中的度数．由于n是大于等于3的奇数，从而Kn的每个结点都是n?1?2的偶数度，于是若u?V在G中是奇数度结点，则它在G中也是奇数度结点．故图G与它的补图G中的奇数度结点个数相等．2．设连通图G有k个奇数度的结点，证明在图G中至少要添加条边才能使2k其成为欧拉图．证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k是偶数． 又根据定理4.1.1的推论，图G是欧拉图的充分必要条件是图G不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图．故最少要加条边到图G才能使其成为欧拉图．2k包含各类专业文献、文学作品欣赏、外语学习资料、生活休闲娱乐、各类资格考试、行业资料、幼儿教育、小学教育、高等教育、专业论文、电大离散数学图论部分期末综合练习题25等内容。
　　【】　
您可在本站搜索以下内容：
　 电大离散数学数理逻辑部... 暂无评价 18页 免费 离散数学图论部分综合练......离散数学期末复习辅导(二) 离散数学图论部分期末复习辅导一、单项选择题 1.设图...
　 离散数学图论部分综合练习... 1页 免费 电大离散数学图论部分期末... 暂无...连通图还是弱连通图的判断,希望大家掌握图论综合作业单 项选择题中的第 4 题...
s　离散数学图论部分综合练习本课程综合练习共分 3 次,分别是集合论部分、图论部分、数理逻辑部分的 综合练习,这 3 次综合练习基本上是按照考试的题型安排练习题目,...
　 离散数学图论部分综合练习_从业资格考试_资格考试/认证_教育专区。离散数学图论部分综合练习本课程综合练习共分 3 次,分别是集合论部分、图论部分、数理逻辑部分的 ...
s　图论部分形成性考核书面本课程形成性考核书面作业共 3 次, 内容主要分别是集合论部分、 图论部分、 数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题...
　电大离散数学凸轮复习题答案图论部分综合练习辅导 离散...们熟悉期末考试的题型, 能够较好地完成这一部分主要...
　 电大离散数学作业s答案(图论部分)_数学_自然科学_专业资料。★ 形成性考核作业... 内容主要分别是集合论部分、 图论部分、 数理逻辑部分的综合练习,基本上是按照...
　 .离散数学图论部分综合练习一、单项选择题 1.设图 G 的邻接矩阵为 ?0 ?0 ? ?1 ? ?0 ?0 ? 0 1 0 0? 0 0 1 1? ? 0 0 0 0? ? 1 0 0 ...
　 离散数学图论部分综合练习(补充)离散数学图论部分综合练习(补充)隐藏&& 图论部分综合练习 补充) 综合练习( 离散数学图论部分综合练习(补充)一、单项选择题 4.设有...
赞助商链接
别人正在看什么？
赞助商链接75离散数学图论部分经典试题及答案
上亿文档资料，等你来发现
75离散数学图论部分经典试题及答案
离散数学图论部分综合练习；一、单项选择题；1．设图G的邻接矩阵为；?01?10??10；??01??01；100?；011??000?；001?010??；则G的边数为()．；A．6B．5C．4D．3；2．已知图G的邻接矩阵为；，则G有（）．；A．5点，8边B．6点，7边C．6点，8边D．5；3．设图G＝&V,E&，则下列结论成；A．deg(V)
　离散数学图论部分综合练习 一、单项选择题1．设图G的邻接矩阵为?01?10??10??01??01100?011??000??001?010?? 则G的边数为(
D．32．已知图G的邻接矩阵为 ， 则G有（
）．A．5点，8边
B．6点，7边
C．6点，8边
D．5点，7边3．设图G＝&V, E&，则下列结论成立的是 (
)．A．deg(V)=2?E?
B．deg(V)=?E? C．?deg(v)?2E
D．?deg(v)?Ev?Vv?Va dc图一b
fe4．图G如图一所示，以下说法正确的是 (
) ． A．{(a, d)}是割边 B．{(a, d)}是边割集 C．{(d, e)}是边割集 D．{(a, d) ,(a, c)}是边割集5．如图二所示，以下说法正确的是 (
)． A．e是割点
B．{a, e}是点割集 C．{b, e}是点割集
D．{d}是点割集6．如图三所示，以下说法正确的是 (
) ．图二 A．{(a, e)}是割边
B．{(a, e)} 是边割集C．{(a, e) ,(b, c)}是边割集
D．{(d, e)}是边割集 1 图三7．设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是 (
)． 图四A．（a）是强连通的
B．（b）是强连通的C．（c）是强连通的
D．（d）是强连通的 应该填写：D8．设完全图Kn有n个结点(n≥2)，m条边，当（
）时，Kn中存在欧拉回路．A．m为奇数
B．n为偶数
C．n为奇数
D．m为偶数 9．设G是连通平面图，有v个结点，e条边，r个面，则r= (
)．A．e－v＋2
B．v＋e－2
C．e－v－2
D．e＋v＋2 10．无向图G存在欧拉通路，当且仅当(
)． A．G中所有结点的度数全为偶数
B．G中至多有两个奇数度结点 C．G连通且所有结点的度数全为偶数 D．G连通且至多有两个奇数度结点11．设G是有n个结点，m条边的连通图，必须删去G的(
)条边，才能确定G的一棵生成树．A．m?n?1
D．n?m?1 12．无向简单图G是棵树，当且仅当(
)．A．G连通且边数比结点数少1
B．G连通且结点数比边数少1 C．G的边数比结点数少1
D．G中没有回路．二、填空题1．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结b a点，则G的边数是
．2．设给定图G(如图四所示)，则图G的点割f2c d e 图四集是
．3．若图G=&V, E&中具有一条汉密尔顿回路， 则对于结点集V的每个非空子集S，在G中删除S 中的所有结点得到的连通分支数为W，则S中结点 数|S|与W满足的关系式为
．4．无向图G存在欧拉回路，当且仅当G连通 且
．5．设有向图D为欧拉图，则图D中每个结点的入度 应该填写：等于出度6．设完全图Kn有n个结点(n?2)，m条边，当
时，Kn中存在欧拉回路．7．设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v，e和r满足的关系式
．8．设连通平面图G的结点数为5，边数为6，则面数为．
9．结点数v与边数e满足10．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去11．已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为
．12．设G＝&V, E&是有6个结点，8条边的连通图，则从G中删去
条边，可以确定图G的一棵生成树．13．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素
，则该序列集合构成前缀码．三、判断说明题1．如图六所示的图G存在一条欧拉回路．v12图六3 2．给定两个图G1，G2（如图七所示）：（1）试判断它们是否为欧拉图、汉密尔顿图？并说明理由． （2）若是欧拉图，请写出一条欧拉回路．3v1v6v4v5v2v3v1 v6v5 v2v34图八图七3．判别图G(如图八所示)是不是平面图， 并说明理由．4．设G是一个有6个结点14条边的连 通图，则G为平面图． 四、计算题1．设图G??V，E?，其中V??a1, a2, a3, a4, a5?,E???a1, a2?，?a2, a4?，?a3, a1?，?a4, a5?，?a5, a2??（1）试给出G的图形表示； （2）求G的邻接矩阵；（3）判断图G是强连通图、单侧连通图还是弱连通图？2．设图G=&V，E&，V={ v1，v2，v3，v4，v5}，E={ (v1, v2)，(v1, v3)，(v2, v3)，(v2, v4)，(v3, v4)，(v3, v5)，(v4, v5) }，试（1）画出G的图形表示；
（2）写出其邻接矩阵； （2）求出每个结点的度数；
（4）画出图G的补图的图形． 3．设G=&V，E&，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，试（1）给出G的图形表示；
（2）写出其邻接矩阵； （3）求出每个结点的度数；
（4）画出其补图的图形． 4．图G=&V, E&，其中V={ a, b, c, d, e}，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) }，对应边的权值依次为2、1、2、3、6、1、4及5，试（1）画出G的图形；
（2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值．5.用Dijkstra算法求右图中A点到其它各点的最短路径。 6．设有一组权为2,3,5,7,11,13,17,19,23,29,31,试（1）画出相应的最优二元树；
（2）计算它们的权值． 7．给出右边所示二元有序树的三种遍历结果． 4
五、证明题1．若无向图G中只有两个奇数度结点，则这两个结点一定是连通的． 2．设G是一个n阶无向简单图，n是大于等于2的奇数．证明图G与它的补图G中的奇数度顶点个数相等．3．设连通图G有k个奇数度的结点，证明在图G中至少要添加使其成为欧拉图．参考解答一、单项选择题1．B
12．A二、填空题1．15
2．{f}，{c，e}
3．W?|S| 4．所有结点的度数全为偶数
5．等于出度 6．n为奇数
7．v-e+r =2
11．512．3
13．0三、判断说明题1．解：正确．因为图G为连通的，且其中每个顶点的度数为偶数．
2．解：（1）图G1是欧拉图．
因为图G1中每个结点的度数都是偶数．图G2是汉密尔顿图．因为图G2存在一条汉密尔顿回路（不惟一）：
a(a, b)b(b, e) e(e, f) f (f, g) g(g, d) d(d, c) c(c, a)a问题：请大家想一想，为什么图G1不是汉密尔顿图，图G2不是欧拉图。（2）图G1的欧拉回路为：（不惟一）：v1(v1, v2) v2 (v2, v3) v3 (v3, v4) v4 (v4, v5)v5
(v5, v2) v2 (v2, v6)v6 (v6, v4) v4 (v4, v1)v1 3．解：图G是平面图．因为只要把结点v2与v6的连线(v2, v6)拽 到结点v1的外面，把把结点v3与v6的连线 5k条边才能2vv6 v5v2v3图九 包含各类专业文献、应用写作文书、专业论文、中学教育、幼儿教育、小学教育、高等教育、生活休闲娱乐、行业资料、文学作品欣赏、外语学习资料、75离散数学图论部分经典试题及答案等内容。　
　　【】　
您可在本站搜索以下内容：
s　 《离散数学》试题及答案 8页 免费 离散数学图论部分经典试... q页 4下载券...离散数学图论部分综合练习本课程综合练习共分 3 次,分别是集合论部分、图论部分...
　 离散数学图论部分经典试题... q页 10财富值 电大离散数学作业s答案(图... ... 离散数学图论部分综合练习辅导 离散数学图论部分综合练习辅导 图论部分本次活动是...
s　★ 形成性考核作业 ★ 离散数学作业 s 姓名: 学号: 得分: 教师签名: 教师签名: 离散数学图论部分形成性考核书面作业 离散数学图论部分形成性考核书面作业 图论...
　图论部分综合练习辅导 离散数学 11 春图论部分综合练习辅导大家好!本学期的第二... 离散数学图论部分经典试... q页 4下载券 2004图论复习题答案 4页 1下载券...
　离散数学习题解答 习题六 (第六章 图论) 1. 从日常生活中列举出三个例子, 并由这些例子自然地导出两个无向图及一个向图。 [解] ①用 V 代表全国城市的...
q　 离散数学图论部分综合练习... 8页 免费 图论练习题200q(学生练习) 6页 免费 图论习题参考答案 12页 2财富值 离散数学图论部分经典试题... q页 10财富值 ...
　 电大离散数学作业s答案(图论部分)_数学_自然科学_专业资料。★ 形成性考核作业...(除单项选择题外)安排练 习题目,目的是通过综合性书面作业,使同学自己检验学习...
　 组合数学与图论复习题及参考答案_工学_高等教育_教育专区。组合数学与图论复习...二分图定义:G 的点可以可以分成互不相交的两部分 X,Y。如果一条边是两 个...
　 离散数学图论部分综合练习_从业资格考试_资格考试/...参考解答 一、单项选择题 1.B q.A 2.D 10.D... 绝对经典搞笑照片 81份文档
笑话大全集 笑话大全...
赞助商链接
别人正在看什么？
赞助商链接离散数学小论文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
35页¥10.006页免费52页免费5页¥3.006页¥3.00 7页¥3.002页免费15页免费5页免费3页免费
喜欢此文档的还喜欢1页免费4页1下载券2页免费3页免费4页1下载券
离散数学小论文|
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
你可能喜欢离散数学应用论文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
离散数学应用论文|离​散​数​学​在​电​气​科​学​中​的​应​用
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
你可能喜欢