6.3树与支撑树

第三节树与支撑树树及其基本性质支撑树及其基本性质1.树及其基本性质树：一个连通且无回路的图(除非特别声明，以后所说的回路皆指初级回路).森林：一个无回路的图.H1∪H2：子图H1和子图H2的边的并集.H1∩H2：子图H1和子图H2的边的交集.H1\H2：在子图H1中但不在子图H2中的边的集合.G+e：在图G中加连边e.G-e：在图G中去掉边e.G-i：在图G去掉点i及与点i关联的所有边.树及其基本性质定理6.3.1设T=(N,E)是的一个图,则下列六个定义是等价的(1)T连通且无回路(2)T有|N|-1条边且无回路(3)T连通且有|N|-1条边(4)T连通且每条边都是割边(5)T的任两点间都有唯一的路相连(6)T无回路，但在任一对不相邻的点间加连一条边，则构成唯一的一个回路证明按照(1)→(5)→(6)→(4)→(3)→(2)→(1)的顺序来讨论等价性(1)→(5)：T连通且无回路→T的任两点间都有唯一的路相连证明：设T连通且无回路，任给T的两个点i和j，因为T连通，所以i和j之间至少存在一条路。又因为T无回路，所以i和j之间又不能有两条或两条以上的路。于是i和j之间有唯一一条路。树及其基本性质续定理6.3.2每个树至少有两个次为1的点证明任给树T=(N,E)，因为T连通，所以T中每个点的次至少为1，即任给i∈N，都有d(i)≥1，但iNdi=2|E|=2|N|-2()因此至少有两个点的次为1支撑树及其基本性质图G的支撑树：G的一个是树的支撑子图.G的反树：T*=G\T.其中T=(N,E')是G=(N,E)的一个支撑树Ω(e)：割集{S1,S2}，其中S1,S2为T-e的两个连通分支的点集合支撑树及其基本性质续定理6.3.3G有支撑树当且仅当G是连通的.定理6.3.4任给图G，设T是G的支撑树，e是T的一条边,则存在唯一的一个割集Ω(e)包含于T*+e中。定理6.3.5设T1和T2是G的两个支撑树，且|T1\T2|=k，则T2经过k次迭代后就得到T1。证明定理6.3.3G有支撑树当且仅当G是连通的。证明设G有支撑树T，因为T连通，所以G具有连通的子图，因此G连通。反之，设G连通，考虑G的极小连通支撑子图T，显然T的每条边也都是割边，因此T是G的一个支撑树。证明定理6.3.4任给图G，设T是G的支撑树，e是T的一条边，则存在唯一的一个割集Ω(e)包含于T*+e中。证明T-e是不连通的，记它的两个连通分支为T1,T2，并记N(T1)=S，显然S=N(T2)，T1G[S]，T2G[S]，且Ω(e)={S,S}。令Ω'(e)T*+e也是G的一个割集，且Ω'(e)={S'，S'}。因为G\Ω'(e)T-e=T1∪T2即G[S']∪G[S']T1∪T2注意到G[S']，G[S']是两个互不相交的非空连通图，且S'∪S'=N(T1)∪N(T2)适当选择记号必有G[S']T1，G[S']T2，于是S'=N(T1)=S，这就意味着Ω'(e)=Ω(e)，因此Ω(e)是唯一的。提示定理6.3.5设T1和T2是G的两个支撑树，且|T1\T2|=k则T2经过k次迭代后就得到T1.提示:令e∈T1\T2,则T2+e包含唯一的一个回路C(e),并且C(e)上至少有一条边e'∈T2\T1,因此T2'=T2+e-e'仍是一个支撑树。但|T1∩T2|=|T1∩T2'|-1我们称T2到T2'为一次迭代。由此可见，由T2变为T1经过|T2\T1|次迭代即可。