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

摘要

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