下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、电子科技大学 图论及其应用 07年研究生试卷 答案 by xjia version1.0 2013年6月19日学 号 姓 名 学 院 密封线以内答 题无效 电子科技大学研究生试卷 (考试时间: 至 ,共_小时)课程名称 图论及其应用 教师 学时 60 学分 教学方式 讲授 考核日期_2007_年_月_日 成绩 考核方式: (学生填写) 一填空题(每题2分,共12分)1教材p6,定理6简单图g=(n,m)中所有不同的生成子图(包括g和空图)的个数是_2m_个;23n=2m设无向图g=(n,m)中各顶点度数均为3,且2n=m+3,则n=_ 6_; m=_9_;3m=n-1,握手定理一棵树有个度数为
2、i的结点,i=2,3,k,则它有2+(i-2)ini个度数为1的结点; 41+2+3+4+6+4下边赋权图中,最小生成树的权值之和为_20_; 5、一天一门呗!?某年级学生共选修9门课。期末考试时,必须提前将这9门课先考完,每天每人只在下午考一门课,则至少需要_9_天才能考完这9门课。二单项选择(每题2分,共10分)1dà(3331)à(220)下面给出的序列中,不是某简单图的度序列的是( d ) (a) (11123); (b) (22222); (c) (3333); (d) (1333).2g的每个点的度是偶数;区别:一个连通图有euler迹当且仅当最多有两个奇点 下
3、列图中,是欧拉图的是( d )3n3的简单图,n2 下列图中,不是哈密尔顿图的是( b )4 下列图中,是可平面图的图的是( b )5下列图中,不是偶图的是(b)三、 (8分)画出具有7个顶点的所有非同构的树解:m=n-1=6四, 用图论的方法证明:任何一个人群中至少有两个人认识的朋友数相同(10分)证明:此题转换为证明任何一个没有孤立点的简单图至少有两个点的度数相同。 参考教材p5。 五(10分) 设g为n 阶简单无向图,n>2且n为奇数,g与g的补图中度数为奇数的顶点个数是否相等?证明你的结论 证明:根据补图定义dgvi+dgvi=n-1。相等。由频序列相同证明有同样奇数的顶点个数。
4、 参考教材p5。六(10分)设g是具有n个顶点的无向简单图,其边数,证明(1) 证明g中任何两个不相邻顶点的度数之和大于等于n。(2)给出一个图,使它具有n个顶点,条边,但不是哈密尔顿图。 证明:(1) 参考教材p79定理6的证明 (2)n=4时,m=4。七、(10分)今有赵、钱、孙、李、周五位教师,要承担语文、数学、物理、化学、英语五门课程。已知赵熟悉数学、物理、化学三门课程,钱熟悉语文、数学、物理、英语四门课程,孙、李、周都只熟悉数学和物理两门课程。问能否安排他们5人每人只上一门自己所熟悉的课程,使得每门课程都有人教,说明理由解:建立图论模型,设a, b, c, d, e分别代表赵、钱、孙
5、、李、周五位教师。a, b, c, d, e分别代表语文、数学、物理、化学、英语五门课程。得模型图如下: a b c d e a b c d e 问题转化为是否存在饱和a, b, c, d, e的匹配存在。 取顶点子集合s=b, c, d, e,因n(s)=b, c, e,所以|ns|<|s|由霍尔定理知:不存在饱和a, b, c, d, e,的匹配。故不能安排他们5人每人只上一门自己所熟悉的课程。 八、(10分)设g是具有n个顶点,m条边,p(个连通分支的平面图,g的每个面至少由k()条边所围成,则 mk(n-p-1)k-2证明:(1)n-m+=p+1 (2)kfdegf=2m 将(2)带入(1)即可得证。九(10分)求下图g的色多项式pk(g).解:参考教材p189习题28该图的补图g如下图所示: h2 h1 它有两个分支,对于hk1,x=x+x2对于h2:n4(g)=1,n3(g)=4,n2(g)=2,n1(g)=0,hk2,x=2x2+4x3+x4所以hg,x=(2x2+4x3+x4)(x+x2)=2x3+6x4+5x5+x6于是g的色多项式pkg=2k3+6k4+5k5+k6 =k(k-1)k-22(k2-5k+8)十、(10分) (1)、在一个只有2个奇度
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 商业交易违约合同模板
- 医师招聘合同模板
- 公司买卖中介合同模板
- 农村加油站租赁合同模板
- 别墅绿化合同模板
- 减免房租合同模板
- 合租合同模板电子版
- 包活合同模板
- 企业环保顾问合同模板
- 修补路面合同模板
- 2024年秋一年级上册9 y w 公开课一等奖创新教学设计
- 考研英语二(作文)模拟试卷2(共43题)
- 科技企业孵化器建设项目可行性研究报告
- 2024年人教版八年级上册英语第三单元课后练习题(含答案和概念)
- 2024年新高考II卷高考生物试卷(真题+答案)
- 汽修厂整改情况报告范文
- 2024秋九年级语文上册 第3单元 14诗词三首《行路难》教案 新人教版
- 医疗垃圾外泄应急演练课件
- 2024住建部建设工程合同模板
- JT-T 1218.5-2024 城市轨道交通运营设备维修与更新技术规范 第5部分:通信
- 妊娠合并糖尿病品管圈
评论
0/150
提交评论