离散数学第十六章课件

1、1第十六章第十六章 树树主要内容主要内容l 无向树及其性质无向树及其性质l 生成树生成树l 根树及其应用根树及其应用 216.1 无向树及其性质无向树及其性质定义定义16.1 (1) 无向树无向树连通无回路的无向图连通无回路的无向图(2) 平凡树平凡树平凡图平凡图(3) 森林森林至少由两个连通分支（每个都是树）组成的无向至少由两个连通分支（每个都是树）组成的无向图图(4) 树叶树叶1度顶点度顶点(5) 分支点分支点度数度数 2的顶点的顶点 3无向树的等价定义无向树的等价定义定理定理16.1 设设G=是是n阶阶m条边的无向图，则下面各命题条边的无向图，则下面各命题是等价的：是等价的：(1) G

2、是树是树(2) G 中任意两个顶点之间存在惟一的路径中任意两个顶点之间存在惟一的路径.(3) G 中无回路且中无回路且 m=n 1. (4) G 是连通的且是连通的且 m=n 1.(5) G 是连通的且是连通的且 G 中任何边均为桥中任何边均为桥.(6) G 中没有回路，但在任何两个不同的顶点之间加一条新中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到惟一的一个含新边的圈边，在所得图中得到惟一的一个含新边的圈. 4)(2)()1(2xnxvdni 由上式解出由上式解出x 2. 定理定理16.2 设设T是是n阶非平凡的无向树，则阶非平凡的无向树，则T 中至少有两片树叶中至少有两片

3、树叶. 无向树的性质无向树的性质证证 设设 T 有有 x 片树叶，由握手定理及定理片树叶，由握手定理及定理16.1可知，可知，5例题例题例例1 已知无向树已知无向树T中有中有1个个3度顶点，度顶点，2个个2度顶点，其余顶点度顶点，其余顶点全是树叶，试求树叶数全是树叶，试求树叶数. 解解 解本题用树的性质解本题用树的性质m=n 1，握手定理，握手定理. 设有设有x片树叶，于是片树叶，于是 n = 1+2+x = 3+x, 2m = 2(n 1) = 2 (2+x) = 1 3+2 2+x解出解出x = 3，故，故T有有3片树叶片树叶.6例例2 已知无向树已知无向树T有有5片树叶，片树叶，2度与度

4、与3度顶点各度顶点各1个，其余顶个，其余顶点的度数均为点的度数均为4，求，求T的阶数的阶数n例题例题解解 设设T的阶数为的阶数为n, 则边数为则边数为n 1，4度顶点的个数为度顶点的个数为n 7. 由握手定理得由握手定理得 2m = 2(n 1) = 5 1+2 1+3 1+4(n 7)解出解出n = 8，4度顶点为度顶点为1个个. 7子图子图定义定义14.8 G=, G =(1) GG G 为为G的的子图子图，G为为G 的的母图母图(2) 若若GG且且V =V，则称，则称G 为为G的的生成子图生成子图(3) 若若VV或或EE，称，称G 为为G的的真子图真子图(4) V （VV且且V）的）的导

5、出子图导出子图，记作，记作GV (5) E （EE且且E）的）的导出子图导出子图，记作，记作GE 在图中，设在图中，设G为为(1)中图所表示，取中图所表示，取V1=a，b，c，则，则V1的导出子图的导出子图GV1为为(2)中图所示。取中图所示。取E1=e1，e3，则，则E1的导出子图的导出子图GE1为为(3)中中图所示。图所示。8不一定连通，也不一定不含回路，如图所示T定义定义16.2 设设G为无向图为无向图(1) G的的树树T 是是G 的子图并且的子图并且T是树是树(2) G的的生成树生成树T 是是G 的生成子图并且的生成子图并且T是树是树(3) 生成树生成树T的的树枝树枝G 的在的在T 中

6、的边中的边(4) 生成树生成树T的的弦弦G 的的不在不在T 中的边中的边(5) 生成树生成树T的的余树余树 T的所有弦的导出子图的所有弦的导出子图T16.2 生成树生成树9推论推论2 的边数为的边数为m n+1. T推论推论3 为为G的生成树的生成树T的余树，的余树，C为为G中任意一个圈，则中任意一个圈，则C与与 一定有公共边一定有公共边. .证证 否则，否则，C中的边全在中的边全在T中，这与中，这与T为树矛盾为树矛盾. TT定理定理16.3 无向图无向图G具有生成树当且仅当具有生成树当且仅当G连通连通.生成树存在条件生成树存在条件推论推论1 G为为n阶阶m条边的无向连通图，则条边的无向连通图

7、，则m n 1. 证证 必要性显然必要性显然.充分性用破圈法（注意：在圈上删除任何一条边，不破坏充分性用破圈法（注意：在圈上删除任何一条边，不破坏连通性）连通性）由定理由定理16.3和树的边数等于顶点数减和树的边数等于顶点数减1可立即得到下述推论。可立即得到下述推论。10基本回路系统基本回路系统定理定理16.4 设设T为为G的生成树，的生成树，e为为T的任意一条弦，则的任意一条弦，则T e中中含一个只有一条弦其余边均为含一个只有一条弦其余边均为T的树枝的圈的树枝的圈. 不同的弦对应的不同的弦对应的圈也不同圈也不同. 证证 设设e=(u,v)，在，在T中中u到到v有惟一路径有惟一路径 ，则，则

8、e为所求的圈为所求的圈. 定义定义16.3 设设T是是n阶阶m条边的无向连通图条边的无向连通图G的一棵生成树，设的一棵生成树，设e 1, e 2, , e m n+1为为T 的弦的弦. 设设Cr为为T 添加弦添加弦e r 产生的只含弦产生的只含弦e r、其余边均为树枝的圈、其余边均为树枝的圈. 称称Cr为为G的对应树的对应树T 的弦的弦e r的的基本基本回路回路或或基本圈基本圈，r=1, 2, , m n+1. 并称并称C1, C2, ,Cm n+1为为G对应对应T 的的基本回路系统基本回路系统，称，称m n+1为为G的的圈秩圈秩，记作，记作 (G). 求基本回路的算法：设弦求基本回路的算法：

9、设弦e=(u,v)，先求，先求T中中u到到v的路径的路径 uv，再并上弦再并上弦e，即得对应，即得对应e的基本回路的基本回路. 11Ca=aefCb=bdeCc=cdf此图的圈秩为此图的圈秩为3，基本回路系统为：基本回路系统为：Ca, Cb, Cc基本回路系统基本回路系统在下图中，对应生成树的弦在下图中，对应生成树的弦a，b，c的基本回路为：的基本回路为：12基本割集的存在基本割集的存在定理定理16.5 设设T是连通图是连通图G的一棵生成树，的一棵生成树，e为为T的树枝，则的树枝，则G中存在只含树枝中存在只含树枝e，其余边都是弦的割集，且不同的树枝对，其余边都是弦的割集，且不同的树枝对应的割集

10、也不同应的割集也不同.证证 由定理由定理16.1可知，可知，e是是T的桥，因而的桥，因而T e有两个连通分支有两个连通分支T1和和T2，令，令 Se=e | e E(G)且且 e 的两个端点分别属于的两个端点分别属于V(T1)和和V(T2)，由构造显然可知由构造显然可知Se为为G的割集，的割集，e Se且且Se中除中除e外都是弦，外都是弦，所以所以Se为所求为所求. 显然不同的树枝对应的割集不同显然不同的树枝对应的割集不同. 13定义定义16.4 设设T是是n阶连通图阶连通图G的一棵生成树，的一棵生成树，e 1, e 2, , e n 1为为T 的树枝，的树枝，Si是是G的只含树枝的只含树枝e

11、 i的割集，则称的割集，则称Si为为G的对应的对应于生成树于生成树T由树枝由树枝e i生成的生成的基本割集基本割集，i=1, 2, , n 1. 并称并称S1,S2, , Sn 1为为G 对应对应T 的的基本割集系统基本割集系统，称，称n 1为为G的的割割集秩集秩，记作，记作 (G). 基本割集与基本割集系统基本割集与基本割集系统求基本割集的算法求基本割集的算法设设e 为生成树为生成树T 的树枝，的树枝，T e 为两棵小树为两棵小树T1与与T2，令，令 Se =e | e E(G)且且e的两个端点分别属于的两个端点分别属于T1与与T2 则则Se 为为e 对应的基本割集对应的基本割集. 14Sa

12、=a,f,gSb=b,g,hSd=d,h,iSc=c,f,hSe=e,f,i基本割集系统为：基本割集系统为：Sa , Sb , Sc , Sd , Se割集秩为割集秩为5.基本割集与基本割集系统基本割集与基本割集系统在下图中，对应树枝在下图中，对应树枝a，b，c，d，e的基本割集分别为：的基本割集分别为：15解解 弦弦e, f, g对应的基本回路分别为对应的基本回路分别为 Ce=e b c, Cf=f a b c, Cg=g a b c d, C基基=Ce, Cf, Cg. 树枝树枝a, b, c, d对应的基本割集分别为对应的基本割集分别为 Sa=a, f, g, Sb=b, e, f, g

13、, Sc=c, e, f g, Sd=d, g, S基基=Sa, Sb, Sc, Sd. 例例 下下图图实线边所示为生成树，求基本回路系统与实线边所示为生成树，求基本回路系统与基本割集系统基本割集系统实例实例16最小生成树最小生成树定义定义16.5 T是无向连通带权图是无向连通带权图G=的生成树的生成树(1) T的权的权W(T)T的各边权之和的各边权之和(2) G的最小生成树的最小生成树G的所有生成树中权最小的生成树的所有生成树中权最小的生成树求最小生成树的一个算法求最小生成树的一个算法避圈法避圈法（Kruskal）设）设G=，将，将G中非环边按权从小中非环边按权从小到大排序：到大排序：e1,

14、 e2, , em.(1) 取取e1在在T中中(2) 查查e2，若，若e2与与e1不构成回路，取不构成回路，取e2也在也在T 中，否则弃去中，否则弃去e2.(3) 再查再查e3, 直到得到生成树为止直到得到生成树为止. 17例例4 求图的一棵最小生成树求图的一棵最小生成树.所求最小生成树如所求最小生成树如图所示，图所示，W(T)=38.实例实例1816.3 根根树及其应用树及其应用定义定义16.6 有向树有向树T 基图为无向树的有向图。基图为无向树的有向图。(1) T 为为根树根树T 中一个顶点入度为中一个顶点入度为0，其余顶点入度均为，其余顶点入度均为1的有向树的有向树.(2) 树根树根入度

15、为入度为0的顶点的顶点(3) 树叶树叶入度为入度为1，出度为，出度为0的顶点的顶点(4) 内点内点入度为入度为1，出度不为，出度不为0的顶点的顶点(5) 分支点分支点树根与内点的总称树根与内点的总称(6) 顶点顶点v的的层数层数从树根到任意顶点从树根到任意顶点v的路径的长度（即路的路径的长度（即路径中的边数）径中的边数）(7) 树高树高T 中所有顶点的最大层数中所有顶点的最大层数(8) 平凡根树平凡根树平凡图平凡图19根树的画法根树的画法:树根放上方树根放上方,省去所有有向边上的箭头省去所有有向边上的箭头如右图所示如右图所示 a是树根是树根 b,e,f,h,i是树叶是树叶 c,d,g是内点是内

16、点 a,c,d,g是分支点是分支点 a为为0层层;1层有层有b,c; 2层有层有d,e,f; 3层有层有g,h; 4层有层有i. 树高为树高为4根根树实例树实例20家族树与根子树家族树与根子树定义定义16.7 设设T 为一颗非平凡的根树为一颗非平凡的根树(1) 祖先与后代祖先与后代 vi ，vj V(T)， vi vj ，若，若vi 可达可达vj ，则称，则称vi 为为vj的祖先的祖先 ， vj为为vi的后代的后代 。(2) 父亲与儿子父亲与儿子 vi ，vj V(T)， vi vj ，若，若vi 邻接到邻接到vj（即（即 E(T) ） ，则称，则称vi 为为vj的父亲的父亲 ， vj为为vi

17、的儿子的儿子 。(3) 兄弟兄弟 vj ，vkV(T)， vj vk ，若，若vj ，vk的父亲相同的父亲相同 ，则，则称称vj与与vk是兄弟是兄弟 。定义定义16.8 设设v为根树为根树T中的任意一个顶点，称中的任意一个顶点，称v及其后代的导出子及其后代的导出子图图Tv为为T的以的以v为根的为根的根子树根子树.常将根树看成家族树，家族中成员之间的关系由下面的定义给出：常将根树看成家族树，家族中成员之间的关系由下面的定义给出：21根树的分类根树的分类(1) T 为为有序根树有序根树同层上的顶点都标定次序的根树同层上的顶点都标定次序的根树(2) 根据根树根据根树T中的每个分支点儿子数以及是否有序

18、，可以将中的每个分支点儿子数以及是否有序，可以将根树分为下列各类：根树分为下列各类： r 叉树叉树每个分支点至多有每个分支点至多有r 个儿子个儿子 r 叉有序树叉有序树r叉树是有序的叉树是有序的 r 叉正则树叉正则树每个分支点恰有每个分支点恰有r 个儿子个儿子 r 叉正则有序树叉正则有序树又若又若r 叉正则树是有序的叉正则树是有序的 r 叉完全正则树叉完全正则树树叶层数相同的树叶层数相同的r叉正则树叉正则树 r 叉完全正则有序树叉完全正则有序树又若又若r 叉完全正则树是有序的叉完全正则树是有序的 2叉正则有序树的每个分支点的两个儿子导出的根子树分别叉正则有序树的每个分支点的两个儿子导出的根子树

19、分别称为该分支点的左子树和右子树。称为该分支点的左子树和右子树。 在所有的在所有的r叉树中，最常用的是叉树中，最常用的是2叉树。下面介绍叉树。下面介绍2叉树的应叉树的应用。用。22定义定义16.9 设设2叉树叉树T 有有t片树叶片树叶v1, v2, , vt，权分别为，权分别为w1, w2, , wt，称，称 为为T 的权，其中的权，其中l(vi)是是vi 的层数的层数. 在所有有在所有有t片树叶，带权片树叶，带权w1, w2, , wt 的的2叉树中，权最小的叉树中，权最小的2叉树称为叉树称为最优最优2叉树叉树. )()(1itiivlwtW最优二叉树最优二叉树求最优求最优2叉树的算法叉树的

20、算法 Huffman算法算法给定实数给定实数w1, w2, , wt ，且，且w1 w2 wt . （1）作）作t片树叶片树叶, 分别以分别以w1, w2, , wt为权为权.（2）在所有入度为）在所有入度为0的顶点的顶点(不一定是树叶不一定是树叶)中选出两个权最小中选出两个权最小的顶点的顶点, 添加一个新分支点添加一个新分支点, 以这以这2个顶点为儿子个顶点为儿子, 其权等于这其权等于这2个儿子的权之和个儿子的权之和.（3）重复（）重复（2）, 直到只有直到只有1个入度为个入度为0 的顶点为止的顶点为止. W(T)等于所有分支点的权之和等于所有分支点的权之和23例例 5 求带权为求带权为1,

21、 1, 2, 3, 4, 5的最优树的最优树. 解题过程由下图给出，解题过程由下图给出，W(T)=38最优二叉树的算法最优二叉树的算法Huffman算法算法24最佳前缀码最佳前缀码定义定义16.10 设设 1 2 n-1 n是长度为是长度为 n 的符号串的符号串(1) 前缀前缀该符号串的子串该符号串的子串 1, 1 2, , 1 2 n 1 (2) 前缀码前缀码符号串集合符号串集合A= 1, 2, , m中的任意两个符中的任意两个符号串都互不为前缀号串都互不为前缀(3) 二元前缀码二元前缀码 i (i=1, 2, , m) 中只出现两个符号，如中只出现两个符号，如0与与1. 如何产生二元前缀码

22、？如何产生二元前缀码？定理定理16.6 一棵一棵2叉树产生一个二元前缀码叉树产生一个二元前缀码.推论推论 一棵正则一棵正则2叉树产生惟一的叉树产生惟一的一个二元一个二元前缀码（按左子树前缀码（按左子树标标0，右子树标，右子树标1）25一棵一棵2元树产生一个二元前缀码元树产生一个二元前缀码:对每个分支点对每个分支点, 若关联若关联2条边条边, 则给左边标则给左边标0, 右边标右边标1; 若只关联若只关联1条边条边, 则可以给它标则可以给它标0(看作左边看作左边), 也可以也可以标标1(看作右边看作右边). 将从树根到每一片树叶的通路上标将从树根到每一片树叶的通路上标的数字组成的字符串记在树叶处的

23、数字组成的字符串记在树叶处, 所得的字符串所得的字符串构成一个前缀码，如右图所示：构成一个前缀码，如右图所示：最优最优2进制编码：使信息传递的进制编码：使信息传递的2进制数最短进制数最短由最优由最优2叉树产生的前缀码为最佳前缀码。叉树产生的前缀码为最佳前缀码。用最佳前缀码传输的二进制位数最省。用最佳前缀码传输的二进制位数最省。最佳前缀码最佳前缀码26图所示二叉树产生的前缀码为图所示二叉树产生的前缀码为 00, 10, 11, 011, 0100, 0101 二叉树产生的前缀码二叉树产生的前缀码27用用Huffman算法产生最佳前缀码算法产生最佳前缀码例例16.7 在通信中，八进制数字出现的频率

24、如下：在通信中，八进制数字出现的频率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6：5% 7：5%求传输它们的最佳前缀码，并求传输求传输它们的最佳前缀码，并求传输10n（n 2）个按上述比）个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的例出现的八进制数字需要多少个二进制数字？若用等长的（长为（长为3）的码字传输需要多少个二进制数字？）的码字传输需要多少个二进制数字？28解解 用用100个八进制数字中各数字出现的个数，即以个八进制数字中各数字出现的个数，即以100乘各频乘各频率为权，并将各权由小到大排列，得率为权，并将各权由小到大排列，得w1=5

25、, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25。用。用Huffman算法求以频率算法求以频率(乘以乘以100)为权的最优为权的最优2叉树。用此权产生的最优叉树。用此权产生的最优2叉叉树如下图所示：树如下图所示： 求最佳前缀码求最佳前缀码传传100个按比例出现的八进个按比例出现的八进制数字所需二进制数字的个制数字所需二进制数字的个数为数为 W(T)=285，传，传10n(n 2)个个按比例出现的八进制数字按比例出现的八进制数字需要需要2.85 10n个个二进制数字二进制数字，用等长码用等长码(长为长为3)传输需传输需3 10n个二进制数字个二进制

26、数字. 01-0 11-1 001-2 100-3 101-4 0001-500000-6 00001-7它产生的最优前缀码它产生的最优前缀码29波兰符号法与逆波兰符号法波兰符号法与逆波兰符号法行遍或周游根树行遍或周游根树T对根树对根树T的每个顶点访问且仅访问一次的每个顶点访问且仅访问一次. 对于对于2叉有序正则树有以下三种周游方式：叉有序正则树有以下三种周游方式： 中序行遍法中序行遍法访问的次序为：左子树、根、右子树访问的次序为：左子树、根、右子树 前序行遍法前序行遍法访问的次序为：根、左子树、右子树访问的次序为：根、左子树、右子树 后序行遍法后序行遍法访问的次序为：左子树、右子树、根访问的

27、次序为：左子树、右子树、根对如右图所示的根树对如右图所示的根树T（2叉有序正则叉有序正则树树）按中序、前序、后序行遍的周游）按中序、前序、后序行遍的周游结果分别为：结果分别为： b a (f d g) c e， a b (c (d f g) e)， b (f g d) e c) a30用用2叉有序正则树存放算式叉有序正则树存放算式存放规则存放规则l 最高层次运算放在树根最高层次运算放在树根l 然后依次将运算符放在根子然后依次将运算符放在根子树的根上树的根上l 数放在树叶上数放在树叶上l 规定：被除数、被减数放在规定：被除数、被减数放在左子树树叶上左子树树叶上 算式算式(b+(c+d) a) (

28、e f) (g+h) (i j)存放在如上图所示的存放在如上图所示的2叉有叉有序正则树上序正则树上. 31波兰符号法波兰符号法波兰符号法波兰符号法按前序行遍法访问存放算式的按前序行遍法访问存放算式的2叉有序正则树，其结果不加括号，叉有序正则树，其结果不加括号，规定从右到左每个运算符对它后面紧邻的两个数进行运算。在这规定从右到左每个运算符对它后面紧邻的两个数进行运算。在这种算法中，由于运算符在它的两个运算对象之前，所以称此种算种算法中，由于运算符在它的两个运算对象之前，所以称此种算法为前缀符号法或波兰符号法法为前缀符号法或波兰符号法. 对下图的访问结果为对下图的访问结果为 b + c d a e

