南京大学：《离散数学》课程教学资源（PPT课件讲稿）Lecture 23 树的基本概念

1 树的基本概念

树的基本概念 1

回顾 口问题1：什么是二部图及其匹配？ ▣两个无内部边的顶点集；互不相邻的边的集合 口问题2：二部图中的有哪些匹配？ 口完备匹配：一个部饱和，充要条件为Hal定理 口最大匹配：充要条件为无增广路径(Berge定理) ▣稳定匹配：每个节点有线性序，稳定匹配算法

 问题1：什么是二部图及其匹配？  两个无内部边的顶点集；互不相邻的边的集合  问题2：二部图中的有哪些匹配？  完备匹配：一个部饱和，充要条件为Hall定理  最大匹配：充要条件为无增广路径（Berge定理）  稳定匹配：每个节点有线性序，稳定匹配算法 回顾

本节提要 口内容1：树的定义及其性质 ▣内容2：根树以及有序根树的遍历

 内容1：树的定义及其性质  内容2：根树以及有序根树的遍历 本节提要

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

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

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

 设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 树中的通路