七．(8分)求证：设Gl是赋权完全偶图G?Kn,n的可行顶点标号l对应的相等子图，若M是Gl的完美匹配，则它必为G的最优匹配。
八.(8分) 求证：若n为偶数，且?(G)??1，则G中存在3因子。
九、(10分)一家公司计划建造一个动物园，他们打算饲养下面这些动物：狒狒(b)、狐狸(f)、山羊(g)、土狼(h)、非洲大羚羊(k)、狮子(l)、豪猪(p)、兔子(r)、鼩鼱(s)、羚羊(w)和斑马(z)。根据经验，动物的饮食习惯为：狒狒喜欢吃山羊、非洲大羚羊(幼年)、兔子和鼩
n2鼱；狐狸喜欢吃山羊、豪猪、兔子和鼩鼱；土狼喜欢吃山羊、非洲大羚羊、羚羊和斑马；狮子喜欢吃山羊、非洲大羚羊、羚羊和斑马；豪猪喜欢吃鼩鼱和兔子；而其余的则喜欢吃虫子、蚯蚓、草或其它植物。公司将饲养这些动物，希望它们能自由活动但不能相互捕食。求这些动物的一个分组，使得需要的围栏数最少。(要求用图论方法求解)
十．(8分)求证，每个5连通简单可平面图至少有12个顶点。
…………………… 密……………封……………线……………以……………内……………答…… ………题……………无……………效…………………… 电子科技大学研究生试卷
（考试时间： 至 ，共__2_小时）
课程名称 图论及其应用 教师 学时 60 学分 教学方式 讲授 考核日期_2011__年___月____日 成绩 考核方式： （学生填写）
一．填空题(每空
学 号 姓 名 学 院 1分，共22分)
1．若n阶单图G的最小度是?，则其补图的最大度?(G)=_____。 2．若图G1?(n1,m1)，G2?(n2,m2)，则它们的积图G?G1?G2的顶点数
=_____; 边数=_____。
3．设A是图G的推广邻接矩阵，则An的i行j列元aij(n)等于由G中顶点vi到顶点vj的长度为______的途径数目。 4．完全图Kn的邻接矩阵的最大特征值为_______。 5. 不同构的3阶单图共有_______个。
6. 设n阶图G是具有k个分支的森林，则其边数m(G)?_______。 7. n阶树(n?3)的点连通度为_______；边连通度为________；点
色数为_______； 若其最大度为?，则边色数为________。 8. 图G是k连通的，则G中任意点对间至少有______条内点不交路。
9. 5阶度极大非哈密尔顿图族为______和_______。
10. 完全图K2n能够分解为_______个边不相交的一因子之并。 11. 设连通平面图G具有5个顶点，9条边，则其面数为_______；
n(n?3)阶极大平面图的面数等于__________；n(n?3)阶极大外
平面图的顶点都在外部面边界上时，其内部面共有_______个。 12. 完全偶图Km,n的点独立数等于________,点覆盖数等于______。
13. 完全m元根树有t片树叶，则其总度数为_______。 i个分支点，14．对具有m条边的单图定向，能得到______个不同的定向图。 二．单项选择(每题3分，共15分)
1．下面给出的序列中，不是某图的度序列的是( )
(A) (1,3,5,4,7); (B) (2,2,2,2,2); (C) (3,2,3,3); (D) (1,5,7,1).
2．下列无向图G?(n,m)一定是树的是（ ）
(A) 连通图；(B)无回路但添加一条边后有回路的图； (C) 每对结点间都有路的图； (D) 连通且m?n?1。 3.以下必为欧拉图的是( ) (A) 顶点度数全为偶数的连通图； (B) 奇数顶点只有2个的图； (C) 存在欧拉迹的图； (D) 没有回路的连通图。
4.设G是n(n?3)阶单图，则其最小度??( )
(A) 必要条件；(B)充分条件；(C)充分必要条件。
n是G为哈密尔顿图的2
