运筹学教案（Word版）--§6-3 树与支撑树.doc

文档介绍：§ 树与支撑树
1、树及其基本性质
树:一个连通且无回路(除非特别声明,以后皆指初级回路)的图
k-树(森林):有k个连通分支且无回路的图
:子图和子图的边的并集
:子图和子图的边的交集
:在子图中但不在子图中的边的集合
G + e:在图G中加连边e
G - e:在图G中去掉边e
G - i:在图G去掉点i及与点i关联的所有边
设T=(N,E)是的一个图,则下列六个定义是等价的:
(1)T连通且无回路;
(2)T有条边且无回路;
(3)T连通且有条边;
(4)T连通且每条边都是割边;
(5)T的任两点间都有唯一的路相连;
(6)T无回路,但在任一对不相邻的点间加连一条边,则构成唯一的一个回路。
每个树至少有两个次为1的点。
2、支撑树及其基本性质
图G的支撑树:的一个是树的支撑子图
G的反树:,其中是的一个支撑树
:割集,其中为的两个连通分支的点集合
G有支撑树当且仅当G是连通的。
任给图G,设T是G的支撑树, e是T的一条边,则存在唯一的一个割集包含于中。
设和是G的两个支撑树,且,则经过k次迭代后就得到.