关于图的导出森林独立系统

ON THE FOREST-INDUCING INDEPENDENCE SYSTEM OF GRAPHS

本文研究图的导出森林独立系统.在这个独立系统中,独立集是指导出子图不含圈的点子集.文中证明了图G的导出森林独立系统是拟阵当且仅当G是块森林.文中同时给出了在强弦图上求最大导出森林的多项式算法.

In this paper we study the forest-inducing independence system of graphs. In this independence system, the independent sets are the subsets of vertices inducing a forest. It is shown that the forset-inducing independence system of a graph G is a matroid if and only if G is a block-forest. A polynomial algorithm to find the maximum induced forest of a strongly chordal graph is given.