图论试卷A卷-14数本

千里之行，始于足下让知识带有温度。第第2页/共2页精品文档推荐图论试卷A卷-14数本**学院2022—2022学年其次学期期末考试2022级本科数学与应用数学专业《图论》试卷A

（本试卷满分100分，考试时光110分钟）

一、填空题（每小题2分，共20分）

1.图G的两个子图G1，G2的环和表示为_______．

2.图G中的一圈，若它通过G中的每一条边(或弧)恰好一次，则称该圈为____．

3.图G的两个不同的生成的树T1，T2的顶点个数_______．（填相同或不相同）4．“3,3

K是欧拉图也是哈密顿图”这句话是_______。(填对或错)

5.图G的随意顶点的关联集都等于其余各顶点关联集的____．

6.(p,q)图G的基本圈有_________个．

7.连通图G的边连通度定义为．

8.设M是G的一个匹配，假如G的每一个顶点都是M-饱和点，则M为______．

9.使图G为n-着色的最小数值即为G的_________．

10.极大可平面图的每一个面的次数都是_________．

二、推断题（每小题1分，共10分）

1.同构的图保持邻接关系．

2.最小生成树即G的全部生成树中权值最小的生成树．

K是欧拉图．

3.

5

4.设G是无向连通图，则G是一笔画G中没有奇数度顶点．

5.图的秩等于图的彻低关联矩阵的秩，而不等于其关联矩阵的秩．

6.图的关联矩阵是对称矩阵．

7.图的边连通度大于最小顶点的度数．

8.一个非彻低连通图的连通度就是使这个图成为非连通图所需要去掉的最小顶点数．

9.完善匹配必然是最大匹配，但反之不然．

K的子图．

10．一个图是平面图当且仅当它没有收缩到K5或

3,3

三、单项挑选题（每小题2分，共20分）

1.一个图的全部顶点的度数之和不行能是()

A.5

B.6

C.8

D.10

2.假如连通图G的顶点个数为8，则其生成树中边的个数为()

A.7

B.6

C.9

D.8

3.在如下各图中（）欧拉图。

4．如下右图所示，以下说法正确的是()．

A．{a,e}是点割集

B．e是割点

C．{b,e}是点割集

D．{d}是点割集

5.假如连通图G的顶点个数为7，边数为8，则其向量空间的维数为()

A.9

B.8

C.7

D.1

6．设无向图G的邻接矩阵为

????????????????010*******

000011100100110，则G的边数为()．

A．3

B．4

C．5

D．6

7.假如连通图G的点连通度为2，边连通度为3，图的最小顶点的度数可能为（）

A.0

B.1

C.3D．2

8.G的一个匹配M中的顶点（）M饱和顶点

A.都不是

B.惟独一个是

C.有些是，有些不是

D.所有是

9.假如连通图G的最大顶点的度数3，则图G的色数不行能是（）

A.2

B.3

C.4

D.5

10.假如一个图含同胚于（）的子图，它可能是可平面图

A.5K

B.3,3K

C.5阶彻低图

D.3K

四、解答题（每小题10分，共40分）

1.下图中各图是否可以一笔画出？请写明理由。（10分）

2.求下图的彻低关联矩阵并以v1为参考点写出关联矩阵和一个可逆大子阵（10分）

3．请回答一下问题：（1）试说明下图是否为正则图？请画出该图的一颗生成树；（2）简述四色定理，画出下图的一种顶点着色计划。4

e2e5e3

v2v3

4e1v1

4.5项工作预备分给5个人去做，如图，其中边（fi,mj)表示fi可以从事mj，假如每个人最多从事其中一项，且每项工作只能由一人担任．问怎样才干使尽可能多的人安派上任务？（10分）

五、证实题（10分）

证实：(平面图欧拉公式)设G为p阶q条边f个面的连通平面图，则pq+f=2.

f1f2m1f3f4f5

m2m3m4m5

**学院2022—2022学年其次学期期末考试

2022级本科数学与应用数学专业《图论》

参考答案与评分标准A

命题老师：***

二、填空题

参考答案：

1，12GG⊕；2，链；3,相同；4，错；5,环合；6,1qp-+；7，使得连通图G变为不连通的边割集的最小边数；8，完善匹配；9，色数；10,3

评分标准：

本部分每小题2分。凡与答案全都的得2分，不全都（含空白）的不得分。

三、推断题

参考答案：

1-5√√√××6-10.××√√√

评分标准：

本部分每小题1分。凡与答案全都的得1分，不全都（含未作推断）的不得分。

三、单项挑选题

参考答案：1-5AABBB6-10CCDDD

评分标准：

本部分每小题2分。凡与答案全都的得2分，不全都（含未选）的不得分。

四、解答题

参考答案：

1.解：一个图是“一笔画”当且仅当奇数度顶点的个数是0或2个，因此（2）

（3）（4）是“一笔

画”。………（10分）

2.解：

………………

………（10分）本题答案不唯一，答对即可。

3.解：（1）不是为正则图，由于各个顶点的度数不彻低相同。该图的生成树不唯一，只要是该图的子图当中含七条边的树即可。……（10分）

（2）四色定理即在一张地图中，给地图的各地域着色，要使邻接的地域具有不同的色彩，四种色彩足够，该图的色数为3，顶点着色计划不唯一，符合题意即可。……………（10分）

4.解：这个问题即为：二部图12,,GVVE=是否存在1V―完善匹配。如图所示，实线表示的即为一种分配计划…（10分）

评分标准：

f1f2m1f3f4f5

m2m3m4m

5??????????????????????1100001101001101100110011彻低关联矩阵关联矩阵(v为参考点)1001111000→01101一个可逆的大子1阵0010123eee

本部分每小题10分，考生每解出一个步骤，得相应的分数。因为某一步单纯计算错误而导致其后数据错误，但办法正确的，可以在不超过该部分应得分一半的范围内给分。

五、证实题

参考答案：

证实：（1）若G中无圈,则G为无圈连通图，是一颗树，必有一个度数为1的顶点v,删除v及与它关联的边,记作G'.G'连通无圈,有p-1个顶点,条边和f个面.由归纳假设,

(p-1)-（q-1）+f=2,

即p-q+f=2,得证q=k+1时结论成立.………………（5分）

(2)若G中有圈,则删去一个圈上的一条边,记作G'.G'连通,有p个顶点,q-1条边和f-1个面.由归纳假设,

p-