电子科大研究生图论05-14年图论期末试题

2005年研究生期末试题(120分钟)

《图论及其应用》

一、填空(15分，每空1分)

1、 已知图G有10条边，4个度数为3的顶点，其余顶点的度数均小于2，则

G中至少有___8___个顶点 .

2、 m条边的简单图G中所有不同的生成子图(包括G和空图)的个数为

__2m____.

3、 4个顶点的非同构的简单图有__11___个. 4、 图G1的最小生成树各边权值之和为__28___.

4 7 6 4 1 6 5 3 9

2 1

5 10 图G1

5、若W是图G中一条包含所有边的闭通道，则W在这样的闭通道中具有最短长度的充要条件是：

(1) 每一条边最多重复经过_1__次；

(2) 在G的每一个圈上，重复经过的边的数目不超过圈的长度的_一半___.

56、5阶度极大非哈密尔顿图族有__C2,__C15___.

7、在图G2 中，图的度序列为(44443322)，频序列为(422)，独立数为3， 团数为4，点色数为4，边色数为4，直径为3.

图G2

二、选择(15分)

(1)下列序列中，能成为某简单图的度序列的是( C )

(A) (54221) (B) (6654332) (C) (332222)

（2）已知图G有13条边，2个5度顶点，4个3度顶点，其余顶点的的度数为2，则图G有( A )个2度点。

(A) 2 ( B) 4 (C ) 8 (3) 图G如(a)所示，与G同构的图是( C )

(a) (A) (B) (C)

(4) 下列图中为欧拉图的是( B ),为H图的是( AB ),为偶图的是( BC ).

(A) (B) (C) 5．下列图中可1-因子分解的是( B )

(A) (C) (B) 三、设?和?分别是(n,m)图G的最大度与最小度，求证：??证明：n??2m?2m??(10分). nv?V(G)?d(v)?n????2m??. nn四、正整数序列(d1,d2,?,dn)是一棵树的度序列的充分必要条件是?di?2(n?1)

i?1(10分).

证明：\?\ 结论显然

\?\

设正整数序列(d1,d2,?,dn)满足?di?2(n?1)，易知它是度序列。

i?1n设G是这个度序列的图族中连通分支最少的一个图，知m=E(G)?n?1. 假设G不连通，则?(G)?2，且至少有一个分支G1含有圈C，否则，G是森林，

有m=E(G)?n???n?1矛盾！从C中任意取出一条边e1?u1v1。并在另一分支

G2中任意取出一条边e2?u2v2，作图

G??G??u1v1,u2v2???u1v2,u2v1?

则G?的度序列仍然为(d1,d2,?,dn)且?(G?)??(G)?1，这与G的选取矛盾！所以

G是连通的，G是树。即(d1,d2,?,dn)一棵树的度序列。

五、求证：在简单连通平面图G中，至少存在一个度数小于或等于5的顶点 (10分).

证明：若不然，2m?v?V(G)?d(v)?6n?6n?12?m?3n?6,这与G是简单连通平

面图矛盾。

六、证明：(1) 若G恰有两个奇度点u与v，则u与v必连通；

(2) 一棵树至多只有一个完美匹配 (10分).

证明；(1) 因为任意一个图的奇度点个数必然为偶数个，若G恰有两个奇度点u与v，且它们不连通，那么就会得出一个连通图只有一个奇度点的矛盾结论。所以若G恰有两个奇度点u与v，则u与v必连通。

(2) 若树T有两个相异的完美匹配M1,M2，则M1?M2??且T[M1?M2]中

的每个顶点的度数为2，则T中包含圈，这与T是数矛盾！

七、求图G的色多项式Pk(G)(15分).

H1 H2 图G

G 解：图G的补图如图G，则

h(H1,x)?r1x?r2x2?r3x3?r4x4，其中，r1?N1(H1)?0，r2?N2(H1)?2 r3?N3(H1)?4，r4?N4(H1)?1；

