07年研究生试卷(A4模板)电子科技大学研究生试卷图论及其应用

…………………… 效 …

… … … … 无 … … … … … 题…

… … 院 学… … 答 … … … … … 内 … … …名… …姓以 … … … … … 4 线 … … … … … 封 … … 号… …学…密 …………………… 电子科技大学研究生试卷

（考试时刻： 至 ，共_____小时）

课程名称 图论及其应用 教师 学时 50 学分 教学方式 教学 考核日期_2007__年___月____日 成绩

考核方式： （学生填写）

一．填空题(每题

2分，共12分)

1．简单图G=(n,m)中所有不同的生成子图(包括G和空图)的个数是_____个；

2．设无向图G=(n,m)中各极点度数均为3，且2n=m+3,那么n=_____;

m=_____；

3．一棵树有ni个度数为i的结点，i=2,3,…,k,那么它有____个度数为1的结点；

．下边赋权图中，最小生成树的权值之和为_______;

v1167v224v635810v39v546v4五、某年级学生共选修9门课。期末考试时，必需提早将这9门课先考完，天天每人只在下午考一门课，那么至少需要______天才能考完这9门课。

二．单项选择(每题2分，共10分)

1．下面给出的序列中，不是某简单图的度序列的是( ) (A) (11123); (B) (22222); (C) (3333); (D) (1333). 2． 以下图中，是欧拉图的是（ ）

ABC

3． 以下图中，不是哈密尔顿图的是（ ） A B C 4． 以下图中，是可平面图的图的是（ ） A B C 5．以下图中，不是偶图的是（ ）

DD D

A B C D

三、 (8分)画出具有7个极点的所有非同构的树

四， 用图论的方式证明：任何一个人群中至少有两个人熟悉的朋友数相同(10分)

五．(10分) 设G为n 阶简单无向图，n>2且n为奇数，G与G的补图G中度数为奇数的极点个数是不是相等？证明你的结论