1.给了一个带权有向图，求最大流并找一个最小截；把有向边改成无向边，再求一棵最小生

成树。

2.(1)已知一个图有 1 个 8 次顶、6 个 6 次顶、8 个 4 次顶，证明它不是平面图。

(2)举出一个 5 个顶的图，使得它添加任意一条边都是 Euler 图。（这题有问题）

(3)证明 n≥5 时，圈 Cn 的补图是 Hamilton 图。

3.课本例 1.11

4.(1)设树的 2,3,...,k 次顶的个数为 n2,n3,...,nk，求一次顶的个数。

(2)n 个顶的树的最大度数Δ最小是多少？最大是多少？并求出最小和最大时对应什么树。

(3)证明树的最长轨的端点为叶。

5.已知有 8 种药品要用容器运输，给出它们的互斥关系（互斥的药品不能放在同一个容器

内），问最少用几个容器？建立图论模型并使用图论知识解决问题。

6.(1)二分图 G 满足|X|=|Y|=n，且最小度数δ≥n/2，证明 G 有完备匹配。

(2)证明 G 中任意一条边都包含于 G 的一个完备匹配，当且仅当对 X 的任一非空真子集 S，

|N(S)|>=|S|+1。

2018年秋季学期图论期末试题1