Acyclicity

Acyclicity is the property of containing no cycles. In graph theory, a cycle is a closed path that starts and ends at the same vertex, with edges and vertices not repeated (other than the starting vertex). In directed graphs, a cycle must follow the direction of the edges; in undirected graphs, cycles are considered without regard to direction.

Undirected graphs that have no cycles are called forests; a connected acyclic undirected graph is a tree, and a graph with several components is a forest consisting of trees. Directed graphs with no directed cycles are called directed acyclic graphs (DAGs). DAGs are central to scenarios where there is a notion of precedence, such as task scheduling, data processing pipelines, and dependency resolution.

Detecting acyclicity can be done efficiently. For undirected graphs, DFS-based cycle detection determines whether a cycle exists. For directed graphs, cycle detection can use a DFS with color marking or a topological sort; if a topological ordering exists, the graph is acyclic. The typical complexity is linear in the number of vertices and edges, O(n+m).

In chemistry, acyclicity distinguishes open-chain (acyclic) compounds from cyclic structures; acyclic compounds are often contrasted with cyclic or aromatic compounds. In computer science and information systems, acyclicity constraints help prevent infinite recursion and simplify reasoning in databases, knowledge graphs, and rule-based systems.

Overall, acyclicity is a fundamental structural property with wide applications across mathematics, computer science, and chemistry.