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

This comprehensive paper, with 47 pages, tries to establish a precise and concise foundation, of an algebraic nature, so that solid proofs can be made to establish correctness of graph algorithms, particularly in the areas of acyclicity and strongly connected components, through ``point-free'' algebraic systems in terms of the union, intersection, composition, and converse operations. After an introductory section, Sections~2, 3, and 4 revisit such notions as lattice, regular algebra, and converse structure; and Sections~5, 6, and 7 introduce several miscellaneous notions including left and right domain operators, ``all-or-nothing'' axioms, and various function-related notions such as functionality, injectivity, surjectivity, and heterogeneous relations. Section~8 reviews some general properties of partitions and equivalence relations. A total of 75 results, including equations, lemmas, corollaries, and theorems, appear in this collection of seven preparatory sections. The authors then turn to the problem of acyclicity in Section~9, starting by defining a graph \(G\) as a homogeneous ``edge'' relation of type \((\mathsf{Node}, \mathsf{Node})\), where \(\mathsf{Node}\) is a finite set. A usual definition would be that \(V\) is a collection of vertices, and \(E\) a collection of edges, \(E=\{(u, v):u, v \in V \}.\) After 12 pages, and 43 results, it ends up with an algebraic proof of the following result: Theorem~115. Suppose \(G\) is a finite graph. Then that there is a topological ordering of \(G\) equivales \(G\) is acyclic. It is clear that the existence of a topological sorting sequence in a finite graph guarantees the acyclicity of such a graph. For the other direction, of a constructive nature, one of the simple topological sorting algorithms [\textit{M. A. Weiss}, Data structures and algorithm analysis in C. Redwood City, CA: The Benjamin/Cummings Publishing Co., Inc. (1993; Zbl 0781.68015), Section~9.2] goes like this: With an initial label of 0, it repeatedly looks for a vertex \(v,\) with its in-degree being 0, labels \(v\) with an updated value, then decrements the in-degree by 1 for all the vertices adjacent to \(v\). It terminates when all the vertices are labeled. To prove its correctness, an acyclic graph necessarily has a vertex with its in-degree being 0; then an inductive approach, both precise and concise, would establish, with this algorithm, if there is a path from \(u\) to \(v,\) \(u\) must be labeled before \(v\). Section~10 covers the strong connected components, starting with a definition of a component, defined through the notion of equivalence class, then explores its properties. This section, consisting of 14 pages with 28 mathematical results, ends with Theorem~143, which is supposed to say that ``solving path problems can be decomposed into solving the problems for each individual strongly connected component and then combining the results using a topological search of an acyclic graph.'' It is commented, in the concluding section, that ``We haven't even begun to discuss algorithms for computing strongly connected components: we have only laid the foundations!'' This paper concludes in Section~11, where it states that the ever-growing dependency of our modern society on computer software demands us to design software based on techniques that allow a precise formulation and calculation of desired properties. To meet such challenges, ``it is vital that we learn how to choose and apply algebraic calculi that are tuned to the task in hand in a way that combines concision with precision.'' This paper is well written and organized, and it is also very technical. Due to the limited background of this reviewer in formal algebraic theory, this reviewer cannot judge the correctness of the results as contained in this paper. Nevertheless, this reviewer does agree with the central point raised by the authors on the importance of establishing correctness of various algorithms, considering the critical roles they play in our society and lives. On the other hand, people might have different opinions as what properties of those algorithmic notions and procedures should be exploited, how should we do so, as well as how much detail should we go through with our students, given the limited time that we could afford to devote to those topics, and the mathematical background of our students. This last issue is worth pointing out since at least two mainstream textbooks [\textit{A. V. Aho} et al., Data structures and algorithms. Reading, Massachusetts, etc.: Addison-Wesley Publishing Company (1983; Zbl 0487.68005); \textit{T. H. Cormen} et al., Introduction to algorithms. Cambridge, MA: MIT Press.; New York, NY: McGraw-Hill (1990; Zbl 1158.68538)] on algorithm studies are mentioned, and commented, in this paper.