h(H2,x)?r1x?r2x2，其中，r1?N1(H2)?1，r2?N2(H2)?1

2234Pk(G)?(x?x)(2x?4x?x)??k?6?5?k?5?6[k]4?2[k]3。

八、求图G中a到b的最短路(15分).

v1 1 v4

2 4 9 6 3 a 8 v2 2 v5 6 b

7 2 4

1 2 9 v3 v6

图G

解 1. A1= {a}，t(a) = 0，T1 = Φ 2.b1?v3

3. m1 = 1, a2 = v3 , t(v3) = t(a) + l(av3) = 1 (最小)，

T2 ={av3} 2. A2 ={a, v3}, b1(2)(2)?v1,b2?v2

?1?3. m2 = 1, a3 = v1 , t(v1) = t(a) + l(av1) = 2 (最小)，

T3 ={av3, av1} 2. A3 ={a, v3, v1}, b1(3)(3)(3)?v2,b2?v2,b3?v4

3. m3 = 3, a4 = v4 , t(v4) = t(v1) + l(v1v4) = 3 (最小)，

T4 ={av3, av1, v1v4}

2. A4 = {a, v3, v1, v4}，b1(4) = v2，b2(4) = v2，b3(4) = v2, b4(4) = v5 3. m4 = 4, a5 = v5 , t(v5) = t(v4) + l(v4v5) = 6 (最小)，

T5 ={av3, av1, v1v4, v4v5}

2. A5 = {a, v3, v1, v4, v5}，b1(5) = v2，b2(5) = v2，b3(5) = v2 , b4(5) = v2, b5(5) = v2 3. m5 = 4, t(v2) = t(v4) + l(v4v2) = 7 (最小)，

T6 ={av3, av1, v1v4, v4v5, v4v2}

2. A6 = {a, v3, v1, v4, v5, v2}, b2(6) = v6, b4(6) = b，b5(6) = v6，b6(6) = v6 3. m6 = 6, a7 = v6 , t(v6) = t(v2) + l(v2v6) = 9 (最小)，

T7 ={av3, av1, v1v4, v4v5, v4v2, v2v6}

2. A7 = {a, v3, v1, v4, v5, v2, v6}, b4(7) = b，b5(7) =b，b7(7) =b 3. m7 = 7, a8 = b , t(b) = t(v6) + l(v6b) = 11 (最小)，

T8 ={av3, av1, v1v4, v4v5, v4v2, v2v6, v6b}

于是知a与b的距离

d(a, b) = t(b) = 11

由T8导出的树中a到b路av1v4v2v6b就是最短路。

2006研究生图论期末试题(120分钟)

一、填空题(15分，每空1分)

1、若两个图的顶点与顶点之间，边与边之间都存在_________对应，而且它们的关联关系也保持其_________关系，则这两个图同构。

2、完全图K4的生成树的数目为_________；阶为6的不同构的树有_________棵。 3、设无向图G有12条边，已知G中度为3的结点有6个，其余结点的度数均小于3，则

G中至少有_________个结点。

4、具有5个结点的自补图的个数有_________。

?0??15、已知图G的邻接矩阵A(G)??0??1?0?1010??1101?1011?，顶点集合V(G)??v1,v2,v3,v4,v5?，

?0101?1111??则由v2到v5的途径长度为2的条数为_________。

6、若Kn为欧拉图，则n=_________；若Kn仅存在欧拉迹而不存在欧拉回路，则n=_________。

7、无向完全图Kn(n为奇数)，共有_________条没有公共边的哈密尔顿圈。

8、设G是具有二分类(X,Y)的偶图，则G包含饱和X的每个顶点的匹配当且仅当

_________，对所有S?X。

9、在有6个点。12条边的简单连通平面图中，每个面均由_________条边组成。

10、彼德森图的点色数为_________；边色数为_________；点独立数为_________。 二、单选或多选题(15分，每题3分)

1、设V??1,2,3,4,5?，E??(1,2),(2,3),(3,4),(4,5),(5,1)?,则图G??V,E?的补图是( ). 2 3

