离散数学第六章

2014-3-31 离散数学 6
树是点比边多一的连通图
证明：因G是树，所以G连通，
明 q=p–1： (1) p=1时，显然q=p–1 ； (2)假设对顶点数少于p的树，结论成立； (3) 对于p个顶点的树G ，p2 , 取e=uv ∈E(G) , 由 定理6.1.1知，e是唯一的(u,v)––通路，于是， G–e不连通而且恰有两个连通分支G1(p1,q1)和 G2(p2，q2),显然，p1<p且p2<p .由归纳假设， q1=p1–1 , q2=p2–1 , 从而q=q1+q2+1=p1+p2–1=p–1 。
2014-3-31
离散数学
9
树若减条边就会不连通
证明：任取u,v ∈V(G) , 若uv∈E(G) , 则u和v
是连通的；若uv E(G) , 则有(4)知，G+uv有 唯一的回路C。由于G中无回路，所以，u,v必 在回路C上，显然，C – uv是G的连通子图，从 而G中含(u,v)–通路，即uv,故G是连通图。
树中至少有两个悬挂点
定理
6.1.3 任何非平凡树G(p,q)中至少有两个 顶点的度数为1（悬挂点 ）。 证明：(反证) 已知G中每个点的度 dG(v)1 ， 若G中最多只有一个点的度数为1，则G中至少 有p–1个顶点的度数大于或等于2，于是， 2q= d (v) 2(p–1) +1 > 2(p–1) = 2q
离散数学
18
去边破回路法
定理6.2.1给出了一种求连通图的生成树的方法：
= {e1，e2，…，eq} for i = 1 to q do //逐条考察G的边// if 删去ei后G仍然是连通的 then 删去ei。 这种方法称为去边破回路法。 e14 e13 例如： e
令E(G)
e1
2014-3-31 离散数学 29
Kruskal 算法
⑴初始化：E’:= E(G); ET:=; i:=1; j:=1; ⑵sort(E’); //将G的边按权从小到大排序// ⑶while j＜ p do ⑷ begin //循环挑选p-1条边// ⑸ if G[ET∪{ei}]无回路 then begin ET:= ET∪{ei}; j:= j+1 end ⑹ i:= i + 1; ⑺end{while}
构）的数目。设 e=xy是图G的一条边，x≠y,于是 (G) = (G–e) + (G e ) 证明：将G的生成树按含e与否分为两类： （1）不含e的生成树即为G–e的生成树；而G–e的生成 树都不含e，所以G的不含e的生成树有(G–e) 个。 （2）包含e的生成树即为包含了收缩e边后的那个顶点 的生成树，故G的含了e的生成树数目为(G e )个。 由（1）和（2）知结论成立。
对任意e∈E(G)
, 若G – e仍连通，则说明G中含 有回路，此与(4)矛盾，故G – e不连通。
2014-3-31
离散数学
10
少条边就会不连通的图是树
只须证G中无回路。
若G中含回路C，取e=xy∈E(C) ,则 C – e仍连 通，任取u,v∈V(G) ,因G连通，故G中有(u,v)––通 路P。若P不含e，则u,v在G – e中仍连通；若 P中 含e，则P中的e可以用C – e中的(x,y)––通路代替， 从而u,v在G – e中仍连通。总之，u与v在G – e中 连通，此与(5)矛盾。故G无回路，因此，G是树。
第六章 树
§6.1 树的定义
定义6.1.1：
连通无回路的图称为树。 让我们来看一下《数据结构》中的树的定义： 一棵树是一个或多个顶点的有限集合T，使得， ⑴有一个特殊标识的顶点，称为根； ⑵除根以外的其余顶点形成n≥0个划分，T1 ， T2 ，… ，Tn，它们也都是树，称为根的子树。 这里的树的定义更为一般。《数据结构》中树 的定义与此定义的区别只是指定了一个特殊的 顶点 ——根，并由此使得顶点之间形成了层次 结构，而它同样也是一个无回路的连通图。
通路、二叉树排序，各种层次结构的表示、等 等。可以说，在计算机领域中几乎处处可以见 到她的婆娑身影。
例如：右图就是用树
– * + a b
4
表示的算术表达式： (a+b)* c – d /c
/ c d e
2014-3-31
离散数学
树中只有单通路
y P1 x 树T中任何两个顶点之间恰有一条 6.1.1 通路。 v u Pxy 证明: (存在性)因为树是连通图，所以任意两点 P2 之间有通路。 (唯一性)设u,v∈V(T),若u和v之间有两条不同的 (u,v)通路P1,P2，于是必有边xy,xy∈E(P1),但 xyE(P2),显然H=P1∪P2-xy是连通图，从而H中 存在(x,y)-通路Pxy.于是Pxy+xy是T中的一条回路， 与树的定义相矛盾。所以定理得证。 此定理的逆不一定成立。
2014-3-31 离散数学 17
去边破回路法
定理6.2.1给出了一种求连通图的生成树的方法：
令E(G)
= {e1，e2，…，eq} for i = 1 to q do //逐条考察G的边// if 删去ei后G仍然是连通的 then 删去ei。
这种方法称为去边破回路法。 例如：
2014-3-31
2014-3-31 离散数学 16
连通是有生成树的充要条件
定理6.2.1：
图G有生成树当且仅当G是一
个连通图。 证明：若G连通，则存在一个G的连通子 图T满足：T连通且从T中去掉任何一条边 后T不连通，于是由定理6.1.2(5)知，G的 生成子图T是树，故T是G的生成树； 反之，若G不连通，则G的任何生成 子图也不连通，故G无生成树。

