第三章 树及其应用(新).pdfVIP

第三章树及其应用

第一节树的基本概念

定义1树是无圈连通无向图.树中度数为1的结点称为

树的叶.树中度数大于1的结点称为树的分枝点或内

点.不相交的若干树称为森林,即森林的每个连通分

枝是树.

定理1T是树T中无环,且任何两结点间有且仅有一

条路.

证:1.(→)必要性:因为T是树,故对T中任意不同的两个结

点x,y之间至少存在一条路.若x,y之间存在T中两条不

同的路P和P,则P和P中至少有一边不同,不妨设

1212

eP,但eP.设e={u,v},显然在P和P的并中删去e后

1212

的图仍然连通,故在PP-e中存在uv路P,所以P+e是

12

圈,矛盾.

v2.充分性:只需证明T中无圈即可.若T中有圈C,当C只

有一个结点时,则T中有环;若C中有两个结点,则T中有

平行边;若V(C)3,则对C中的任意两个结点,均有两条

不同的路,矛盾,因此,T是无圈连通图,即T是树.

定理2T是树T连通对有W(T-e)=2.

证明:1.必要性:若T是树,由定理1,T连通,且T中无环和无平

行边,故T为简单连通图.设e={x,y},则W(T-e)2.又由定

理1,xey是T中唯一xy路,故则W(T-e)2.所以W(T-e)=2

2.充分性:只需证明T中无圈即可.若T中有圈C,且

e={x,y}E(C),又W(T-e)=2,所以1=W(C-e)W(T-e)=2,

矛盾.所以T连通无圈,从而T是树.

定理3T是树T连通且=|E|=n-1,其中为T的

边数,n为T的顶点数.

证明:必要性:若T是树,由定理2,对T中的任意一条边e,

有W(T-e)=2,故当T中删去n-1条不同的边时,有W(T-

e-e-…e)=n,有树中无圈,此时n个连通分支即为n个

12n-1

孤立结点,从而有=n-1.

充分性:若n=1,显然=0;若n=2,显然=1;此时结论显然

成立.设任何n阶且边数=n-1的连通图不含圈.则对n+1

阶且边数=n的连通图T,显然(T)1.若(T)2,则2=

2n=矛盾.故存xV(T),使得Deg(x)

=1.从而T-x是n阶图,且T-x只有n-1条边.由归纳假设T-

x不含圈,从而T为不含圈的连通图,即T为树.

推论T是森林=n-w,其中为T的边数,n为T的顶点数,w

为T的连通分枝数.

定理4设T是n阶非平凡树(平凡图称为平凡树),则

T中至少有2片树叶.

证:设T是n阶非平凡树,则(T)1,并设T有

条边,k片树叶,则

又=n-1,故k2.

定义2设T是有向图,若T的基础图是树,称T

是有向树.

定义3仅一个结点的入度为0,其余所有结点的

入度都为1的有向树称为根树.入度为0的结点

称为根.出度为0的结点(度数为1的结点)仍称

为叶;出度不为0的结点称为分枝点或内点.由

根到某一顶点v的有向路的长度,称为v的层数.

根树的高度就是顶点层数的最大值.

例1用根树可以表示家庭之间的关系.（p94）

定义4如果在根树中规定了每一层上顶点的次序,

这样的根树称为有序树.

规定同一层次的定点的次序从左到右（即不能互换）

也可以用边的次序代替顶点的次序.（p95）

定义5每个结点的出度不大于m的有序根树称为m叉