浙江师范大学《图论》考试卷（2007－2008学年第一学期）考试类别 闭卷 使用学生 行知数学 051.052.考试时间 150 分钟 出卷时间 2008年1月4日说明：考生应将全部答案都写在答题纸上，否则作无效处理。

一、填空题 (25%)1、给定图G11（1）给出图G 的一条最长路＿＿＿＿＿＿＿；（2）给出图G 的二个参数值λ(G)= ,κ(G)= ；（3）给出图G 的一个最大独立集 ；（4）作出子图G[u 2,u 5,u 7,u 9,u 11,u 12]________,G-{u 8,u 9,u 12}____________,G-{u 1u 3,u 1u 4,u 1u 7,u 1u 10}_________ _______；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个顶点的无回路图，且对Ｇ中任两个不相邻的顶点v u ,，Ｇ+uv 有唯一的回路，则Ｇ的边数为____________;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 个边不交的完美对集M 1,M 2, ┄, M k ，使 E(G)= M 1∪M 2∪┄∪M k 。

(13%)五、 给出平面图G 的顶点数p(G)、边数q(G)、面数 )(G ϕ和连通分支数ω(G)的一个关系式，并给予证明。

(15%)六、 G 是p 个顶点的简单图，对G 中每一对不相邻的顶点u 、v,均有d G (u)+d G (v)≥p-1。

（1） 证明G 有Hamilton 路；（2） G 是二连通图吗？为什么？。

(12%)七、设Ｇ是连通图，若对每个真子集V 0⊆V(G) ，只要∣V 0∣≤k-1，G- V 0仍连通.证明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)59(2分)3211(2分)u311(2分)2、不含奇圈的非平凡图(2分)3、α0(G)=β1(G) (2分)4、r(k,t)≤r(k-1,t) +r(k,t-1) (2分)5、55 (2分)6、G连通且无奇点。

(3分)二、（1）解：用100w 1=5 w 2=6 w 3=10 w 4=12 w 5=20 w 6=22 w 7=25，用Huffman 算法求得权为5，6，10，12 22，25的最优二元树T 。

(8分 在T 上求一个最优前缀码 A ＝{0000，0001，001，100，101，01，11} 传送这六个字母的最优前缀码为：11表示a ，01表示b ，001表示c ，100表示d ， 101表示e, 0001表示f ，0000表示 (7分) 0000 0001三、 证明；因为G 是非平凡连通图，故图G 有生成树T ，且至少有二个点。

（3分）则T 中度为1的顶点个数至少有2个， （2分）设u 1，u 2是T 中度为1的顶点，则对每一个u i ,T-u i 仍是树，且为G －u i 的生成树（i=1,2）,因此G －u i 是连通图，也即u 1，u 2都是图G 的个非割点。

因此连通因G 至少有2个非割点。

（5分）四、 证明；因为G 的点色数χ(G)=2，所以图G 不包含长为奇数的回路，由定理5.1.1,G是k —正则二分图。

（3分）由推论5.3.3，图G 有完美对集M 1. （4分）因G 是k —正则二分图，故G －M 1是(k-1)—正则二分图,故当k-1≥1时， 同样由推论5.3.3，图G －M 1有完美对集M 2，依次类推，可得图G 的k 个边不交的完美对集M 1,M 2, ┄, M k ，使 E(G)= M 1∪M 2∪┄∪M k （6分）五、 证明：若图G 连通，则由Euler 公式p(G)-q(G)+)(G ϕ=ω(G)+1。

（3分）设G 的连通分支为G 1，G 2，┄┄，G ω，则对G 的每一个连通分支G i , G i 是连通平面图，由Euler 公式，有p(G i )-q(G i )+ ϕ(G i )= 2。

（4分）又对G ，有p(G)=)(1∑=ωi i G p ,q(G)=)(1∑=ωi i G q , ϕ(G i )=)(1∑=ωϕi iG - (ω-1) （3分） 现对式子p(G i )-q(G i )+ϕ(G i )= 2关于i 求和，并将上面三个式子代入，可得p(G)-q(G)+ϕ(G)= ω+1 （3分）六、证明：构造图H ：在G 中增加一个不在G 中的顶点w ，使w 与G 中的每一个顶点相邻。

（2分）现在H 的顶点数为p(G)+1,而且G 中两个顶点不相邻当且仅当这两个顶点在H 中不相邻，对H 中每一个不同于w 的顶点u ，均有d H (u) ＝d G (u)+1。

故对H 中任二个不相邻的顶点u,v,有d H (u) +d H (v)＝d G (u) +d G (v)+2>p 。

即d H (u) +d H (v) ≥p(H) （4分）由定理 4.3.2，图H 有Hamiltom 回路C ，则C-w 就是G 的Hamiltom 路。

(3分）图G 不一定是二连通图，如二个完全图有一个公共顶点所产生的图就是一个反例 。

(3分）七、 设V 1是G 的一个最小顶点割集，则G-V 1是非连通图且∣V 1∣＝)(G κ（3分）由己知条件可知，∣V 1∣≥k ，所以)(G κ≥k 。

但δ(G) ≥)(G κ≥k 。

（4分）再由定理1.3.12q(G)=∑uu d )( ≥p(G)δ(G) ≥p(G)k故有 q(G) ≥kp(G)/2 （3分）模拟试题1(单击答案二字即可打开答案，再单击答案二字即折叠答案)一、填空题（20分，每空2分）1、给定图(1)、给出图的一个最长回路 ；(2)、给出图的一个生成树 ；(3)、给出图的点连通度 ；(4)、给出图的最大对集 ；(5)、作出图 的闭包 ；2、任一个圈中奇点的个数必为 ；3、若有44个点的连通图，且对每条边 ， 非连通，则的边数为 ；4、设有个连通分支且无回路，则；5、非平凡连通图是Euler图的充分必要条件是；6、简单图至少有3个点,,为的非空真子集,则的连通分支数至多是.o 1. (1)o(2)o(3) 3o(4)o(5)o4. 5. 无奇点 6.o 2. 偶数 3. 43二、(本题满分12分)试给出一个算法,求连通赋权图中权最大的生成树.o算法：1)在中选取边，使尽可能的大；2)若已经选定边，则在中选取边，使满足以下两条：I.不含回路；II.在满足Ⅰ的前提下，使尽可能的大。

3)当2)不能继续执行时，停止。

