Given an undirected graph with n nodes and k edges , find the minimum number of edges that have to be removed in order to attain an acyclic graph. I initially thought that the minimum number of edges that need to be removed is the number of cycles that exist in the graph since each cycle needs one edge to be removed.
[Math] Minimum number of edges that have to be removed in a graph to make it acyclic
algorithmscomputer sciencegraph theory
Related Solutions
We give a simple algorithm that orients the edges of $G$ to get a DAG. Number the vertices $n$ vertices of $G$ arbitrarily $\{v_1,\ldots, v_n\}$. If $v_i$ and $v_j$ are adjacent in $G$, then direct the edge $v_iv_j$ as follows: If $i < j$ direct $v_iv_j$ towards $j$; otherwise direct the edge towards $i$.
The resulting orientation of the edges has no directed cycles. Indeed, for each $i$, every vertex reachable from $v_i$ is of the form $v_k; k > i$.
I think I am probably just misinterpreting all of these definitions? Can we define the terms "acyclic", "cyclic", "undirected cycle" and "directed cycle" in some other way to help clarify what they mean?
Yes, many graph theory textbooks do a better job than yours did. The best way is to start with a firm understanding of (undirected) graphs and move from there to digraphs. So let's start over and eliminate all the useless words.
A cycle is a walk in a graph where the origin and internal vertices are all distinct and the terminus is the same as the origin. A graph is acyclic if it does not contain a cycle.
With that said, a directed graph is one where the edges are all endowed with a direction. Associated with every digraph is its underlying graph which is an undirected graph with the same vertex and edge set but "ignoring" the direction. So when we say that a directed graph is or isn't acyclic, we are implicitly referring to whether the underlying graph is acyclic. But the added structure gives us the notion of a directed cycle, which is a directed walk in the digraph (i.e. one the follows all of the directions) where again the origin and internal vertices are distinct and the terminus and the origin are the same.
The only wrinkle in all of this is that the meddling computer scientists have forced the term directed acyclic graph (DAG) on us. This refers to a digraph that contains no directed cycle (although its underlying graph may contain a cycle). It's not a good name, but there's no putting that toothpaste back in the tube so we have to deal with its existence.
Coming back to the two introductory questions you asked:
By Definition 1, can a graph be acyclic and yet contain a directed cycle?
No. If a digraph contains a directed cycle, then that same walk in the underlying graph of the digraph would be a cycle. The converse is possible -- a digraph can be cyclic but not contain a directed cycle. The graph you pasted into your question is an example of that.
Unless Definition 1 is implying that all directed cycles can be treated as undirected cycles, but undirected cycles cannot be treated as directed cycles?
Yes, as I just noted every directed cycle would be a cycle in the underlying graph. And a cycle in the underlying graph would be a directed cycle in the digraph iff its edges are all following the direction of the walk.
Definition 2 seems to reinforce this idea, by suggesting that an undirected cycle can simply ignore edge directions.
Yes. A cycle is a feature of the underlying graph, so the direction of the edges in the digraph is not considered.
The good news is that all of this is essentially invisible once you have these definitions straight in your mind. Does this clear it up?
Best Answer
Basically, we combine these observations:
If the connected components in the original graph have $c_1,c_2,\ldots,c_k$ vertices, then the any union of spanning trees for each component has exactly $$(c_1-1)+(c_2-1)+\cdots+(c_k-1) = (c_1+\cdots+c_k)-k$$ edges. The number of edges we need to delete is thus $$|E(G)|-(c_1+\cdots+c_k)+k.$$