1、第三章 树3.1 树的有关定义o 给定一个图 G=(V,E), 如果它不含任何回路 , 我们就叫它是林 , 如果 G又是连通的 , 即这个林只有一个连通支 , 就称它是树 .o 无圈连通无向图称为 树 。 (*)o 定义 3.1.1一个不含任何回路的连通图称为树 , 用 T表示 . T中的边称为树枝 , 度为 1的节点称为树叶 .树的基本应用电线,水管,煤气有关度的若干术语o 孤立点 :度为 0的顶点o 悬点 :度为 1的顶点n 悬边 :与悬点关联的边o 奇点 :度为奇数的顶点o 偶点 :度为偶数的顶点o 正则图 :各顶点度相同n 若度为 k,称为 k-正则图 .n 例如 :Kn是 (n1)-
2、正则图树的有关定义o 树的每条边 , 都不会属于任何回路 . 这样的边叫割边 .o 定义 3.1.2设 e是 G的一条边 , 若 G=G-e比 G的连通支树连通支数增加 , 则称 e是 G的一条割边 .o 显然 , 图 G删去割边 e=(u,v)之后 , 结点 u, v分属于不同的分支 .树的有关定义o 定理 3.1.1e=(u, v)是割边 ,当且仅当 e不属于 G的任何回路 .证明 : 必要性。设 e=(u, v)是割边 , 此时若 e=(u, v)属于 G的某个回路 , 则 G=G-e中仍存在 u到 v的道路 , 故 结 点 u和 v属于同一 连 通支 , e不是割 边 .矛盾 .充分性
3、。 设 e不属于 G的任何回路 , 此 时 若 e不是割边 , 则 G=G-e与 G的 连 通支数一 样 . 于是 u和 v仍属于同一 连 通支 . 故 G中存在道路 P(u,v), P(u,v)+e就是 G的一个回路 .矛盾 .树的有关定义o 定理 3.1.2设 T是结点数为 n2的树 , 则下列性质等价 :1. T连通且无回路2. T连通且每条都是割边3. T连通且有 n-1条边4. T有 n-1条边且无回路5. T的任意两结点间有唯一道路6. T无回路 , 但在任两结点间加上一条边后恰有一个回路T连通且无回路 T连通且每条都是割边 T连通且有 n-1条边o 12: T无回路,即 T的任意
4、边 e都不属于回路,由定理 3.1.1, e是割边。o 23:对结点数 n进行归纳。令 n(T), m(T)分别表示树 T的结点数和边数。当 n=2时命题成立。设nk时, 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连通且有 n-1条边4. T有 n-1条边且无回路o 34:反证,假定 T存在圈,去掉圈上一条边,还是联通的,但 m(T)=n-2,不能保证联通了。 4. T有 n-1条边且无回路5. T的任意两结点间有唯一道
5、路o 45:设 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-2n-1与已知 m(T)=n-1矛盾 .再证唯一性。若存在两条不同的道路 P(u,v), P(u,v),则其对称差 P(u,v)P(u,v)至少含有一个回路。注: G1G2=(V,E),其中 V=V1V2,E=E1E2;5. T的任意两结点间有唯一道路6. T无回路 , 但在任两结点间加上一条边后恰有一个回路1. T连通且无回路o 56:显然成立o 61: 只要证明 T是连通的。反证法。假设 T不连通,设 T1,T2为 T中的两个连通分支。 v1为 T1中的一个顶点, v2为 T2中的一个顶点。在 T中加边 (v1,v2)不形成回路。矛盾。 v1v2 v3v4 v5 v6