Abstract
Central to algorithmic graph theory are the concepts of acyclicity and strongly connected components of a graph, and the related search algorithms.
This article is about combining mathematical precision and concision in the presentation of these concepts.
Concise formulations are given for, for example, the reflexive-transitive reduction of an acyclic graph,
reachability properties of acyclic graphs and their relation to the fundamental concept of “definiteness”,
and the decomposition of paths in a graph via the identification of its strongly connected components and a pathwise homomorphic acyclic subgraph.
The relevant properties are established by precise algebraic calculation.
The combination of concision and precision is achieved by the use of point-free relation algebra capturing the algebraic properties of paths in graphs,
as opposed to the use of pointwise reasoning about paths between nodes in graphs.