G T1 T2 T3 T5 T6 T8
G T1 T2 T3 T4 T5 T6 T7 T8
T1={1,2,3};T2={1,2,4};T3={1,2,5};T4={1 3,5};T5={1,4,5};T6={2,3,4};T7={2,3,5}; T8={3,4,5} n, -2 ★树余(补树)(树支、连支) 在图G中与树T互补的子图称为树余( cotree),树中 所含的边称为树支( tree branch),树余中所包含 的边称为连支(link) ★林和余林 在由s个分离部分组成的非连通图中,各分离部分的 树的集合构成一个包含个树的林( (forest),林的补图 称为余林( coforest)
T1 ={1, 2, 3}；T2 ={1, 2, 4}；T3 ={1, 2, 5}；T4 ={1, 3, 5}；T5 ={1, 4, 5}；T6 ={2, 3, 4}；T7 ={2, 3, 5}； T8 ={3, 4, 5}。 −2 = t n nt t ★树余（补树）（树支、连支） 在图G中与树T互补的子图称为树余（cotree）,树中 所含的边称为树支（tree branch），树余中所包含 的边称为连支(link) ★林和余林 在由s个分离部分组成的非连通图中，各分离部分的 树的集合构成一个包含s个树的林(forest)，林的补图 称为余林(coforest)
★树支:树的支路 定理1:一个树有n=n2-1个树支 证明:可用数学归纳法证明如下: 1=2时,树支数为1,定理成立; 假设n=k时定理成立(树支数为k1); 现考虑nt=k+1的连通图G,在G中任选一个树T,在 T中至少存在这样一个节点,它只与一条支路相关联 (否则T中每一节点至少与两条支路关联,必会形成回 路,与T是树的假设矛盾)。现从G中移去上述节点与 支路后,剩余的部分T1必为G1的一个树,由假设其 树支数为k1,故T有k条树支
★树支： 树的支路 定理1：一个树有n = nt -1个树支。 证明：可用数学归纳法证明如下： nt =2时，树支数为1，定理成立； 假设nt =k时定理成立(树支数为k-1)； 现考虑nt =k +1的连通图G，在G中任选一个树T，在 T中至少存在这样一个节点，它只与一条支路相关联 (否则T中每一节点至少与两条支路关联，必会形成回 路，与T是树的假设矛盾)。现从G中移去上述节点与 支路后，剩余的部分T1必为G1的一个树，由假设其 树支数为k-1，故T有k条树支
★连支:补树的支路 推论:一个补树有=b-(n-1)个树支。 图G的秩=n=nt-1. 图G的环秩=l=b-(nt-1) 定理2:一个树的任意两节点间有且仅有一条通路 证明:因为树连通所有节点且无回路。 定理3:一个树的任意两节点间若加上连支,必存在 个唯一的单连支回路(单连支回路也称为基本回路)。 证明:这是由于树加上一条支路后,该两节点之间就 有两条通路,即形成了一个回路,又由定理2得知该 回路是唯一的。 有向图的单连支回路:规定以该连支的方向作为相应 基本回路的绕向
★连支： 补树的支路 推论：一个补树有l = b-( nt –1)个树支。 图G的秩= n = nt –1 . 图G的环秩= l = b-( nt –1) . 定理2：一个树的任意两节点间有且仅有一条通路。 证明：因为树连通所有节点且无回路。 定理3：一个树的任意两节点间若加上连支，必存在一 个唯一的单连支回路(单连支回路也称为基本回路)。 证明：这是由于树加上一条支路后，该两节点之间就 有两条通路，即形成了一个回路，又由定理2得知该 回路是唯一的。 有向图的单连支回路：规定以该连支的方向作为相应 基本回路的绕向
割集( cut set) ★割集Q ①移走这些支路后图G分为两个部分 ②少移走其中任一条支路图仍连通。 ★割集几何意义 一闭合面所一次切割到的支路集合 ★基本割集Q 对应连通图G某个选定的树中的一条树支与相应的 组连支所构成的单树支割集。 ★有向图的单树支割集: 规定以该树支的方向作为相应基本割集法线的方向
二、割集 (cut set) ★割集Q ① 移走这些支路后图G分为两个部分； ② 少移走其中任一条支路图仍连通。 ★割集几何意义 一闭合面所一次切割到的支路集合 ★基本割集Qf 对应连通图G某个选定的树中的一条树支与相应的一 组连支所构成的单树支割集。 规定以该树支的方向作为相应基本割集法线的方向。 ★有向图的单树支割集：