运筹学讲义 如 显然,若T是树,则v∈V(T),T-ν必是森林(∵T-v的各连通分支显然是树!) Lema1若图G无孤立点,且E≤v-(o≥1),则G至少有一个悬挂点 证明:(反证法)假设G无悬挂点,则由G无孤立点知,yv∈V,d(v)≥2,i=1,2,…,v 于是,2E=∑()2∑2=2→E≥v,与E≤v-0≤v-1矛盾■ 注:注意Lema1与§2.2.2 Lemma2的异同 性质:(1)F是森林台F的每一个连通分支都是树;树是连通分支数O=1的森林 (2)F是森林分E=v-(≥1) 证明:(1)∵森林的每一个连通分支都连通且无圈 (2)→设F是森林,其各连通分支为T1,T2…,T。,则由(1)知,T1,T2,…,T。都是树,故 6(F)=∑=(7)=∑()-1=∑v(T)-=v(F) ←设E=v-0,下证F无圈.W.L.0.G.设F无孤立点 (对v作数归法)当v=1时,O=1,E=V-0=0,无圈 设当=k-1时,无圈性成立,则当v=k时,由Lema知,F至少有一个悬挂点v 显然,(F-v)=k-1.∴由归纳假设知,F-V无圈.当然,F也无圈 故综上知,F无圈,从而F是森林■ 注:由(1)知,树是连通分支数O=1的森林;再由(2)知,树的边数为E=v-O=V-1 Th a graph F is a forest if and only if every edge of F运 筹 学 讲 义 9 如 显然，若 T 是树，则 v V(T) ，T −v 必是森林（  T −v 的各连通分支显然是树！） Lemma1 若图 G 无孤立点，且   − (  1) ，则 G 至少有一个悬挂点． 证明：（反证法）假设 G 无悬挂点，则由 G 无孤立点知， vi V,d(vi )  2,i =1,2,  , . 于是，  =    =     = = 2 ( ) 2 2 1 1 p i p i i d v ，与   −  −1 矛盾.▌ 注：注意 Lemma1 与§2.2.2 Lemma 2 的异同. 性质：（1） F 是森林  F 的每一个连通分支都是树；树是连通分支数  =1 的森林． （2） F 是森林   = − (  1) ． 证明：（1）  森林的每一个连通分支都连通且无圈． （2）  设 F 是森林，其各连通分支为 T T T , , , 1 2  ，则由（1）知， T T T , , , 1 2  都是树，故           =  =  − =  − = − = = = ( ) ( ) [ ( ) 1] ( ) ( ) 1 1 1 F T T T F i i i i i i .  设  = − ，下证 F 无圈.W.L.O.G.设 F 无孤立点. （对  作数归法）当  =1 时，  =1， = − = 0 ，无圈； 设当  = k −1 时，无圈性成立，则当  = k 时，由 Lemma1 知， F 至少有一个悬挂点 v . 显然，  (F − v) = k −1. 由归纳假设知， F − v 无圈.当然， F 也无圈. 故综上知， F 无圈，从而 F 是森林.▌ 注：由（1）知，树是连通分支数  =1 的森林；再由（2）知，树的边数为  = − = −1. Th A graph F is a forest if and only if every edge of F is a cut edge