Acyclic graph

As explained in Graph Neural Networks in Action

An acyclic graph is a graph containing no cycle that returns to a starting node without backtracking.

An acyclic graph contains no cycle: starting at any node, you cannot return to it by following edges without backtracking. Its structure often resembles a tree or a non-looping path. A directed acyclic graph (DAG) is the directed form, with one-way edges and no cycles, useful for causal structures, workflows, and dependency chains. section 1.2.2

Distinguish the related forms:

• A cyclic graph permits a path that returns to its starting node without retracing edges. section 1.2.2
• An acyclic graph may be undirected or directed, provided no cycle is possible. section 1.2.2
• A DAG restricts the graph to directed edges, representing relationships that cannot flow back to their starting point. section 1.2.2

Figure 1.4 A cyclic graph (left), an acyclic graph (right), and a DAG (bottom). In the cyclic graph, the cycle is shown by the arrows (directed edges) connecting nodes A-E-D-C-B-A. Note that two nodes, G and F are part of the graph, but not part of its defining cycle. The acyclic graph is composed of undirected edges, and no cycle is possible. In the DAG, all directed edges flow in one direction, from A to F.

Compare a cyclic graph, an undirected acyclic graph, and a DAG; the diagrams make the absence of cycles and direction constraints visible. section 1.2.2

How Graph Neural Networks in Action covers it

How deep it goes

Defines cycles, contrasts directed and undirected forms, and stops short of implementation or cycle-detection procedures.

Examples

Uses a visual comparison of a cyclic graph, an undirected acyclic graph, and a DAG.

What you can do after

Evaluate whether a graph permits cycles and recognize when directed one-way structure forms a DAG.

How it connects

Connects acyclic graphs with cyclic graphs, directed acyclic graphs, causal analysis, workflow processes, and dependency chains.

liveBookmanning.com

Read Graph Neural Networks in Action on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Optimization Algorithms: AI techniques for design, planning, and control problemsAn acyclic graph is a graph that contains no cycles.
• 

  liveBookmanning.com
  Grokking Data StructuresAn acyclic graph is a graph that contains no cycles.

Compare how 3 books explain acyclic graph →

Related concepts

• graphkind of · A graph is a mathematical structure consisting of vertices connected by edges that represent relationships or connections.
• treeincludes · A tree is a connected, acyclic structure of nodes, commonly organized hierarchically through parent-child relationships and optionally around a designated root.
• directed acyclic graphincludes · A directed acyclic graph is a graph with directed edges and no directed cycles.

This explainer was generated by Manning's knowledge graph from the text of Graph Neural Networks in Action. The section links point to the parts of the book it draws on.