离散数学 第十二章树 主要内容 ●无向树及其性质 ●生成树 ●根树及其应用 1
1 第十二章 树 主要内容 ⚫ 无向树及其性质 ⚫ 生成树 ⚫ 根树及其应用
离散数学 12.1无向树及其性质 定义12.1连通无回路的无向图称为无向树，简称树.每个连 通分支都是树的无向图称为森林.平凡图称为平凡树.在无 向树中，悬挂顶点称为树叶，度数大于或等于2的顶点称为 分支点 例 星形树
12.1 无向树及其性质 定义12.1 连通无回路的无向图称为无向树,简称树.每个连 通分支都是树的无向图称为森林.平凡图称为平凡树.在无 向树中,悬挂顶点称为树叶,度数大于或等于2的顶点称为 分支点． 例 f 星形树
离散数学 无向树的性质 定理12.1设G=<V,E>是阶条边的无向图，则下面各命题 是等价的： (1)G是树 (2)G中任意两个顶点之间存在惟一的路径. (3)G中无回路且n-1. (4)G是连通的且mn-1. (⑤)G是连通的且G中任何边均为桥. (⑥)G中没有回路，但在任何两个不同的顶点之间加一条新 边后所得图中有惟一的一个含新边的圈. 3
3 无向树的性质 定理12.1 设G=<V,E>是n阶m条边的无向图，则下面各命题 是等价的： (1) G 是树 (2) G 中任意两个顶点之间存在惟一的路径. (3) G 中无回路且m=n−1. (4) G 是连通的且m=n−1. (5) G 是连通的且G 中任何边均为桥. (6) G 中没有回路，但在任何两个不同的顶点之间加一条新 边后所得图中有惟一的一个含新边的圈
离散数学 证明 证(1)→(2).若路径不惟一，必有回路. (2)→3).若G中有回路，则回路上任意两点之间的路径不 惟一.对n用归纳法证明n-1. 当=1时成立.设≤k时成立，证=k+1时也成立：任取 一条边e,G-e有且仅有两个连通分支G,G2.n≤k,由归 纳假设得m,=n-1,=1,2.于是， tFm1+m2+1=n1+n2-2+1=n-1. (3)=→(4).只需证明G连通.用反证法.否则G有s(s≥2)个连通 分支，它们都是树.于是，有m,=-1, m=∑m,=∑4-s=n-ss≥2) i=1 i= 这与n-1矛盾. 4
4 (3)(4). 只需证明G连通. 用反证法. 否则G有s(s2)个连通 分支, 它们都是树. 于是, 有mi=ni−1, 这与m=n−1矛盾. 证明 (2)(3). 若G中有回路，则回路上任意两点之间的路径不 惟一. 对n用归纳法证明m=n−1. 当n=1时成立. 设nk时成立，证n=k+1时也成立：任取 一条边e，G−e有且仅有两个连通分支G1 ,G2 . nik，由归 纳假设得mi=ni−1, i=1,2. 于是， m=m1+m2+1=n1+n2−2+1=n−1. ( 2) 1 1 = = − = − = = m m n s n s s s i i s i i 证 (1)(2). 若路径不惟一, 必有回路
离散数学 证明 (4)→（⑤）.只需证明G中每条边都是桥.下述命题显然成立：G 是n阶m条边的无向连通图，则m心n-1. Ve∈E,G-e只有n-2条边，由命题可知G-e不连通，故e为桥 (⑤)=→>（⑥.由（⑤）易知G为树.由(1)→(2)知，u,veV(u≠v), u到v有惟一路径，加新边(w,)得惟一的一个圈. (6)→(1).只需证明G连通，这是显然的. 5
5 (4)(5). 只需证明G 中每条边都是桥. 下述命题显然成立: G 是 n 阶 m 条边的无向连通图，则 mn−1. eE, G−e只有n−2条边，由命题可知G−e不连通，故e为桥. 证明 (5)(6). 由(5)易知G为树. 由(1)(2)知，u,vV（uv）, u到v有惟一路径，加新边(u,v)得惟一的一个圈. (6)(1). 只需证明G连通，这是显然的