树的基本概念 离散数学一树 南京大学计算机科学与技术系
树的基本概念 离散数学─树 南京大学计算机科学与技术系
殼壁嘉 内容提要 。树的定义 ·树的性质 ·根树 ·有序根树的遍历
内容提要 树的定义 树的性质 根树 有序根树的遍历
线兔 树的定义 ·定义:不包含简单回路的连通无向图称为树。 ●森林(连通分支为树) 。树叶/分支点(度为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,vVT , T中存在唯一的 uv-简单通路。 证明:T是连通图,u,vVT , T中存在uv-简单通路。 假设T中有两条不同的uv-简单通路P1 ,P2。不失一般性,存在 e=(x,y)满足:eP1但eP2,且在路径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是平凡树,结论显然成立。 假设当nk是结论成立。 若n=k+1。因为T中每条边都是割边,任取eET , 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( n2)的连通图,其边数mn-1。 (对于树,m=n-1, “树是边最少的连通图”) 证明:对n进行一般归纳。当n=2时结论显然成立。 设G是边数为m的连通图,且|VG |=n>2。任取vVG,令 G’=G-v,设G’有(1)个连通分支G1 ,G2 ,…,G,且Gi的边数 和顶点数分别是mi和ni。 我们有n=n1 +n2 +…+n +1, mm1 +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 -通路 多于1条 (b) v0 vn 假设从 vn 到 v0 也有通路 (c) v0 vk w1 入度>1 (a) vn vn