自测题一
（一）填空题。（14分）
1.设G 是一个具有m 个顶点的无向完全图，则G 有边数_____条，顶点度数之和_____度，每一个顶点的度数_____度。
2.设图G 的邻接矩阵为
，
则G 的顶点数为_____，边数为_____。
3.任何一个无向图G 可一笔画出的充要条件是_____。
*4.设G 是完全二叉树，G 有15个顶点，其中8个叶点，则G 有_____条边，G 的总度数是_____，G 的分支点数是_____，G 中度数为3的顶点数是_____。
5.若G 是汉密尔顿图，且G 有n 个顶点，则G 的汉密尔顿路有_____条边，G 的汉密尔顿回路有_____条边。
6.G 为任意图，则G 中奇数度顶点个数为_____。
（二）判断题。判断下列说法是否正确，如不正确加以改正，如果正确说明理由。（36分）
1.由m 个顶点组成的完全图Km，删去
条边后即可得到树。
2.K3×3 是欧拉图。
3.设G 是有6个顶点，12条边的连通简单平面图，则它的面数为8。
4.已知图G 的关联矩阵
则G 的边数为5，顶点数为8。
（三）计算题。（50分）
*1.求如图所示权图中从u 到v 的最短路径。
2.求上图所示的最小支撑树。
3.国内六个城市间的铁路距离表如下（单位：100km），求连接这六个城市的最短距离的铁路网。
注：该试卷中标有*号的试题仅供选学该内容的学员参考。
自测题二
（一）填空题。（14分）
1.设G 是一棵树，顶点度数的和为12，则这棵树的边数为_____。
2.设图G 的关联矩阵为
则G 的顶点数为_____，边数为_____，顶点最小度δ（G）=_____，最大度Δ（G）=_____。
3.判断一个图是否是平面图的充要条件是_____。
4.设G 是一棵树，有n 个顶点，则G 的边数为_____。
5.设G 中无回路，且G 可一笔画出，则G 中奇数度顶点的个数是_____。
6.设G 是平面图，G 的顶点数为υ，面数为φ，则边ε=_____。
（二）多项选择题。（36分）
1.设G 是具有n 个顶点的完全图，则下列说法正确的是_____。
A.G 的边数为
B.G 的顶点度数之和为
C.每一个顶点的度数为n（n-1）
D.删去
条边得到树
2.对于K5，K3.3，下列说法正确的是_____。
A.K5，K3.3 不是平面图 B.K5 不是欧拉图
C.K5 是汉密尔顿图D.K5 去掉一边是平面图
3.设G 是连通简单平面图，每个面至少由k 条边围成，边数为ε，顶点数为υ，则下面说法正确的是_____。
A.ε≤3υ-6 B.φ=υ-ε-2
C.面数
D.υ-ε=2-φ
4.已知图G 的邻接矩阵为
则下列结果正确的有_____。
A.ε=6 B.υ=5 C.度数之和为12 D.δ=1
（三）计算题。（30分）(www.xing528.com)
1.求如图所示权图的最小支撑树。
2.求如图所示权图中从u 到v 的最短路径。
（四）证明题。（20分）
1.试证明如图所示之图不是汉密尔顿图。
2.若G 是简单平面图，则顶点最小度＜6。
【自测题一答案】
（一）填空题
1.m(m-1)/2,m(m-1),m-1
2.4,3
3.恰有0个或2个奇数度顶点
4.14,28,7,6
5.n-1,n
6.偶数
（二）判断题
1.正确。因为m 个顶点的完全图Km，共有
条边，而m 个顶点的树m-1有条边，故
为需删除的边数。
2.K3.3 不是欧拉图，因为欧拉图没有奇数度顶点，而K3.3 的每一个顶点的度都是3。
3.正确。由欧拉公式：υ-ε+φ=2，得6-12+φ=2，因此φ=8（υ 为顶点数，ε 为边数）。
4.不正确。关联矩阵指出顶点数为5，边数为8。
（三）计算题
*1.从u 到v 的最短路为：
u→v1→v5→v9→v或u→v1→v5→v6→v
2.最小支撑树如图所示。
3.最短距离铁路网如图所示。
【自测题二答案】
（一）填空题
1.6
2.5,6,0,4
3.它不包含与K5 和K3.3 的同胚的子图
4.n-1
5.2
6.υ+φ-2
（二）多项选择题
1.A、D2.A、C、D
3.D4.A、B、C、D
（三）计算题
1.
2.
（四）证明题
1.证明：假设存在汉密尔顿回路，则仅用以L 为端点的两边，其余3边不要，对点H 和J也有类似的情况，则共有9条边不在汉密尔顿回路中。
点F 的度是3，则以F 为端点的一条边不在回路中，对点B，O，D 也有类似的情况，则共有4条边不在汉密尔顿回路中。
综上所述，图中共有13条边不在汉密尔顿回路中。而图中有27条边，因此，汉密尔顿回路中最多包含27-13=14条边，但是，图中有16个顶点，汉密尔顿回路应该有16条边，矛盾，所以图中无汉密尔顿回路。
2.证明：设图G 共有n 个顶点，当1≤n≤6时，由于G 是简单图，故δ（G）≤Δ（G）≤n-1≤5＜6。
设n＞6，且G 中所有顶点度数都大于等于6，则
即m≥3n，而由推论4.5.1，m≤3n-6，矛盾，所以G 中顶点的最小度＜6。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
