西北工业大学《离散数学（第6版）》课件-第9章树.pdfVIP

第九章 树 1 2008-2018 by Li Weigang. All rights reserved. 主要内容 树及其性质  生成树 有向树及其应用 2 9.1 无向树及其性质 定义9.1 (1) 无向树——无回路的连通无向图 (2) 平凡树——平凡图 (3) 森林——至少由两个连通分支（每个都是树）组成 (4) 树叶——1度顶点 (5) —— 2 分支点 度数 的顶点 3 无向树的等价定义 9.1 G= V,E n m 定理 设 是 阶 条边的无向图，则下面各命题 是等价的： (1) G 是树 (2) G 中任意两个顶点之间存在惟一的路径. (3) G 中无回路且m n1. (4) G 是连通的且m n1. 是连通的且删除 中任何边使得 变得不连通 (5) G G G . (6) G 中没有回路，但在任何两个不同的顶点之间加一条新 边，在所得图中得到惟一的一个含新边的圈. 4 证明思路 关键一步是 若路径不惟一必有回路 (1)(2). , . (2)(3). G 若 中有回路，则回路上任意两点之间的路径不 . n m n1. 惟一 对 用归纳法证明 正确 设 时正确，证 时也对 取 中任意边 n=1 . nk n k+1 : G e, Ge G ,G ( ?), n k, 有且仅有两个连通分支 1 2 为什么 它们的顶点满足 i m n 1, i=1,2. m m +m +1 n +n 2+1 n1. 由归纳假设得 i i 于是 1 2 1 2 (3)(4). G . . G s s2 只需证明 连通 用反证法 否则 有 （ ）个连通 . m n 1, 分支都是小树 于是有 i i ， s s m m n s n s (s 2)   i i i