运筹学讲义 Proof:(: refer to 02-02(1)Th2 for reference) F is a forests every connected component of F is a trees every edge of f is a cut edge. 支撑(生成)森林( spanning forest): F a spanning subgraph of a graph g which is itself a forest(本身是森林的支撑子图) 注:(1)图的支撑森林必定存在,且可能不唯一,但边数均为q=p- (2)图的支撑森林是其极大森林( maximal forest) F是图G的极大森林◇→F匚G是森林,且ⅤFcHG,H不是森林. (3)若F是图G的一个支撑森林,则F的边数为E=v-0,G的不在F上的边数为 (4)若F是图G的一个支撑森林,则ⅤG的一个连通分支H,F∩H是H的支撑树 例10求证:任一图G中都至少含有E-v+O个不同的圈,O≥1. 证明:(1)若O=1,则由例6得证:(2)若O≥2,则设G的各连通分支为G1G2,…G。,则 由例6知,G2中含有的不同的圈的个数至少为sG)-V(G)+1,i=1,2,…,O.于是,G中含有的 不同的圈的个数至少为∑[(G)-v(G)+1∑6(G)-∑v(G)+O=E-v+O运 筹 学 讲 义 10 Proof:(:refer to 02-02(1) Th2 for reference). F is a forest  every connected component of F is a tree  every edge of F is a cut edge.▌ 支撑（生成）森林（spanning forest）： F a spanning subgraph of a graph G which is itself a forest（本身是森林的支撑子图）. 注：（1）图的支撑森林必定存在，且可能不唯一，但边数均为 q = p − . （2）图的支撑森林是其极大森林（maximal forest）. F 是图 G 的极大森林  F  G 是森林，且  F  H  G ， H 不是森林. （3）若 F 是图 G 的一个支撑森林，则 F 的边数为  = − ， G 的不在 F 上的边数为  − ( −) =  − + . （4）若 F 是图 G 的一个支撑森林，则 G 的一个连通分支 H ， F  H 是 H 的支撑树. 例 10 求证：任一图 G 中都至少含有  − + 个不同的圈，  1. 证明：(1)若  =1 ，则由例 6 得证；(2)若   2 ，则设 G 的各连通分支为 G G G , , , 1 2  ，则 由例 6 知， Gi 中含有的不同的圈的个数至少为 (Gi ) −(Gi ) +1，i = 1,2,  , .于是， G 中含有的 不同的圈的个数至少为             − + =  − + = − + =1 =1 =1 [ ( ) ( ) 1] ( ) ( ) i i i i i Gi Gi G G .▌