…………………… 效 …
… … … … 无 … … … … … 题…
… … 院 学… … 答 … … … … … 内 … … …名… …姓以 … … … … … 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中度数为奇数的极点个数是不是相等？证明你的结论
07年研究生试卷(A4模板)电子科技大学研究生试卷图论及其应用
