内容发布更新时间 : 2024/12/27 15:18:07星期一 下面是文章的全部内容请认真阅读。
…… ……………… 效 …
… … … … 无 … … … … …
题 … … 院… 学… … 答 … … … … … 内 … … … 名… …姓以 … … … … … 线 … … … … … 封 … … 号…… 学…密 …………………… 电子科技大学研究生试卷
（考试时间： 至 ，共__2_小时）
课程名称 图论及其应用 教师 学时 60 学分
教学方式 讲授 考核日期_2012__年___月____日 成绩 考核方式： （学生填写）
一、填空题（填表题每空1分，其余每题2分，共30分)
1．n阶k正则图G的边数m(G)=___nk2___； 2．3个顶点的不同构的简单图共有___4___个；
3．边数为m的简单图G的不同生成子图的个数有__2m___个；
4. 图G1?(n1,m1)与图G2?(n2,m2)的积图G1?G2的边数为_n1m2?n2m1___； 5. 在下图G1中，点a到点b的最短路长度为__13__； 6 1 4 6 1 4 a 4 2 b 5 3 7 2 G1 ??31120?2111?设简单图G的邻接矩阵为A，且A2??16. ??11302??，则图G的边数为?21020?
???01202??__6__；
1
?n2?7. 设G是n阶简单图，且不含完全子图K3，则其边数一定不会超过__??_；
?4?8．K3的生成树的棵数为__3__;
9. 任意图G的点连通度k(G)、边连通度?(G)、最小度?(G)之间的关系为 __k(G?)?G(?)?G()_；_
10. 对下列图，试填下表（是??类图的打〝√ 〞，否则打〝 ?〞）。
① ② ③
能一笔画的图 Hamilton图 偶图 可平面图 ① ? √ ? √ ② ? √ ? √ ③ ? √ √ √
二、单项选择(每题2分，共10分)
1．下面命题正确的是 ( B )
对于序列(7,5,4,3,3,2)，下列说法正确的是： (A) 是简单图的度序列；
(B) 是非简单图的度序列; (C) 不是任意图的度序列; (D) 是图的唯一度序列.
2．对于有向图，下列说法不正确的是 ( D )
(A) 有向图D中任意一顶点v只能处于D的某一个强连通分支中； (B) 有向图D中顶点v可能处于D的不同的单向分支中;
(C) 强连通图中的所有顶点必然处于强连通图的某一有向回路中; (D) 有向连通图中顶点间的单向连通关系是等价关系。
3.下列无向图可能不是偶图的是 ( D ) (A) 非平凡的树；
(B) 无奇圈的非平凡图；
2
(C) n(n?1)方体；注意：n方体是n正则二部图。 (D) 平面图。
4.下列说法中正确的是 ( C )
(A) 连通3正则图必存在完美匹配；
(B) 有割边的连通3正则图一定不存在完美匹配； (C) 存在哈密尔顿圈的3正则图必能1因子分解； (D) 所有完全图都能作2因子分解。
5. 关于平面图，下列说法错误的是( B )
(A) 简单连通平面图中至少有一个度数不超过5的顶点； (B) 极大外平面图的内部面是三角形，外部面也是三角形；
(C) 存在一种方法，总可以把平面图的任意一个内部面转化为外部面；(D) 平面图的对偶图也是平面图。
三、 (10分) 设G与其补图G的边数分别为m1,m2，求G的阶数。 解：设G的阶数为n。
因mmn(n?1)1?2?2…………………………………4分
所以：n2?n?2m1?2m2?0……………………..2分 得：n?1?1?8(m1?m2)2………………………..4分
四、(10分) 求下图的最小生成树（不要求中间过程，只要求画出最
小生成树, 并给出T的权和）。
v1 v1 1 2 3 1 2 3 v2 V7 v2 V7 2 v 4v4 3 5 v6 1 6 v2 v 4v6 4 3 5 1 6 v3 6 vv 4 5 v5 v3 6 vv 4 5 v5 w?T??16
3