连接的无向无环图与树

Question

当我通过麻省理工学院的书《算法导论》学习图论时，我参考了一些关于图和树的定义。

在麻省理工学院的《算法导论》第三版书中，附录树章节向我展示了定理 B.2，“自由树的性质”

令 G = (V,E) 为无向图。以下语句是等效的。

1. G是一棵自由树...
2. G 是无环的，并且 |E| =|V| - 1.

是否有一个不是树的连通、无向、无环图的例子？

理论上，如果存在满足|E|条件的无向无环图 =！|V| - 1，这可以作为例子吗？

如果有一个满足这个条件的例子，你能告诉我吗？

Answer 1

任何连通的无环图都是一棵树。树有几种不同的等效定义：

• 它们是连接的非循环图。
• 它们是比边多一个节点的连通图。
• 它们是最小连接图（它们是连接的，但删除任何边会使它们断开连接）
• 它们是最大的非循环图（它们是非循环的，并且添加任何缺失的边会创建一个循环）
• 它们是任意两个节点之间只有一条简单路径的图表。

所以不，你找不到不是树的连通无环图。:-)