【教学课件】第三节树与支撑树.ppt

第三节 树与支撑树,树及其基本性质支撑树及其基本性质,树及其基本性质,树：一个连通且无回路的图（除非特别声明，以后所说的回路皆指初级回路）森林：一个无回路的图H1H2：子图H1和子图H2的边的并集H1H2：子图H1和子图H2的边的交集H1H2：在子图H1中但不在子图H2中的边的集合G+e：在图G中加连边eG-e：在图G中去掉边eG-i：在图G去掉点i及与点i关联的所有边,树及其基本性质,定理 设T=(N,E)是|N|3的一个图，则下列六个定义是等价的:(1)T连通且无回路(2)T有|N|-1条边且无回路(3)T连通且有|N|-1条边(4)T连通且每条边都是割边(5)T的任两点间都有唯一的路相连(6)T无回路，但在任一对不相邻的点间加连一条边，则构成唯一的一个回路,树及其基本性质,定理 每个树至少有两个次为1的点,续,证明,支撑树及其基本性质,图G的支撑树：G的一个是树的支撑子图G的反树：T*=GT，其中T=(N,E)是G=(N,E)的一个支撑树(e)：割集S1,S2，其中S1,S2为T-e的两个连通分支的点集合,支撑树及其基本性质,定理 G有支撑树当且仅当G是连通的。定理 任给图G，设T是G的支撑树，e是T的一条边，则存在唯一的一个割集(e)包含于T*+e中。定理 设T1和T2是G的两个支撑树，且|T1T2|=k，则T2经过k次迭代后就得到T1。,续,