Connections in acyclic hypergraphs (Q762180): Difference between revisions

The property of equivalence between subgraphs without articulation points and biconnected components known in ordinary graph theory is generalized to hypergraph theory. The notion of a cyclicity in hypergraphs is understood in a nonstandard way and it is proved that a hypergraph H is acyclic if and only if for no pair of subsets \(N\subset H\), \(M\subset H\), there is an independent path. A relationship between the process of Graham reduction of acyclic hypergraphs [see \textit{M. H. Graham}, On the universal relation, Tech. Rept., Univ. of Toronto (1979)] and the process of tableau reduction [see \textit{A. V. Aho, Y. Sagiv} and \textit{J. D. Ullman}, SIAM J. Comput. 8, 218-246 (1979; Zbl 0412.68041)] is also exhibited.