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

ON THE FOREST-INDUCING INDEPENDENCE SYSTEM OF GRAPHS

作　　者：吴举林[1] 

机构地区：[1]青岛大学数学系,邮码266071

出　　处：《高校应用数学学报（A辑）》1991年第3期420-426,共7页Applied Mathematics A Journal of Chinese Universities(Ser.A)

摘　　要：本文研究图的导出森林独立系统.在这个独立系统中,独立集是指导出子图不含圈的点子集.文中证明了图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.

关 键 词：独立系统 组合规划 图 导出森林 

分 类 号：O224[理学—运筹学与控制论]