Am Schlossgarten

图论:树,图的生成树

树的定义:
如果一个无向简单图G满足以下相互等价的条件之一,那么G是一棵树:
1. G是没有回路的连通图。
2. G没有回路,但是在G内添加任意一条边,就会形成一个回路。
3. G是连通的,但是如果去掉任意一条边,就不再连通。
4. G内的任意两个顶点能被唯一路径所连通。

如果向简单图G有有限个顶点(设为n个顶点),那么G是一棵树还等价于:
G是连通的,有n−1条边,并且G没有简单回路。

树的性质:
1. 每个节点有零个或多个子节点;
2. 没有父节点的节点称为根节点;
3. 每一个非根节点有且只有一个父节点;(该性质决定了树内无回路)
4. 除了根节点外,每个子节点可以分为多个不相交的子树;

生成树的定义:
给定一个图,如果把一个连通图中的多余边全部删除,使其满足树的定义所要求的条件,所构成的树叫做这个图的生成树

© Am Schlossgarten | CC BY-NC-ND 4.0 International License

评论