Biggs Theorem for Directed Cycles and Topological Invariants of Digraphs

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 #P 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 graph embeddings, discrete Morse theory and graph clustering.

中国城乡地区的生态卫生(英文)

在今后的几十年中,中国的城市污水处理领域将需要上百亿美元的投资。当前通过增加城市环境投资来改善水质的做法受到了全球专家的赞许,但是在将卫生策略与高度非逆转投资结合在一起之前,中国应该考虑替代卫生概念的可用性。许多科学家、政策顾问及实业家都高度重视生态卫生,因为从生态和经济意义上讲生态卫生比传统卫生体系更具持续性。通过分析中国的水资源现状、环保法规及水务投资等,指出实施生态卫生工程的必要性,并提出了城市生态卫生的价值链。根据中国城市生态卫生试点项目的经验,详细说明了有关的政策问题。