———————————— __ ——____——____——____——____——____线线____——____——____——____——__：_——_名：——姓名———— _姓_ ——____——____——____——____——____——____——____——____封封____——____——__：_——_号：——学号———— 学 _ ——_ __——____——____——___：——__级——：班——级 ——班__密密_ __——____——____——____——_：：——业业——专专————————————————

**学院2013—2014学年第二学期期末考试 数学与应用数学专业2013级《图论》试卷B

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

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

1.每一对不同的顶点都邻接的简单图称为完全图，n阶完全图记为 。2.树T无圈，但增加任一新边，得到且仅得到一个 。 3.图G中的一个圈，若它通过G中每个顶点恰好一次，则该圈称为 。4.图G(p,q)的基本圈有 个。

5.图的所有顶点的关联集线性 （填相关与无关）。 6.6阶完全图的连通度是 。

7.图的边着色要求 的边着不同的颜色。

8.M为 的充要条件是：图G中不存在M-可增广道路。 9.若M是图G=(V,E)的边子集，且M中的任意两条边在G中不相邻，则称M为G中的一个 。

10. G的所有面的次数之和等于边数的 倍。 二、判断题（每小题2分，共20分） 1.同构的两个图顶点数相同。

2.G1?G2中的边数一定比G1中的边多。

3.最小生成树即G的所有生成树中权最小的生成树。 4.连通图的秩与其关联矩阵的秩不相等。

5.在图的邻接矩阵中每一行中的1的个数表示相应顶点的度数。 6.图的连通度、边连通度、顶点的最小度数三者可能相等。

7.无向图G为欧拉图当且仅当G连通，并且所有顶点的度都是偶数。8.一个非平凡连通图的连通度就是使这个图成为非连通图所需要去掉

的最小边数。

9.设G为长度大于或等于3的奇圈，则???G?=3。

10. 一个图是平面图当且仅当它没有收缩到K3,3 和K5的子图。

第 1 页 共 7 页

三、解答题（每小题5分，共30分） 1.设G1，G2如图所示，求它们的环和。

1

●● 2 1

●● 2 ● 5

3

●● 4 3

●● 4

G1 G2

图G的一个生成树T并写出图G关于T的基本圈组． A

B

C

D

3.求下图的邻接矩阵． x1

x2 x3

y1

y2

y3

4.写出下面两个图的点连通度、边连通度。

第 2 页 共 7 页

2.写出下

5．下面的图中加粗的边构成最大匹配吗？如果不是请说明理由．

f1

f2

f3

f4

f5

m1 m2 m3 m4 m5

6.试写出该图的色数，并回答与该图有关的一个定理．

x1 x3 x2

y1

y2

y3

四、应用题（每小题5分，共10分）

1.甲乙两个邮递员去送信，两人以同样的速度走遍所有的街道，甲从A点出发，乙从B点出发，最后都回到邮局（C点）。如果要选择最短的线路，谁先回到邮局？

2.一个工厂有3个车间和3个仓库。为了工作需要，车间与仓库之间将设专用的车道。为避免发生车祸，应尽量减少车道的交叉点，最好是没有交叉点，这是否可能？

五、证明题（每小题10分，共20分）

1. 证明：无向图G有生成树的充分必要条件是G为连通图。

2. 证明：设G是有n个顶点(n?3)，e条边的简单平面图，则e?3n?6。

第 3 页 共 7 页