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

更新时间:2024-05-21 01:45:01 阅读量: 综合文库 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

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

Top