文档介绍：2017/11/11
管理运筹学课程组 ftp://
1
第二节最小树问题
一、树及其性质
定义1: 无圈的连通图称为树。树一般用T表示。
定理1: 任给树T=(V,E),若n(T)≥2,则
T中至少有两个悬挂点。
证明:设 Q=(v1,v2,…,vk)是G中含边数最多的一条初等链,因 n(T )≥2,并且T是连通的,故链 Q中至少有一条边,从而v1与vk是不同的。
现证v1是悬挂点,即d(v1)=1。
2017/11/11
管理运筹学课程组 ftp://
2
反证法:如d(v1)≥2,则存在边[v1,vm],使m≠2,
若vm不在Q上,
v1
v2
vk
vm
那么(vm,v1,v2,…,vk)比Q链边数多一条,与Q是边数最多的链矛盾。
若vm在Q上
v1
v2
vk
vm
(v1,v2,…, vm, v1)是圈,与T是树矛盾。
所以必有d(v1)=1,即v1是悬挂点。
同理可证:vk也是悬挂点。所以G至少有两个悬挂点。
2017/11/11
管理运筹学课程组 ftp://
3
(1)T是一个树。
(2)T无圈,且m=n-1。
(3)T连通,且m=n-1。
定理2 图T=(V,E), p=n, q=m,则下列关于
树的说法是等价的。
边数=点数-1
(4)T无圈,但每加一条新边即得唯一一个圈。
(5)T连通,但每丢掉一条边就不连通。
(6)T中任意两点,有唯一链相连。
先证明(6)→(1)
2017/11/11
管理运筹学课程组 ftp://
4
证明:(1)→(2)
由于T是树,由定义知T连通且无圈。只须证明m=n-1。
归纳法:当n=2时,由于T是树,所以两点间显然有且
仅有一条边,满足m=n-1。
假设 n=k-1时命题成立,即有k-1个顶点时,T有k-2条边。
当n=k时,因为T连通无圈,k个顶点中至少有一个点次为1。设此点为u,即u为悬挂点,设连接点u的悬挂边为[v,u],从T中去掉[v,u]边及点u ,不会影响T的连通性,得图T’,T’为有k-1个顶点的树,所以T’有k-2条边,再把( v,u)、点u加上去,可知当T有k个顶点时有k-1条边。
2017/11/11
管理运筹学课程组 ftp://
5
(2)→(3) 只须证T是连通图。
反证法设T不连通,可以分为l个连通分图(l≥2),
设第i个分图有ni个顶点,
因为第i个分图是树,所以有ni-1条边,l个分图共有边数为:
与已知矛盾。所以T为连通图。
(3)→(4)、(4)→(5)、(5)→(6)、及(6)→(1)的证明略。
2017/11/11
管理运筹学课程组 ftp://
6
定理2:图T是树,则T中的边数m等于点数n减1, 即:m=n-1
证明:如图图T是树,则依树的定义,则T 是连通图,对于m=n-1可以用数学归纳法证明。
(1)当n=1时,m=0,m=n-1成立。
(2)当n=1时,m=1,m=n-1成立。
(3)假设当n=k时,m=n-1成立。
2017/11/11
管理运筹学课程组 ftp://
7
(4)对于k+1个顶点的图T而言,由树的性质1可知,T中至少有两个悬挂点。
设v1是T的一个悬挂点,考虑图T-{v1},则图T-{v1} 的顶点数为K,由归纳假设可得:
,因为,
,则,证毕。
2017/11/11
管理运筹学课程组 ftp://
8
证明:必要性因T是连通的,故任两个点之间至少有一条链。但如果某两个点之间有两条链的话,那么图T中含有圈,这与树的定义矛盾,从而任两个点之间恰有一条链。
充分性设图T中任两个点之间恰有一条链,那么易见T是连通的,如果T中含有圈,那么这个圈上的两个顶点之间有两条链,这与假设矛盾,故T不含圈,于是T是树。
定理3:图T是树的充分必要条件是任意两个顶点之间恰有一条链。
2017/11/11
管理运筹学课程组 ftp://
9
(1)T是无圈图
(2)T是连通图
(3)T中边数为点数减1,即
(4)T中减去一条边则不连通
(5)T中加一条边则恰有一个圈
(6)T中至少有两个悬挂点
根据树的定义及其三个性质的证明,我们可以归纳出树T的六个基本性质,即:
2017/11/11
管理运筹学课程组 ftp://
10
二、图的支撑树
定义2 设图T=[V,E’]是图G=(