1 1 1 5 1 5 5 2 2 4 A 3 B 4 C 4 D 3

2、在下列图中，既是欧拉图又是哈密尔顿图的是( ).

C A B

3、下列图中的( )图，V2到V4是可达的。 V1 V2

V4 V1 V4 V1 D V4 V1 V4 V3 A V2 B V3 V2 C V3 V2 D V3 4、下列图中，可1—因子分解的是( ).

(A) (C) (B) (D)

5、下列优化问题中，存在好算法的是( )

(A) 最短路问题；(B) 最小生成树问题；(C) TSP问题；(D) 最优匹配问题. 三、作图题(10分)

1、分别作出满足下列条件的图

(1)、E图但非H图；(2) H图但非E图；(3) 既非H图又非E图；(4) 既是H图又是E图 2、画出度序列为(3,2,2,1,1,1)的两个非同构的简单图。

四、求下图的最小生成树，并给出它的权值之和(10分)。

v1 1 v4 2 4 9 6 3 a 8 v2 2 v5 6 b

7 2 4 2 9 v3 v6

图G

2 五、给出一个同构函数证明G1?G2(10分)

a 1 2 i 5 f g 3 b 8 e 6 4 h d c 9 7 G1 G2

六、若图G为自补图，那么，它的阶n一定能够表示为4k或者4k?1的形式，其中k为非负整数。而且，图G的边有

n(n?1)条。(5分) 4七、设T为一棵非平凡树，度为i的顶点记为ni，则n1?2?n3?2n4???(k?2)nk。(10分)

八、证明：阶数为8的简单偶图至多有16条边(5分)

