第三章树 3.1树的有关定义 口给定一个图G=vE,如果它不含任何回 路,我们就叫它是林,如果G又是连通的 即这个林只有一个连通支,就称它是树 口定义31.1 一个不含任何回路的连通图称为树,用T表 示.T中的边称为树枝,度为1的节点称为树 叶
第三章 树 3.1 树的有关定义 给定一个图G=(V,E), 如果它不含任何回 路, 我们就叫它是林, 如果G又是连通的, 即这个林只有一个连通支, 就称它是树. 定义3.1.1 一个不含任何回路的连通图称为树, 用T表 示. T中的边称为树枝, 度为1的节点称为树 叶
树的有关定义 口树的每条边,都不会属于任何回路.这样的 边叫割边。 口定义312 设e是G的一条边,若G=G-e比G的连通 支树连通支数增加,则称e是G的一条割边 口显然,图G删去割边e=(uv)之后结点u v分属于不同的分支
树的有关定义 树的每条边, 都不会属于任何回路. 这样的 边叫割边. 定义3.1.2 设e是G的一条边, 若G’=G-e比G的连通 支树连通支数增加, 则称e是G的一条割边. 显然, 图G删去割边e=(u,v)之后, 结点u, v分属于不同的分支
树的有关定义 口定理3.1.1 e=(u,v)是割边当且仅当e不属于G的任何回路 证明: 必要性,设e三(u)是割边,此时若e=(u 路结点和属于同连通支,宋是割边盾 充分性。设e不属于G的任何回路此时着e不是割 边,帅Ge与G的连道数 U和v仍 属子同一连通支敌Q中存在追路F(u) (uv)+e就是G的一个回路矛盾
树的有关定义 定理3.1.1 e=(u, v)是割边,当且仅当e不属于G的任何回路. 证明: 必要性。设e=(u, v)是割边, 此时若e=(u, v)属 于G的某个回路, 则G’=G-e中仍存在u到v的道 路, 故结点u和v属于同一连通支, e不是割边.矛盾. 充分性。设e不属于G的任何回路, 此时若e不是割 边, 则G’=G-e与G的连通支数一样. 于是u和v仍 属于同一连通支. 故G’中存在道路P(u,v), P(u,v)+e就是G的一个回路.矛盾
树的有关定义 口定理312 设T是结点数为n≥2的树则下列性质等价 1.T连通且无回路 2.T连通且每条都是割边 3.T连通且有n-1条边 4.T有n1条边且无回路 5.T的任意两结点间有唯一道路 6.T无回路但在任两结点间加上一条边后恰有一个
树的有关定义 定理3.1.2 设T是结点数为n≥2的树, 则下列性质等价: 1. T连通且无回路 2. T连通且每条都是割边 3. T连通且有n-1条边 4. T有n-1条边且无回路 5. T的任意两结点间有唯一道路 6. T无回路, 但在任两结点间加上一条边后恰有一个 回路
T连通且无回路一>T连通且每条都是割边一)T连通且有n-1条边 口1→2:T无回路,即T的任意边e都不属于回路, 由定理3.1.1,e是割边。 口2→3:对结点数n进行归纳。令n(T,m(T)分别 表示树T的结点数和边数。当n=2时命题成立。设 n≤k时,m(T)=nT)-1成立。则n=k+1时 由于任一边e都是割边,故G′=G-e有两个连通 支T1T2由于n(T)≤k,i=12,故 n(T)=n(T)-1。所以mT)=n(T)-1也成立
T连通且无回路→T连通且每条都是割边→T连通且有n-1条边 1→2：T无回路，即T的任意边e都不属于回路， 由定理3.1.1，e是割边。 2→3：对结点数n进行归纳。令n(T), m(T)分别 表示树T的结点数和边数。当n=2时命题成立。设 n≤k时，m(T)=n(T)-1成立。则n=k+1时， 由于任一边e都是割边，故G’=G-e有两个连通 支T1, T2。由于n(Ti)≤k，i=1,2，故 m(Ti)=n(Ti)-1。所以m(T)=n(T)-1也成立