南京大学：《离散数学 Discrete Mathmatics》课程教学资源（课件讲稿，2018）图论——第26章 树的基本概念

树的基本概念 离散数学一树 南京大学计算机科学与技术系

树的基本概念 离散数学─树 南京大学计算机科学与技术系

殼壁嘉 内容提要 。树的定义 ·树的性质 ·根树 ·有序根树的遍历

内容提要  树的定义  树的性质  根树  有序根树的遍历

线兔 树的定义 ·定义：不包含简单回路的连通无向图称为树。 ●森林（连通分支为树) 。树叶/分支点（度为1？) 互不同构的6个顶点的树

树的定义  定义：不包含简单回路的连通无向图称为树。  森林（连通分支为树）  树叶/分支点（度为1？） 互不同构的6个顶点的树

校线 树中的通路 ·设T是树，则u,V∈VT,T中存在唯一的uV-简单通路。 .7 证明：T是连通图，.u,v∈V,T中存在uv-简单通路。 假设T中有两条不同的uv-简单通路P,P2。不失一般性，存在 e=(x,y)满足：e∈P1但eEP2,且在路径P,上x比y靠近u。令 T*=T-{e},则T*中包含P,于是(P中的xu-段)+P2+(P中的vy 段)是T*中的xy-通路，∴.T*中含xy-简单通路（记为P),则 P'+e是T中的简单回路，与树的定义矛盾。 Pi P2

树中的通路  设T是树，则u,vVT , T中存在唯一的 uv-简单通路。  证明：T是连通图，u,vVT , T中存在uv-简单通路。 假设T中有两条不同的uv-简单通路P1 ,P2。不失一般性，存在 e=(x,y)满足：eP1但eP2，且在路径P1上x比y靠近u。令 T*=T-{e}，则T*中包含P2 , 于是(P1中的xu-段)+P2 +( P1中的vy- 段)是T*中的xy-通路，T*中含xy-简单通路(记为P’)，则 P’+e是T中的简单回路，与树的定义矛盾。 u x y v  P2 P1

急售扇 有关树的几个等价命题 ·设T是简单无向图，下列四个命题等价： (1)T是不包含简单回路的连通图。/树的定义 (2)T中任意两点之间有唯一简单通路。 (3)T连通，但删除任意一条边则不再连通。 (4)T不包含简单回路，但在任意不相邻的顶点对之间加一 条边则产生唯一的简单回路。 ●备注： ●树是边最少的连通图 ●树是边最多的无简单回路的图

有关树的几个等价命题  设T是简单无向图，下列四个命题等价： (1) T是不包含简单回路的连通图。//树的定义 (2) T中任意两点之间有唯一简单通路。 (3) T连通，但删除任意一条边则不再连通。 (4) T不包含简单回路，但在任意不相邻的顶点对之间加一 条边则产生唯一的简单回路。  备注：  树是边最少的连通图  树是边最多的无简单回路的图

树中边和点的数量关系 。设T是树，令n=|Vl,m=El,则m=n-l。 证明.对n进行归纳证明。当n=l,T是平凡树，结论显然成立。 假设当n≤k是结论成立。 若n=k+l。因为T中每条边都是割边，任取eeET-{e}含两 个连通分支，设其为T,T,并设它们边数分别是m1,m2, 顶点数分别是n1,n2,根据归纳假设：m1=n1-1,m2n21。 注意：n1+n2n,m1+m2m-l。 ∴.m=m,+m,+1=n-1

树中边和点的数量关系  设T是树，令n=|VT |, m=|ET |, 则m=n-1。  证明. 对n进行归纳证明。当n=1, T是平凡树，结论显然成立。 假设当nk是结论成立。 若n=k+1。因为T中每条边都是割边，任取eET , T-{e}含两 个连通分支，设其为T1 , T2 , 并设它们边数分别是m1 , m2 , 顶点数分别是n1 , n2 , 根据归纳假设：m1 =n1 -1, m2 =n2 -1。 注意：n1 +n2 =n, m1 +m2 =m-1。 m= m1 +m2 +1=n-1

