We generalize Biggs Theorem to the case of directed cycles of multi-digraphs allowing to compute the dimension of the directed cycle space independently of the graph representation with linear runtime complexity. By c...We generalize Biggs Theorem to the case of directed cycles of multi-digraphs allowing to compute the dimension of the directed cycle space independently of the graph representation with linear runtime complexity. By considering two-dimensional CW complex of elementary cycles and deriving formulas for the Betti numbers of the associated cellular homology groups, we extend the list of representation independent topological inavariants measuring the graph structure. We prove the computation of the 2nd Betti number to be sharp #<em>P</em> hard in general and present specific representation invariant sub-fillings yielding efficiently computable homology groups. Finally, we suggest how to use the provided structural measures to shed new light on graph theoretical problems as <em>graph embeddings</em>, <em>discrete Morse theory </em>and<em> graph clustering</em>.展开更多
Forman has developed a version of discrete Morse theory that can be understood in terms of arrow patterns on a(simplicial,polyhedral or cellular)complex without closed orbits,where each cell may either have no arrows,...Forman has developed a version of discrete Morse theory that can be understood in terms of arrow patterns on a(simplicial,polyhedral or cellular)complex without closed orbits,where each cell may either have no arrows,receive a single arrow from one of its facets,or conversely,send a single arrow into a cell of which it is a facet.By following arrows,one can then construct a natural Floer-type boundary operator.Here,we develop such a construction for arrow patterns where each cell may support several outgoing or incoming arrows(but not both),again in the absence of closed orbits.Our main technical achievement is the construction of a boundary operator that squares to 0 and therefore recovers the homology of the underlying complex.展开更多
文摘We generalize Biggs Theorem to the case of directed cycles of multi-digraphs allowing to compute the dimension of the directed cycle space independently of the graph representation with linear runtime complexity. By considering two-dimensional CW complex of elementary cycles and deriving formulas for the Betti numbers of the associated cellular homology groups, we extend the list of representation independent topological inavariants measuring the graph structure. We prove the computation of the 2nd Betti number to be sharp #<em>P</em> hard in general and present specific representation invariant sub-fillings yielding efficiently computable homology groups. Finally, we suggest how to use the provided structural measures to shed new light on graph theoretical problems as <em>graph embeddings</em>, <em>discrete Morse theory </em>and<em> graph clustering</em>.
基金funding provided by Max Planck Societysupported by a stipend from the InternationalMax Planck Research School(IMPRS)“Mathematics in the Sciences.”。
文摘Forman has developed a version of discrete Morse theory that can be understood in terms of arrow patterns on a(simplicial,polyhedral or cellular)complex without closed orbits,where each cell may either have no arrows,receive a single arrow from one of its facets,or conversely,send a single arrow into a cell of which it is a facet.By following arrows,one can then construct a natural Floer-type boundary operator.Here,we develop such a construction for arrow patterns where each cell may support several outgoing or incoming arrows(but not both),again in the absence of closed orbits.Our main technical achievement is the construction of a boundary operator that squares to 0 and therefore recovers the homology of the underlying complex.
