2020-2021《图论》期末课程考试试卷（含答案）_第1页
2020-2021《图论》期末课程考试试卷（含答案）_第2页
2020-2021《图论》期末课程考试试卷（含答案）_第3页
2020-2021《图论》期末课程考试试卷（含答案）_第4页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

2020-2021《图论》期末课程考试试卷3写出下图的关联集，并由此求出图的全部断集。（10分）

适用专业：信计本科生考试口期：年月

考试时间：120分钟；考试方式：闭卷；总分100分

一、填空题.（6小题，每小题3分，共18分）

1树中所有度大于1的顶点都是。

2称为欧拉图。

3若G是连通的（p,q）图，则它的•棵生成树有条边。

4求一个连通图的生成树的两种方法：和0

5使图G为八一着色的〃最小数值称为G的o

6如果M中任意两条边在G中均不邻接，则称M是G的一个。

二解答题（5小题，共38分）

I假设A,B……G是7个哨所，监视着11条路段（如下图所示），为节省人力，问至少需要在几个哨所派

人站岗,就可以监视全部路段,写出具体的一个可行方案？（6分）

4写出下图的完全关联矩阵。（8分）

2试作出下列二图作的并，交与环和。（8分）

3

5画出下图的对偶图（在原图上用另一种颜色的笔画出来）。（6分）

4

8求下述网络的最大流.（10分）

三应用题（3小题，共34分）

6如下图，现准备在a,4c,4,e,fg七个居民点设置一银行，各点之间距离由图给出，则银行设

在哪个点可使最大服务距离最小？若要设置两个银行，则设在哪两个点？（12分）

四证明题（1小题,每小题10分，共10分）

7在通信中，0、1、2....7出现的频率如下：

9、若图G=（V,E）不是哈密顿图（„3）,证明至少有一个顶点的度适合dcg（v）＜M/2。

0：30%,I：20%,2:15%,3：10%,4：10%,5：5%,6：5%,7：5%

求传输它们的最佳前缀码。（12分）

2020-2021《图论》期末课程考试试卷答案然后作出它们所有的环和

S(D©S(2)={b,d,e,f},S(D®S(3)={a,b,c,f}

填空题（共6小题，每小题3分，共18分）

S(2)@S(3)={a,c,e,d},

1割点。2顶点的度均为偶数的图。

S(D©S(2)®S(3)={e,c,f)

3PT；4破圈法和避圈法。OOOOO

11000

5色数；6匹配。

4解：01100

00010

解答题（共5小题，共38分）

10111

三、应用题（3小题，共34分）

6解：求出任意两点间的距离，得出每行的最大值，在最大值中取最小值

4.8,故一个银行应设在c,此时最大服务距离为4.8

abcdefg最大值

a034.86.39.36.369.3

b301.83.36.33.346.3

c4.81.801.54.51.52.54.8

d633.31.506346.3

e9.36.34.560359.3

f6.33.31.533026.3

g642.545206

如取两个银行，在上表7列中任取两列，从两列序号的分量中选出

最小数，再在这7个最小数中选出最大者，最后在21个数字中选出最小者

3,所以设两个银行应设在aJ或

（题2图）

7解：：⑴求带权5,5,5,10,10,15,20,30的最优二叉树；

1解：｛A,D,G,E｝和｛A,D,G,B｝都是最小点覆盖,所以至少需要在4个哨

（2）求T所对应的前缀码；

所派人站岗来监视全部路段.

人人文库> 全部分类> 教育资料 > 辅导培训

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论