三、（本题满分10分）设是阶连通图,若对每个,只要,仍连通,证明:.证：由条件知,是连通图，则四、（本题满分12分）证明：简单图是树当且仅当中存在一个顶点到中其余每个顶点有且只有一条路。

o证：必要性：由定理3.1.1立即可得。

充分性：首先可见连通。

否则，设有两个连通分支、，且，则到中的顶点没有路，与题设矛盾。

其次，中无回路。

否则，若有回路。

由于连通，到上的点有路，且设与的第一个交点为，则到上除外其余点都至少有两条路，又与题设矛盾。

故是树。

五、(本题满分13分) 设是简单图若，则中有一个长度至少是的回路。

∙答案o证：在的所有路中，取一条最长的路 ,记，则和的所有邻点全在中，由于，所以至少有个邻点，设有，则就是的一个长为的回路，显然。

六、(本题满分18分) 设是连通图中某一回路，若删去中任意一条边就得到的一条最长路。

证明：(1)是的H—回路；(2)讨论此时中是否有完美对集。

∙答案o证：(1)设的长度为。

反证法，假设不是连通图的H—回路，即连通，存在路，设与最后一个交点为。

在中去掉与关联的一条边，再加上路，就可以得到一条长度至少是的路，与删去中任意一条边就得到的一条最长路矛盾。

故，则含个点，是H—回路(2)当为奇数时，无完美对集。

当为偶数时，则令，则是的一个完美对集，也是的一个完美对集，故此时有完美对集。

七、(本题满分15分)设是无奇圈的-正则图简单图()，证明：中有个边不交的完美对集，使。

答案o证：对用归纳法。

当 =1时，图本身可以看成是一个对集，故此时命题成立。

假设当时命题也成立，则当时，是正则二分图，由推论5.3.3，有完美对集是正则二分图，由归纳假设，存在个边不交的完美对集，使：。

从而有存在个边不交的完美对集，使：，即命题成立。

模拟试题2(单击答案二字即可打开答案，再单击答案二字即折叠答案)一、填空题（20分，每空2分）1、是阶简单图，则，等号成立当且仅当是图。

2、的图是图或图。

3、边数最少的连通图是。

4、是简单图且，则。

5、是有40个点的简单图且中任两个点之间有且只有1条路，则6、二分图中若与满足，则必有完美对集。

7、若二分图有Hamilton回路，则与满足。

8、的一个对集是最大对集的充要条件是。

o1、，完全图 2、平凡图，不连通图 3、树， 4、 5、396、7、8、中无可扩路二、(本题满分12分)对下图，求一个最优生成树。

∙答案oo三、(本题满分13分)证明任意六个人中有三个人互相认识，或有三个人互不认识。

.∙答案o证：构图如下：图的顶点代表这6个人，两个顶点相邻当且仅当对应的两个人互相认识。

则对于图中任意一个点或。

不妨设及它的3个邻点为。

若中有任意两个点，不妨设为，相邻，则对应的3个人互相认识；否则，中任意两个点不邻，即它们对应的3个人互不认识。

四、(本题满分10分)连通图的一条边是割边当且仅当不含在的任何回路上。

∙答案o证：必要性：假设在的某一回路上，，中存在路，1、若，则是中的路；2、若，则是中的途径，从而中存在路。

故连通。

，与是割边矛盾。

故不在回路中。

充分性：假设不是割边，则仍连通，存在路，则就是含的一个回路，与不在回路中矛盾。

故是割边。

五、(本题满分12分)设是至少有3个顶点的连通图，证明中存在两个顶点，使得仍是连通图。

∙答案o证：是至少有3个顶点的连通图，有生成树，设是的悬挂点，则连通，是的生成子图，从而连通。