树 (图论)
维基百科,自由的百科全书
在图论中,树是任意两个顶点间有且只有一条路径的图。森林是任意两个顶点间至多有一条路径的图。
[编辑] 定义
如果一个无向简单图G是一棵树,必须满足这个条件: G是连通图,而且没有简单环。如果在G中加入一条边,就会有一个环。如果在G中断开一条边,就不会连通。G中的任意两个顶点能被唯一的简单路径连接。
如果G有有限个顶点,(设为n个顶点),还满足以下条件:
- G是连通的,有n-1条边,并且G没有简单环。
如果一个无向简单图G中没有简单环,那么G是森林。
[编辑] 例子
[编辑] 树的类型
- 自由树
- 有根树
- 有向树
- 二叉树
- 满二叉树
- 完全二叉树
- Positional tree
- 空树