Please enable JavaScript.
Coggle requires JavaScript to display documents.
树 (生成树, 无向树及其性质, 根树及其应用) - Coggle Diagram
树
生成树
基本概念
G的树——T 是G 的子图并且是树
生成树T的树枝——T 中的边
G的生成树——T 是G 的生成子图并且是树
生成树T的弦——不在T 中的边
生成树T的余树 T拔 ——全体弦组成的集合的导出子图
基本回路
求法是设弦e = (u, v),现在树种求u到v的路径，在此基础上并上弦e，就得到基本回路
基本割集
生成树存在条件
无向图G具有生成树当且仅当G连通.
推论2：余树的边数为m-(n-1）
推论1：G为n阶m条边的无向连通图，则m>=n-1.
推论3 ：T拔为G的生成树T的余树，C 为G中任意一个圈，则C
与 余树一定有公共边
无向树及其性质
基本概念
无向树其实就是无向图，但没有回路
平凡树——平凡图
森林——至少由两个连通分支（每个都是树）组成
树叶——1度顶点
分支点——度数为2的顶点
等价定义
设G=<V,E>是n阶m条边的无向图
G 中任意两个顶点之间存在惟一的路径
G 中没有回路，但在任何两个不同的顶点之间加一条新
边，在所得图中得到惟一的一个含新边的圈.
G 是树
G 中无回路且 m=n-1.
G 是连通的且 G 中任何边均为桥
G 是连通的且 m=n-1
注意，离散中一个节点的度数和数据结构中一个节点的度数定义不同，离散重复考虑，数据结构只考虑子，不重复
一种题型：利用
1.边数和度数的关系（握手定理）
和
2.边数和顶点数的关系求解，
并做同构图，做同构图时关键是先找到度数最大的节点，然后次大，逐渐排列
根树及其应用
基本定义
根树
一个顶点入度为0，其余的入度均为1
有向树（基图为无向树）
树根——入度为0的顶点
树叶——入度为1，出度为0的顶点
内点——入度为1，出度不为0的顶点（就是中间点）
分支点——树根与内点的总称
顶点v的层数——从树根到v的通路长度
树高——T 中层数最大顶点的层数
分类
r 叉树——每个分支点至多有r 个儿子
r 叉有序树——r 树是有序的
r 叉正则树——每个分支点恰有r 个儿子
性质
r 叉正则树的性质: 在r 叉正则树中，其树叶数为t，
分枝点数为i，则 (r-1)i=t-1
r 叉完全正则树——树叶层数相同的r叉正则树