当前位置: 动力学知识库 > 问答 > 编程问答 >

data structures - What is a Acyclic connected undirected graph?

问题描述:

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.

分享给朋友:
您可能感兴趣的文章:
随机阅读: