Acyclic Graph — Definition, Formula & Examples
An acyclic graph is a graph that contains no cycles — meaning there is no way to start at a vertex, follow a sequence of distinct edges, and return to the starting vertex.
A graph is acyclic if and only if it contains no subgraph that is a cycle. Equivalently, for an undirected graph, is acyclic if and only if it is a forest (a disjoint union of trees). For a directed graph, is acyclic (a DAG) if and only if it admits a topological ordering of its vertices.
How It Works
To determine whether a graph is acyclic, you check if any closed walk using distinct edges exists. For an undirected graph, run a depth-first search (DFS): if you encounter an already-visited vertex that is not the parent of the current vertex, you have found a cycle. For a directed graph, perform DFS and look for back edges — an edge pointing from a vertex to one of its ancestors in the DFS tree. If no such edge exists, the graph is acyclic.
Worked Example
Problem: Determine whether the undirected graph with vertices {A, B, C, D} and edges {(A,B), (B,C), (C,D)} is acyclic.
Step 1: Count the vertices and edges. There are 4 vertices and 3 edges.
Step 2: An undirected connected graph is a tree (and therefore acyclic) if and only if it has exactly edges. Check: .
Step 3: Verify connectivity: starting from A, you can reach B, then C, then D. All vertices are reachable, so the graph is connected.
Answer: The graph is a tree with 4 vertices and 3 edges, so it is acyclic.
Why It Matters
Acyclic graphs are central to scheduling and dependency resolution. Directed acyclic graphs (DAGs) model task dependencies in project management, build systems, and compiler optimization. In machine learning, Bayesian networks are DAGs that encode probabilistic relationships among variables.
Common Mistakes
Mistake: Assuming that an acyclic directed graph cannot have multiple paths between two vertices.
Correction: A DAG can have multiple distinct paths from vertex to vertex . Acyclicity only forbids directed closed walks, not multiple open paths sharing endpoints.