CODEWITHSUNDEEP
data-structuresgraph
Sahil
Sahil

Reputation: 9488

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?

Upvotes: 5

Views: 10664

Answers (1)

stesim
stesim

Reputation: 163

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.

Upvotes: 9

Related Questions