连通图的基本割集多项式生成所有支撑树的一种证明

连通图必存在支撑树,且支撑树一般不唯一。如何得到连通图的所有支撑树,是图论中讨论的一个重要问题。利用基本割集对应的子图多项式生成所有支撑树是一个简单可行的方法1],现有的对这种方法的理论证明较繁琐。本文给出一种较直观的证明,说明该方法可生成全体互异的支撑树。

A proof of obtaining all the support trees of a connected graph with the polynomials of its basic cutsets

There is inevitably some support trees in a connected graph. In general, there is not only one support tree in a graph. How to obtain all the support trees of a connected graph is an important problem in graph theory. It is a simple and feasible method to generate all the support trees of a graph by making use of the polynomial of its basic cutsets. But the existing theoretical proof to this method is overelaborate and tedious. In this paper, a simpler proof to the method is given to illustrate that it can be used to obtain all the different support trees of a connected graph.