29、 f + g h i j 逆波兰符号法逆波兰符号法按后序行遍法访问存放算式的按后序行遍法访问存放算式的2叉有序正则树，其结果不加括号，叉有序正则树，其结果不加括号，规定从左到右每个运算符对它前面紧邻的两个数进行运算。在这规定从左到右每个运算符对它前面紧邻的两个数进行运算。在这种算法中，由于运算符在它的两个运算对象之后，所以称此种算种算法中，由于运算符在它的两个运算对象之后，所以称此种算法为后缀符号法或逆波兰符号法法为后缀符号法或逆波兰符号法. 对上图的访问结果为对上图的访问结果为 b c d + + a e f g h + i j 32重点重点主要内容主要内容l 无向树及其性质无向树及其性质l

30、 生成树、生成树、最小生成树最小生成树、基本回路系统基本回路系统、基本割集系统基本割集系统l 根树及其分类根树及其分类、最优树最优树、二叉树产生的前缀码二叉树产生的前缀码、最佳前缀最佳前缀码码、波兰符号法波兰符号法、逆波兰符号法逆波兰符号法基本要求基本要求l 深刻理解无向树的定义及性质深刻理解无向树的定义及性质l 熟练地求解无向树熟练地求解无向树l 准确地求出给定带权连通图的最小生成树准确地求出给定带权连通图的最小生成树l 深刻理解基本回路、基本割集的概念，并会计算深刻理解基本回路、基本割集的概念，并会计算l 理解根树及其分类等概念理解根树及其分类等概念l 熟练掌握求最优树及最佳前缀码的方法熟