oc
c b 3 2
a b 3(1)
定理6.2.2 树的任意一条边被收缩后仍为树。 证明：树的任意一条边被收缩后，其顶点数减1， 边数也减1，且收缩后的图仍为连通图，由定理 6.1.2(2)知结论成立。
2014-3-31 离散数学 20
图的生成树的数目
定理
6.2.3 以下用(G)表示图G的不同生成树（包括同
2014-3-31
离散数学
21
求一个图的生成树的数目
给定图G为： (G) = = + +( + +
=
=
(
)
+
(
+
+
)
)+ (
+ + +
)+ (
+ +
离散数学
)
=8
22
=
+
Байду номын сангаас
+
+
2014-3-31
例中图G的八棵生成树
计算(G)中最后出现了八个图：
除第一个外，它们并不是图G的生成树。
图G的八个生成树是：
2014-3-31 离散数学 28
Kruskal 算法的思想
给定连通图G，设G的各边权非负且无环： 首先选择一条权值最小的边； 然后逐条增加边的数目。增加的方法是： 从未选入的边中挑选一条不会形成回路 的权值最小边。 这样一直到选满p-1条边。 显然，这样得到的是无回路的p-1条边的 子图，由定理6.1.2可知这是一棵生成树。
2014-3-31 离散数学 25
完全图的生成树的数目
定理 6.2.4 (Cayley公式)：(Kn) = nn–2 ， n2。 证明：完全图Kn的生成树的数目就是所有由n
个顶点构成的树的数目。 由前面对树的编码可知，每棵n个顶点的 树有一个n-2位的编码，而每个n-2位的编码对 应一棵n个顶点的树。因此编码与树是一对一 的映射。有多少个编码就有多少棵树。 n-2位的编码有nn-2个，所以， (Kn) = nn–2。 注意不同的生成树可以是同构的。例如： (K6) = n4=1296，可是K6互不同构生成树只有6个。
定理
2014-3-31 离散数学 5
几种等价说法
定理
6.1.2 设G(p,q) 是一个图，于是，下列五 种说法相互等价： G是树； (1) (2) G连通且q = p – 1; (2) (3) G无回路且q = p – 1; (3) (4) G无回路,但对任意的u,v∈V(G),若uv E(G),则 G+uv中恰有一条回路； (4) (5) G连通，但对任意e ∈E(G) , G–e不连通。(5) (1)
e2
e5
e3
e4
e6
e7
e9 e10 e8
e11
15
e12
19
显然，考察边的顺序不同会产生不同的生成树。
2014-3-31 离散数学
边的收缩运算
定义6.2.2：
设G是连通图，e∈E(G)，删去e并 使e的两端点重合，此过程称为e的收缩。所得 的图记为Goe 。 例如： G：1 G ：
a 2
2014-3-31
离散数学
11
少条边就不连通的图是树的证明图示
P不含e：
u
C
v
P含e：
u
C
v
x
e
y
x
e y
P
P
G
2014-3-31 离散数学
G
12
平凡树和森林
只有一个顶点的图（平凡图）称为平凡
树。 具有多个连通分支，且每个连通分支都 是树的图称为森林。
2014-3-31
离散数学
13
2014-3-31 离散数学 7
下对p做归纳证
树是点比边多一的无回路图
假设G有回路，则显然可以依次从各回路中去
掉边而保持G的连通性。设从G中去掉了k条边 得到G的一个无回路的连通生成子图T，由定义 知T是G的生成树，且其边数是q–k ,顶点数是p, 由(2)知 q– k = p –1 但已知 q =p–1, 因此必有k =0 .这说明G本身就 无回路。