推论2.3

推论2.3 任何一个非平凡树G至少有两个度数为1的顶 点． 证 因为G为非平凡树，所以G的任何一个顶点v，d(v) ≥1．假如G的p个顶点中，度数为1的顶点个数小于2， 那么度数大于或等于2的顶点个数就不小于p-1．于是， 总度数：
d (v) 2( p 1) 1 2(Βιβλιοθήκη p 1) 2q2 3 4


1 6 5
s1=1, t1 =4 s2=2, t2 =3 s1=3, t1 =4 s1=4, t1 =5 (4, 3 , 4 , 5)

反过来，要从长度为n-2的序列重新构造 出Kn的一棵生成树T．我们注意到，T中 度数为1的顶点正是在该序列中没有出现 的那些顶点．设s1是N的不在(t1,t2,t3,…,tn-2) 中的第一个顶点，则连接s1与t1 。其次设 s2是N\{s1}的不在(t2 , t3 , …, tn-2)中的第一 个顶点，则连接s2与t2，…如此继续下去， 直到连接了n-2条边s1t1,s2t2,…,sn-2tn-2．最 后再增添一条连接N\{s1, s2 , …, sn-2}中剩 下的两个顶点的一条边，即可得到T． 最后可以证明Kn的不同生成树对应着不 同的序列．这样就建立了所希望的一一 对应．
生成树数目的递归算法示例
练习

利用生成树的递推公式，计算K3,3的生成树 数目。 = =
=
=3+8+8+16+7+ 10+12+12=76个
凯莱(Cayley)公式

定理2.7 (凯莱(Cayley)公式) ： τ(Kn)=nn-2 证 设Kn的顶点集合为N={1，2，…， n}．注意到由N的元素组成的长度为n-2序 列的个数是nn-2．于是为了证明本定理只须 在Kn的生成树集合和这种序列集合之间建 立一一对应就行了．我们用树的编码思想 来给出这种对应．
1 1 1
1 1
2 2 1
深探法
边的收缩运算

设e是G的一条边，将e删去，并使其两端重 合，称e被收缩，所得图记为G·。 e
G1
e
G1· e
G2
e
G 2· e
定理2.5 树经边的收缩后仍为树． 证 设T是树，e是T的一条边，因为T连通， 所以T· e也连通。在T中：q(T)=p(T)-1,经边的 收缩后，q(T· e)=q(T)-1，p(T· e)=p(T)-1 于是在T· e中， q(T· e)=p(T· e)-1 因此T· e也是树。

生成树数目的递归算法


定理2.6 若e是G的一条边，则τ(G)=τ(G-e)+τ(G· e)，其中τ(G) 表示G的生成树的数目． 证 将G的生成树分成两类



1)不包含e的生成树，它也是G-e的生成树；反之， G-e的生 成树也是G的不包含e的生成树．此类生成树有τ(G-e)个。 2)包含e的生成树，设T是这样一棵生成材；则T· e是G· e的一 棵生成树．反之，G· e的一棵生成树包含e边收缩成的点，将 此点扩张成G的一条边e，这样得到G的一棵含e的生成 树．此类生成树有τ(G· e)个． 因此 τ(G)=τ(G-e)十τ(G· e)
1)当l=0时，此途径即为通路。
2)假设重复顶点个数小于l时，结论成立。 设第k个(1≤k≤l)重复出现的顶点在途径中首次出现为vi， 末次出现为vj，即(u,v)-途径为： w1=u1e1v1…viei+1…vjej+1…env，将vi,vj合并，途径成为



w2=u1e1v1…viej+1…env

首先给N的各个顶点标号，即把N 当作一个n元集合．如果我们已经 有了Kn的一棵生成树T，设s1是T 中度数为1的最小标号顶点，与s1 邻接的那个顶点标号为t1 ．现在 从T中删去s1 ，用s2记T-s1中度数 为1的最小标号顶点，与s2邻接的 那个顶点标号为t2 …重复这个操 作，直到tn-2被确定，留下一个恰 有两个顶点的一棵树．这样由Kn 的一个生成树唯一地确定一个长 度为n-2的序列(t1, t2 , t3 , …, tn-2)


最优树的算法




Kruskal算法——加边避圈法． 不妨假定，连通图G各边的权非负，即w(e)≥o． 1)选择e1，使得w(e1)尽可能地小； 2)若已选好e1,e2,…,ei，则从E(G)-{e1,e2,…,ei}中选取ei+1满足； a)G[{e1,e2,…,ei+1}]无回； b)w(ei+1)是满足a)的尽可能小的权； 3)直到2)不能再进行为止． 去边破圈法 1)取G的任意一个圈ci 2)在ci上，去掉权最大的边； 3)重复1)一2)，直到G中无圈为止
练习

