图论:树,图的生成树

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

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

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

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

2 回复
    • hannesgao
      hannesgao says:

      谢谢前辈斧正。这一段是从一个CSDN用户的博客上截取下来的,其实就是生成树是一个连通图的意思,为了方便理解原文已经修改。另外多谢及时帮我恢复藏经阁账户。

      回复

发表评论

Want to join the discussion?
Feel free to contribute!

发表评论