Components and acyclicity of graphs. An exercise in combining precision with concision

Backhouse, Roland; Doornbos, Henk; Glück, Roland; van der Woude, Jaap

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.

Citation

Backhouse, R., Doornbos, H., Glück, R., & van der Woude, J. (2022). Components and acyclicity of graphs. An exercise in combining precision with concision. Journal of Logical and Algebraic Methods in Programming, 124, Article 100730. https://doi.org/10.1016/j.jlamp.2021.100730

• Journal Article Type: Article
• Acceptance Date: Oct 1, 2021
• Online Publication Date: Oct 13, 2021
• Publication Date: Jan 1, 2022
• Deposit Date: Oct 22, 2021
• Publicly Available Date: Oct 22, 2021
• Journal: Journal of Logical and Algebraic Methods in Programming
• Print ISSN: 2352-2208
• Electronic ISSN: 2352-2208
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 124
• Article Number: 100730
• DOI: https://doi.org/10.1016/j.jlamp.2021.100730
• Keywords: Software; Theoretical Computer Science; Computational Theory and Mathematics; Logic
• Public URL: https://nottingham-repository.worktribe.com/output/6508281
• Publisher URL: https://www.sciencedirect.com/science/article/pii/S2352220821000936