- 1、本文档共20页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
图论模拟题
浙江师范大学《图论》考试卷
(2007-2008学年第一学期)
考试类别 闭卷 使用学生 行知数学 051.052.
考试时间 150 分钟 出卷时间 2008年1月4日
说明:考生应将全部答案都写在答题纸上,否则作无效处理。
填空题 (25%)
给定图G
u3 u2 u8
u1 u5 u6
u12 u11
u10
u4 u7 u9
(1)给出图G的一条最长路_______;
(2)给出图G的二个参数值(G)= ,(G)= ;
(3)给出图G的一个最大独立集 ;
(4)作出子图G[u2,u5,u7,u9,u11,u12]________,G-{u8,u9,u12}____________,
G-{u1u3,u1u4,u1u7,u1u10}_________ _______;
2、图G是二分图的充分必要条件是 ;
3、G=(X,Y,E)是二分图,无孤立点,则β1(G) 与α0(G)的关系是 ;
4、Ramsey数r(k,t)、r(k-1,t) 和r(k,t-1) 的关系是 ;
5、G 是含有56个顶点的无回路图,且对G中任两个不相邻的顶点,G+有唯一的回路,则G的边数为____________;
6、图G有Euler环游的充要条件是____;
二、设七个字母在通迅中出现频率分别为a;25%,b;22%,c;20%,d;12%,e;10%,f;6%,g;5%。编一个最优前缀码,并画出相应的最优二元树。 (15%)
证明:非平凡连通图G至少有二个非割点。 (10%)
G是点色数(G)=2的k—正则简单图。证明G有k个边不交的完美对集M1,M2, ┄, Mk,使 E(G)= M1∪M2∪┄∪Mk 。 (13%)
给出平面图G的顶点数p(G)、边数q(G)、面数 和连通分支数ω(G)的一个关系式,并给予证明。 (15%)
G是p个顶点的简单图,对G中每一对不相邻的顶点u、v,均有dG(u)+dG(v)p-1。
(1) 证明G有Hamilton路;(2) G是二连通图吗?为什么?。 (12%)
七、设G是连通图,若对每个真子集V0V(G) ,只要∣V0∣≤k-1,G- V0仍连通.证明q(G)≥kp(G)/2 。 (10%)
《图论》试卷参考答案和评分标准
(2007-2008学年第一学期)
命题教师卜月华 使用学生 行知学院 数学051 052 班 2008年1月4日
填空题
1、(1) C= u5u1u3u2u8u11u12u7u4u10u6u9 (2分);
(2) (G)=2 ,(G)= 2 ; (4分)
(3) {u3,u5,u8,u9,u10,u12} (2分)
(4)
u2 u5
u11
您可能关注的文档
最近下载
- 航空服务对中国民航发展影响的研究.doc
- 合肥工业大学工程图学答汇总全部.pptx
- 建筑工程图集 11SG814:建筑基坑支护结构构造.pdf VIP
- 2025年高考语文易错题:文学类文本阅读之教考衔接题——对语文教材不熟,衔接脱节(含答案).pdf VIP
- 机械制造技术基础习题答案4 .pdf VIP
- 电子元器件知识.pptx VIP
- AS300A门机控制器说明书-2023A1版.pdf
- 2024年高考语文考试(新高考)16文学类文本阅读之教考衔接题——对语文不熟,衔接脱节(解析版).pdf VIP
- 丁锦红-认知心理学(第3版)第3章-知觉与模式识别.pptx VIP
- 灌肠技术操作.pptx VIP
文档评论(0)