九、设图G有10个4度顶点和8个5度顶点，其余顶点度数均为7。求7度顶点的最大数量，使得G保持其可平面性(10分) 十、求图G的色多项式(10分）

1

5 2 4

3

G

…………………… 效 …

… … … … 无 … … … … …

题 … … 院… 学… … 答 … … … … … 内 … … … 名… …姓以 … …… 4 … … 线 … … … … … 封 … … 号…… 学…密 ……………………

电子科技大学研究生试卷

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

课程名称 图论及其应用 教师 学时 60 学分 教学方式 讲授 考核日期_2007__年___月____日 成绩 考核方式： （学生填写）

一．填空题(每题

2分，共12分)

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

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

m=_____；

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

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

v1167v224v635810v39v546v45、某年级学生共选修9门课。期末考试时，必须提前将这9门课先考完，每天每人只在下午考一门课，则至少需要______天才能考完这9门课。 23二．单项选择(每题2分，共10分)

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

ABC

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

A B C

DD D D

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

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

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

六．(10分)设G是具有n个顶点的无向简单图，其边数

1(n?1)(n?2)?2，证明(1) 证明G中任何两个不相邻顶点的度数之21m?(n?1)(n?2)?1和大于等于n。(2)给出一个图，使它具有n个顶点，

2m?条边，但不是哈密尔顿图。

七、(10分)今有赵、钱、孙、李、周五位教师，要承担语文、数学、物理、化学、英语五门课程。已知赵熟悉数学、物理、化学三门课程，钱熟悉语文、数学、物理、英语四门课程，孙、李、周都只熟悉数学和物理两门课程。问能否安排他们5人每人只上一门自己所熟悉的课程，使得每门课程都有人教，说明理由

八、(10分)设G是具有n个顶点，m条边，p(P?2)个连通分支的平面图，G的每个面至少由k（k?3）条边所围成，则

m?k(n?p?1)

k?2

九．(10分)求下图G的色多项式Pk(G).

图G

十、(10分) (1)、在一个只有2个奇度点的边赋权图中，如何构造一个最优欧拉环游？说明理由；

(2)、在一个边赋权的哈密尔顿图中，如何估计其最优哈密尔顿圈的权值之和的下界？

………以……………内……………答…… ………题……………无……………效……………………

电子科技大学研究生试卷

（考试时间： 至 ，共__2_小时）

课程名称 图论及其应用 教师 学时 50 学分 教学方式 讲授 考核日期_2008__年___月____日 成绩 考核方式： （学生填写）

一．填空题(每题

姓 名 学 院 2分，共20分)

1．若n阶单图G的最大度是?，则其补图的最小度?(G)=_____； 2．若图G1?(n1,m1)，G2?(n2,m2)，则它们的联图G?G1?G2的顶点

数=_____;边数=_____；

3．G是一个完全l部图，ni是第i部的的顶点数i=1，2,3,…,l。

则它的边数为____；

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

5. 若G?Kn,则G的谱spec(G)?_______; 6. 5个顶点的不同构的树的棵数为_______; 7. 5阶度极大非哈密尔顿图族是_______;

8. G为具有二分类(X,Y)的偶图，则G包含饱和X的每个顶点的匹配的充分必要条件是______

9. 3阶以上的极大平面图每个面的次数为_______;3阶以上的极大外平面图的每个内部面的次数为_______;

10. n方体的点色数为_______;边色数为_______。 二．单项选择(每题3分，共12分)

1．下面给出的序列中，不是某图的度序列的是( ) (A) (33323); (B) (12222); (C) (5533); (D) (1333). 2．设V(G)=?1,2,3,4,5?，E(G)??(1,2),(2,3),(3,4),(4,5),(5,1)?则图G?(V,E)的补图是（ ）

5 1 2 7 1 1 2 3 3 6 2 5 1 2 4 7 3 4 2 6 1 5 2 5 1 2 1 2 4 (A) 3 4 (B) 3 4 (C) 3 4 (D) 3 3.下列图中，既是欧拉图又是哈密尔顿图的是( )

(A) (B) (C) (D) 4.下列说法中不正确的是( ) (A)每个连通图至少包含一棵生成树； (B)k正则偶图(k>0)一定存在完美匹配； (C)平面图G?(G*)*,其中G*表示G的对偶图； (D)完全图K2n可一因子分解。

三、 (10分)设图G的阶为14，边数为27，G中每个顶点的度只可能为3，4或5，且G有6个度为4的顶点。问G中有多少度为3的顶点？多少度为5的顶点？

四，(10)证明：每棵非平凡树至少有两片树叶(10分)

_______; 7. 三角形图的生成树的棵数为_______; 8. G2的点连通度与边连通度分别为______；

G2

9.n=5的度极大非H图族为_______;

10. n方体(n?1)的点色数为_______;边色数为_______。 二．单项选择(每题3分，共12分) 1．下面命题正确的是( )

(A) 任意一个非负整数序列均是某图的度序列；

(B) 设非负整数序列??(d1,d2,?,dn)，则?是图序列当且仅当?di为

i?1n偶数;

(C) 若非负整数序列??(d1,d2,?,dn)是图序列，则?对应的不同构的图一定唯一;

(D) n阶图G和它的补图G有相同的频序列. 2．下列有向图中是强连通图的是( )

3.关于欧拉图与哈密尔顿图的关系，下面说法正确的是( )

(A) (B) (C) (D) (A) 欧拉图一定是哈密尔顿图； (B) 哈密尔顿图一定是欧拉图；

(C) 存在既不是欧拉图又不是哈密尔顿图的图； (D) 欧拉图与哈密尔顿图都可以进行圈分解。 4.下列说法中正确的是( ) (A) 任意一个图均存在完美匹配； (B) k(k?1)正则偶图一定存在完美匹配；

(C) 匈牙利算法不能求出偶图的最大匹配，只能用它求偶图的完美匹配；

(D) 图G的一个完美匹配实际上就是它的一个1因子。

三、 (10分)若阶为25且边数为62的图G的每个顶点的度只可能为3，4，5或6，且有两个度为4的顶点，11个度为6的顶点，求G中5度顶点的个数。

四，(8分)求下图的最小生成树（不要求中间过程，只要求画出

最

小生成树, 并给出T的权和）。

1 7 3 1 1 4 1 1 4 3 5 8 3

1 6

五．(8分)求下图的k色多项式。

G

六．(8分) 设G是一个边赋权完全图。如何求出顿圈的权值的一个下界？为什么？ G的最优哈密尔

七．(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的点独立数等于________,点覆盖数等于______。

i个分支点，13. 完全m元根树有t片树叶，则其总度数为_______。

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为哈密尔顿图的25.下列说法正确的是( )

(A) 非平凡树和n(n?2)方体都是偶图； (B) 任何一个3正则图都可1-因子分解；

(C) 可1-因子分解的3正则图中一定存在哈密尔顿圈； (D) 平面图G的对偶图的对偶图与G是同构的。

三、 (10分)设无向图G有12条边，且度数为3的结点有6个，其余结点的度数小于3，求G的最少结点个数。

四，(12分) 在下面边赋权图中求：(1)每个顶点到点a的距离(只需要把距离结果标在相应顶点处，不需要写出过程); (2) 在该图中求出一棵最小生成树，并给出最小生成树权值(不需要中间过程，用波浪线在图中标出即可).

a 7 1 1 2 3 3 6 2 5 7 4 3 6 1 2 4

五．(10分) 今有赵、钱、孙、李、周五位教师，要承担语文、数学、物理、化学、英语五门课程。已知赵熟悉数学、物理、化学三门课程，钱熟悉语文、数学、物理、英语四门课程，孙、李、周都只熟悉数学、物理两门课程。问能否安排他们都只上他们熟悉的一门课程，使得每门课程都有人教（用图论方法求解）。

六．(6分)设l是赋权完全偶图G=(V,E)的可行顶点标号，若标号对应的相等子图Gl含完美匹配M*,则M*是G的最优匹配。

七.(6分) 求证：在n阶简单平面图G中有?(G)?5，这里?(G)是G的最小度。

八、(10分)课程安排问题：某大学数学系要为这个夏季安排课程表。所要开设的课程为：图论(GT), 统计学(S),线性代数(LA), 高等微积分(AC), 几何学(G), 和近世代数( MA )。现有10名学生(学生用Ai表示，如下所示）需要选修这些课程。根据这些信息，确定开设这些课程所需要的最少时间段数，使得学生选课不会发生冲突。 (要求用图论方法求解)

A1 : LA, S ; A2 : MA, LA, G ; A3: MA, G, LA ; A4: G, LA, AC ; A5: AC, LA, S ; A6: G, AC; A7: GT, MA, LA ; A8: LA,GT, S ; A9: AC, S, LA; A10: GT, S。

九．(9分)求下图G的色多项式Pk(G).

1 5 2 4 G

…………………… 效 …

… … … … 无 … … … … …

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

（考试时间： 至 ，共__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的边数为

_n1m?2n2_m1；_ _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__；

7. 设G是n阶简单图，且不含完全子图K3，则其边数一定不会超过

?n2?__??_； ?4?8．K3的生成树的棵数为__3__;

9. 任意图G的点连通度k(G)、边连通度?(G)、最小度?(G)之间的关系为

G?)?G(?)? __k(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) 无奇圈的非平凡图； (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。

n(n?1)因m1?m2?…………………………………4分

2所以：n2?n?2m1?2m2?0……………………..2分 得：n?1?1?8(m1?m2)………………………..4分

2四、(10分) 求下图的最小生成树（不要求中间过程，只要求画出最

小生成树, 并给出T的权和）。

v1 1 2 3 V7 v1 1 2 3 V7 v2 4 3 5 1 6v3 v2 4 v v6 vv2 4 3 5 1 6v5 v3 v2 4 v v6 v6 v 4 56 v 4 5v5

w?T??16

五、(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 P ) 2分 ?1k(G)?(k

?????? ? + ? ??????

本文来源：https://www.bwwdw.com/article/7jd7.html