余树在图式流形拓扑分类中的应用

Application of Cotree in Topological Classification of Graphlike Manifold

图式流形是以一个无向图G为框架产生出的管形曲面M(G)。本文讨论图式流形同胚分类的计数问题,该问题可转化为图的一类2-边着色问题,提出一种新的观点,探讨图式流形的等价分类,以便推进已有的工作。图的计数理论分为两大部分:标定图的计数与非标定图的计数。由于涉及同构判定,非标定图的计数较难。本文运用图论中的向量空间,包括圈空间及割空间,建立基本的计数方法,这一方面简化了群论方法的证明,另一方面更深入地揭示出同胚分类与圈结构的关系。以余树的概念为基础,提出"余树法",并得出结论:以余树的所有边导出子图为黑边子图,构成T-等价类的一个横贯;同时,以余树中所有不同构的边导出子图为黑边子图,构成H-等价类的一个代表系。

The graphlike manifold M（G） is a tubular surface with the frame of a simple connected graph G. This paper studies the enumeration problem of homeomorphic equivalence classes of the graphlike manifold, which can be transformed into a 2-edgecoloring enumeration problem for graphs. A new approach is proposed in this paper, based on the cut space and the cycle space in the graph theory. It is well known that the enumeration theory of graphs is composed of two parts： the enumeration of labeled graphs and that of unlabelled graphs. Generally speaking, the former is easier than the latter （as the latter involves isomorphism transformation）. The enumeration formula and related results of labeled graphs are obtained by means of the group theory in the paper. The enumeration based on the cycle space and the cut space in the graph theory not only Simplifies the proofs based on the group theory, but also better reveals the relation between homeomorphic classes and the cycle-structure of graphs. Based on the definition of cotree a new kind, named ＂cotree scheme＂, is proposed. It is found tiat a transverse of T-classes can be constructed by taking all edge-induced subgraphs of the cotree as the black subgraphs. A representative system of H-classes can be constructed by taking all non-isomorphic edge-induced subgraphs of the cotree as the black subgraphs.