31、练掌握求最优树及最佳前缀码的方法l 掌握波兰符号法与逆波兰符号法掌握波兰符号法与逆波兰符号法33第十六章第十六章 习题课习题课主要内容主要内容l 无向树及其性质无向树及其性质l 生成树、最小生成树、基本回路系统、基本割集系统生成树、最小生成树、基本回路系统、基本割集系统l 根树及其分类、最优树、最佳前缀码、波兰符号法、逆波根树及其分类、最优树、最佳前缀码、波兰符号法、逆波兰符号法兰符号法基本要求基本要求l 深刻理解无向树的定义及性质深刻理解无向树的定义及性质l 熟练地求解无向树熟练地求解无向树l 准确地求出给定带权连通图的最小生成树准确地求出给定带权连通图的最小生成树l 深刻理解基本回路、基本

32、割集的概念，并会计算深刻理解基本回路、基本割集的概念，并会计算l 理解根树及其分类等概念理解根树及其分类等概念l 会画会画n阶（阶（n较小）非同构的无向树及根树（较小）非同构的无向树及根树（1 n 6）l 熟练掌握求最优树及最佳前缀码的方法熟练掌握求最优树及最佳前缀码的方法l 掌握波兰符号法与逆波兰符号法掌握波兰符号法与逆波兰符号法34为树叶数ttnnkii 2 kiitnm21tnivdtnmkiiniikii 212)(22222)2(3 kiinit（2）（3）从而解出从而解出练习练习11. 无向树无向树 T 有有ni个个i 度顶点，度顶点，i=2, 3, ,k，其余顶点全是树叶，其余顶

33、点全是树叶，求求T 的树叶数的树叶数. 解解 用树的性质：边数用树的性质：边数 m=n 1（n为阶数），及握手定理为阶数），及握手定理. (1) 352设设n阶非平凡的无向树阶非平凡的无向树T中，中， (T) k，k 1. 证明证明T至少至少 有有k片树叶片树叶. 证证 反证法反证法. 否则，否则，T至多有至多有s片树叶，片树叶，s k，下面利用握手定理及树的，下面利用握手定理及树的性质性质m = n 1推出矛盾推出矛盾. 由于由于 (T) k，故存在，故存在v0，d(v0) k. 于是，于是，sksnvdnmnii )1(2)(2221由此解出由此解出s k，这与，这与s k矛盾矛盾. 证本题的方法有多种，请用分支点都是割点来证明证本题的方法有多种，请用分支点都是割点来证明.练习