2012年研究生试卷-图论评分细则2

…… ……………… 效 …

… … … … 无 … … … … …

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

（考试时间： 至 ，共__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?6. 设简单图G的邻接矩阵为A，且A2??1??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)方体； (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。

因m?mn(n?1)12?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 42 v 4v6 4 3 5 v6 1 6 v4 3 5 1 6 vv3 6 vv 4 5 v5 v3 6 vv 4 5 v5 w?T??16

3

五、(10分) (1). 求下图G的k色多项式； (2). 求出G的点色数 ?；

(3). 给出一种使用?种颜色的着色方法。

G

解：(1)、图G的补图为：(2分)

H1 H2

h(H1,x)?x………………………………………………..1分

对于H2：r1?0,r2?2,r3?4,r4?1，所以，其伴随多项式为： h(H2,x)?2x2?4x3?x4……………………………………..1分 所以：h(G,x)?2x3?4x4?x5………………………………1分 于是色多项式PG(x)?2?k?3?4?k?4??k?5

?2k(k?1)(k?2)?4k(k?1)(k?2)(k?3)?k(k?1)(k?2)(k?3)(k?4)= k (k-1) (k-2)[2+4(k-3) +(k-3) (k-4)] = k(k-1)2 (k-2)2

2分

解法2 Pk(G)?(k?1 ) 2分 ???? = (k-1) ?? + ? 3分 ???????

4

= (k-1)[ k(k-1) (k-2)2]

= k(k-1)2 (k-2)2 2分

(2)、由于P1(G)?P2(G)?0,P3(G)?12，所以，点色数?=3；……..2分 (3)、?点着色：(1分)

1 2

3

1 1 G

六、(10分) 5个人A,B,C,D,E被邀请参加桥牌比赛。桥牌比赛规则是每一场比赛由两个2人组进行对决。要求每个2人组?X,Y?都要与其它2人组?W,Z?（W,Z ?{X,Y}）进行对决。若每个人都要与其他任意一个人组成一个2人组，且每个组在同一天不能有多余一次的比赛，则最少安排多少天比赛（每一天可以有多场比赛）？请给出相应的一个时间安排表。(用图论方法求解)

解：(1)、建模：5个人能够组成10个2人组：AB, AC, AD, AE, BD, BC, BE, CD , CE, DE。

以每个2人组作为顶点，因要求每个2人组?X,Y?都与其它2人组?W,Z?比赛，所以，得到比赛状态图如下：

AB CE BE CD DE AC AD BD BC AE

4分 (2)、最少安排多少天比赛转化为求状态图的边色数??。

因为彼得森图不可1因子分解，于是可推出???4，又可用4种色对其正常边着色(见

5

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库2012年研究生试卷-图论评分细则2在线全文阅读。