AcyclicGraphQ

AcyclicGraphQ[g]
yields True if the graph g is an acyclic graph and False otherwise.

DetailsDetails

  • A graph has a cycle if there is a path that starts and ends in the same vertex.

Background
Background

  • AcyclicGraphQ checks if a graph is cycle-less. A graph cycle (more properly called a circuit when the cycle is identified using an explicit path with specific endpoints) is a subset of a graph's edge set that forms a connected path such that the first node of the path corresponds to the last. A graph with no cycles is known as an acyclic graph, while a graph containing one or more cycles is called a cyclic graph. AcyclicGraphQ returns True for an acyclic graph (ignoring any self-loops) and False otherwise.
  • A simple graph containing no cycles of length three is called a triangle-free graph, and a simple graph containing no cycles of length four is called a square-free graph. Simple acyclic graphs are therefore triangle-free and square-free. They are also non-Hamiltonian (i.e. they contain no Hamiltonian cycles).
  • A connected acyclic graph is known as a tree. All trees are therefore acyclic by definition, and TreeGraphQ (which is equivalent to the logical conjunction of AcyclicGraphQ and ConnectedGraphQ) can be used to check if a graph is a tree. Trees appear extensively in computer science and in particular in the implementation of many types of algorithms and data structures, including file and folder storage on disk.
  • A not-necessarily-connected acyclic graph is known as a forest. A forest with directed edges is more commonly known as a directed acyclic graph or DAG. A DAG is therefore a graph for which both AcyclicGraphQ and DirectedGraphQ return True. DAGs are important in modeling many different kinds of information, e.g. electronic circuits, information flows, and events and tasks.
  • FindCycle can be used to find one or more cycles in graphs that are not acyclic (and returns the empty list for graphs that are).
Introduced in 2010
(8.0)
Translate this page: