连接的无向无环图与树

Question

当我正在学习MIT的算法导论中的图论时，我遇到了一些关于图和树的定义。

在MIT的《算法导论第三版》中，附录树章节向我展示了定理B.2，“自由树的特性”。

以下陈述等价于G =（V，E）为无向图，且满足以下条件：

1. G是一棵自由树

2. G是无环图，且| E |= | V |-1

有没有一个连通的、无向的、无环图，不是一棵树呢？

从理论上讲，如果存在一个无向无环图，满足| E | != | V |-1。那么这个图就是一个例子吗？

如果有满足该条件的样例，能否请您展示一下？

- Einstrasse

Answer 1

任何连通的无向无环图都是一棵树。以下是几个等价的树的定义：

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

所以，不，你找不到一个既连通又无环的非树形图。 :-)

- templatetypedef