《数据结构与算法》课程教学资源（PPT课件讲稿）第三章 树 3.1 树的有关定义

第三章树 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也成立

3.T连通且有n1条边 4.T有n-1条边且无回路 口3→4:假定T有回路,设C是其中一条含有 k(<n)个结点的初级回路。因为T连通,所 以v(T)-V(c)中一定有结点u与C上某点v相 邻,即存在边(uv)∈E(T),依此类推,最 终v(T)-V(C)中的n-k个结点需要n-k条边 才可能保持T连通,但|E(T)-E(c)|=(n 1)-k<n-k矛盾

3. T连通且有n-1条边 4. T有n-1条边且无回路  3→4：假定T有回路，设C是其中一条含有 k(<n)个结点的初级回路。因为T连通，所 以V(T)-V(C)中一定有结点u与C上某点v相 邻，即存在边(u,v)E(T)，依此类推，最 终V(T)-V(C)中的n-k个结点需要n-k条边 才可能保持T连通，但|E(T)-E(C)|=(n- 1)-k<n-k.矛盾

4.T有n-1条边且无回路 5.T的任意两结点间有唯一道路 口45:设uν是T的任意两结点,先近道路P(u)的存在性,即证 明T是连通的。反证法。 如果T不是连通的,则至少有两个连通分支T1T2由已知T中无回路 可知,T1T2也没有回路。根据1→2→3的证明,再由T和T2是 连通的且无回路可得,m(T1)=n(T1)-1,m(T2)=n(T2)-1,则 有 m(T)=m(T1)+m(T2)=(n(T1)+n(T2)-2=n-2<n-1 与已知m(T)=n-1矛盾 再证唯一性。若存在两条不同的道路P(uv),P′(uv),则其对称 差P(uv)⊕P’(uv)至少含有一个回路。 注:G1G2=(vE其中V=V1V2E=E1E2

4. T有n-1条边且无回路 5. T的任意两结点间有唯一道路  4→5：设u,v是T的任意两结点，先证道路P(u,v)的存在性，即证 明T是连通的。反证法。 如果T不是连通的，则至少有两个连通分支T1, T2.由已知T中无回路 可知，T1, T2也没有回路。根据1 → 2 → 3的证明，再由T1和T2是 连通的且无回路可得，m(T1)=n(T1)-1, m(T2)=n(T2)-1, 则 有： m(T)=m(T1)+m(T2)=(n(T1)+n(T2))-2=n-2<n-1 与已知m(T)=n-1矛盾. 再证唯一性。若存在两条不同的道路P(u,v), P’(u,v)，则其对称 差P(u,v)P’(u,v)至少含有一个回路。 注：G1G2=(V,E),其中V=V1V2,E=E1E2;

5.T的任意两结点间有唯一道路 6.T无回路,但在任两结点间加上一条边后恰有一个回路 1.T连通且无回路 口5>6:显然成立 口6→1:只要证明T是连通的。反证法。 假设T不连通,设T1T2为T中的两个连通分 支。v1为T1中的一个顶点,Vv2为T2中的一 个顶点。在T中加边(v1V2)不形成回路。 矛盾

5. T的任意两结点间有唯一道路 6. T无回路, 但在任两结点间加上一条边后恰有一个回路 1. T连通且无回路  5→6：显然成立  6→1：只要证明T是连通的。反证法。 假设T不连通，设T1,T2为T中的两个连通分 支。v1为T1中的一个顶点，v2为T2中的一 个顶点。在T中加边(v1,v2)不形成回路。 矛盾。 v1 v2 v3 v4 v5 v6

总结 树是极小的连通图,减少一条边就不连通 ■树是极大的不含回路的连通图,增加一条边就 有回路

总结 ◼ 树是极小的连通图，减少一条边就不连通 ◼ 树是极大的不含回路的连通图，增加一条边就 有回路

树的有关定义 口定理3.13 树T中一定存在树叶结点。 证明:由于T是连通图所以任结点v∈v(T),都有 d(v;)≥1.若无树叶则d(v)≥2.这样 m=∑d()≥ 矛盾

树的有关定义  定理3.1.3 树T中一定存在树叶结点. 证明: 由于T是连通图,所以任一结点viV(T), 都有 d(vi)≥1. 若无树叶, 则d(vi)≥2. 这样 矛盾. n − = m = d(vi )  n 2 1 1