什么是非循环连接无向图？

Question

我正在阅读最小生成树的讲座,它说我们应该在无向图中找到连通的非循环子图.

我的问题是,连接的无向图是如何成为非循环的,因为它是连接的,你可以从任何顶点移动到任何顶点.

谁能告诉我我做错了什么？

Answer 1

这只是一个定义问题.见http://en.wikipedia.org/wiki/Cycle_(graph_theory).您似乎将其称为循环,在文章中称为封闭式散步:从顶点到自身的任何路径.正如您自己所说,使用该定义,任何连接的无向图都包含循环.但是,如果您要求从第二个到最后一个顶点的子路径是一个简单的路径(因此是简单的循环),即一个不包含重复顶点的路径,您最终会得到许多连接的无向图,这些图实际上是非循环的,例如树实例.显然,路径还必须包含至少3个边,否则任何(A,B,A)一个都是循环.

请考虑以下图表

     A         A
1)  / \   2)  / \
   B   C     B - C

只2)包含简单的循环,1)非循环也是如此.