问题描述:

I was going through lecture of Minimum Spanning Tree, It says we are supposed to find connected acyclic subgraph graph in a Undirected graphs.

My question is that How can a connected undirected graph be a Acyclic, Since it is connected you can move to any vertex from any vertex.

Can anyone tell me what I am doing wrong?

网友答案:

It's really just a matter of definition. See http://en.wikipedia.org/wiki/Cycle_(graph_theory). What you seem to refer to as a cycle, is what is called a closed walk in the article: any path from a vertex to itself. As you have said yourself, using that definition, any connected undirected graph contains cycles. However, if you require that the subpath from the second to the last vertex be a simple path (hence simple cycle), i.e. one containing no repeating vertices, you end up with many connected undirected graphs which are in fact acyclic, such as trees for instance. Obviously, the path also has to contain at least 3 edges, else any (A,B,A) would be a cycle.

Consider the following graphs

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

only 2) contains simple cycles, so 1) is acyclic.

相关阅读:
Top