图论模拟题.doc

 浙江师范大学《图论》考试卷 （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个顶点的无回路图，且对Ｇ中任两个不相邻的顶点，Ｇ+有唯一的回路，则Ｇ的边数为____________; 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%) 七、设Ｇ是连通图，若对每个真子集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