K5有多少个生成树？其中不同构的有多少？ 根据Cayley公式， K5有55-2=125个生成树。 根据顶点的最高度分析，可知其中互不同构的 生成树只有三种，即
连接问题

设给定n个城市v1,v2,v3,…,vn，城市vi与vj 直接修通一条 铁路需要费用xij，试设计一个总造价最低的铁路网把 这些城市连接起来，这就是所谓的连接问题。 连接问题反映在图论上，就是在赋权图G中，找出具 有最小权的连通子图——最小权生成树，称为最优树 (最小树)． 对有限的赋权图，由于它只有有限个生成树，通过穷 举比较，总可以找出其中权最小者，故最优树是一定 存在的，但不难想见，穷举法实现起来是很困难的




(2, 3 , 2 , 3) s1=1, t1 =2 s2=4, t2 =3 s1=5, t1 =2 s1=2, t1 =3
2 3 4
1 6 5

练习

画出K4的所有16棵生成树。
A B A B A B A B D C D C D C D C A B A B A B A B D C D C D C D C A B A B A B A B D C D C D C D C A B A B A B A B D C D C D C D C

(4) G无回，且q＝p—1
(5) G无回，若u，v是G的任意两个非邻接顶点， G+uv有且仅有一个回路；

(6) G连通，但舍弃任何一条边后便不连通．

引理2.2 若在图G中存在(u,v)-途径，则在G中存在 (u,v)-通路．
证明：对途径中重复出现的顶点个数l作归纳：



纽约
伦敦
68
59
67
59
36
2
20
55
/
34
34
/
数学竞赛中的图论方法



例1 十个学生参加一次考试，试题十道。已知没两个学生做对 的题目完全相同。证明在这十道试题中可以找到一道试题，将 这道试题取消后，每两个学生所做对的题目仍然不会完全相同。 证明：用反证法。每一个学生用一个点vi(1≤i≤10)表示，如果 命题不成立，那么对每一个题目h，如果去除h后，就可以找到 一对学生vi与vj，做对的题目相同。这就不妨设原来vi比vj多做 对一道题目h，在这样的一对点vi与vj中连一条边，并且标上数 h,于是得到一个有10个顶点10条边的图，并且这10条边上标上 了10个互不相同的数。因为边数不小于顶点数，所以此图一定 有圈。 设(vi1,vi2, …,vik, vi1)为一个圈，那么沿这个圈前进时，每通过一 条边相当于解出的题目增加或减少一道，并且增减的题目互不 相同。由vi1做对的题目增加一些题再减少一些题，最后的结果 和和vi1原来做对的题目完全相同，这显然是矛盾的。
最优树算法示例
去边破圈法 加边避圈法
6 6 6 7 3 8 1 3 4 2 2 3
6 6 6
2 2 2
3 1
练习

试用Kruskal算法和破圈法求下列赋权图的 最优树。
5 2 2 3 2 2 1 3 3 5 3 4 2 2
4 11 15 2
6 18
练习

已知世界六大城市之间的航线距离(以百英里为单位) 表，试在此表确定的赋权完全图中找出一个最小权生 成树。 北京 东京 巴黎 墨西哥 纽约 伦敦 北京 东京 巴黎 墨西哥 / 13 51 77 13 / 60 70 51 60 / 57 77 70 57 / 68 67 36 20 50 59 2 55
求生成树的方法

1．去边破圈法 在连通图G中，逐次去边，破掉所有回路，但 必须保持连通化最后得到的无回连通图就是G的 生成树．
求生成树的方法

2．加边避圈法。 在连通图G中任取一条边e1，找一条不与e1构成回路的边e2 ， 然后再找不与{e1, e2}构成回路的e3 …如此继续下去，直到 这一过程不能再进行为止，所得图就是G的生成树． 广探法

生成树

图G的生成子图如果是树，则称为G的生成 树(支撑树)。 定理2.4 图G有生成树的充要条件为G是 连通的． 证 如果G不连通，那么它的任何一个生成 子图都不连通，因此G没有生成树． 如果G连通，那么G必有连通的生成子图 (特别地， G本身便是)．设G的最小连通生 成子图为T，那么对T的每一条边e，图T-e 不连通，由定理2.1(6)，T是树．又T是G的 一个生成子图，所以T是G的生成树．
vV

导出矛盾．故G至少有两个度数为1的顶点． 树的度数为1的顶点称为悬挂点
练习
用Δ(G)表示G中顶点的最大度。证明：若G 是Δ(G) ≥k的树，则G至少有k个顶点的度为1。 证明：假设顶点v的度为Δ(G) ，则G-v有Δ(G) 个分支，而每个分支中至少有两个悬挂点， 故必有G中的一个1度点。
定理2.1的证明