急售房 连通图边数的下限 。J顶点数为n（n≥2)的连通图，其边数mm-l。 (对于树，m=n-1,“树是边最少的连通图”) 。证明：对n进行一般归纳。当n=2时结论显然成立。 设G是边数为m的连通图，且IVc=n>2。任取veVc,令 G’=G-y,设G有o(o≥1)个连通分支G1,G2,…,G。,且G的边数 和顶点数分别是m和n。 我们有n=n1+n2+..+n。+1,m≥m1+m2+..+m。+0(每个连通分 支中至少有一个顶点在G中与删除的v相邻)。 由归纳假设，m2n-1(=1,2,.o)。 所以：m2m1+m2+..+mo+0≥n1+n2+..+no0+0=n-1

连通图边数的下限  顶点数为n（ n2）的连通图，其边数mn-1。 (对于树，m=n-1, “树是边最少的连通图”)  证明：对n进行一般归纳。当n=2时结论显然成立。 设G是边数为m的连通图，且|VG |=n>2。任取vVG，令 G’=G-v,设G’有(1)个连通分支G1 ,G2 ,…,G，且Gi的边数 和顶点数分别是mi和ni。 我们有n=n1 +n2 +…+n +1, mm1 +m2 +…+m + (每个连通分 支中至少有一个顶点在G中与删除的v相邻)。 由归纳假设，mi ni -1(i=1,2,…)。 所以：m m1 +m2 +…+m +n1 +n2 +…+n -+=n-1

与边点数量关系有关的等价命题 设T是简单无向图，下列三个命题等价： (1)T是树。 (2)T不含简单回路，且m=n-1。 (3)T连通，且m=n-1。 。(1)→(2)，已证。 ·(2)→(3)，若不连通，分支数o0≥2，各分支为树（无简单回 路、连通)，则m=n-0<n-1,矛盾。 ●(3)→(1)，设e是T中任意一条边，令T'=T-e,且其边数和顶点 数分别是m和n,则m'=m-1=n-2<n-1,.T”是非连通图。因 此，G的任意边均不在简单回路中，.G中无简单回路

与边点数量关系有关的等价命题  设T是简单无向图，下列三个命题等价： (1) T是树。 (2) T不含简单回路，且m=n-1。 (3) T连通，且m=n-1。  (1)(2), 已证。  (2)(3), 若不连通，分支数2，各分支为树（无简单回 路、连通），则m=n-<n-1，矛盾。  (3)(1), 设e是T中任意一条边，令T’=T-e, 且其边数和顶点 数分别是m’和n, 则m’=m-1=n-2<n-1, T’是非连通图。因 此，G的任意边均不在简单回路中，G中无简单回路

线兔 根树的定义 。定义：底图为树的有向图称为有向树。 ●定义：若有向树恰含一个入度为0的顶点，其它顶 点入度均为1，则该有向树称为根树，那个入度为 0的顶点称为根

根树的定义  定义：底图为树的有向图称为有向树。  定义：若有向树恰含一个入度为0的顶点，其它顶 点入度均为1，则该有向树称为根树，那个入度为 0的顶点称为根

售嘉 根树中的有向通路 ·若v是根树T的根，则对T中任意其它顶点y,存在唯 一的有向yoy,-通路，但不存在ynyo-通路。 假设oyn通路p 多于1条 假设从y.到o 也有通路 (c)

根树中的有向通路  若v0是根树T的根,则对T中任意其它顶点vn ,存在唯 一的有向v0 vn -通路,但不存在vn v0 -通路。 v0 vi 假设 p v0 vn -通路 多于１条 (b) v0 vn 假设从 vn 到 v0 也有通路 (c) v0 vk w1 入度>1 (a) vn vn