答网友顶点覆盖的子句消去法

姜咏江

图论中的顶点覆盖问题是说，给定一个N个点M条边的无向图G（点的编号从1至N），问是否存在一个不超过K个点的集合S，使得G中的每条边都至少有一个点在集合S中。这实际上是求最小顶点覆盖问题。

本文介绍如何用子句消去法来来求解图论中的顶点覆盖问题。

1.      图的0和1句表示

将图中本顶点用1表示，与其关联顶点用0表示，就是图的0和1子句表示法。图1的0和1表达形式如表1所示。因为这个求解方法近似于本人发明的子句消去法，所以也将表1中的每一行叫做子句。

图1  哈密顿图

表1  哈密顿图子句表示

2.      顶点覆盖的子句消去法

用0和1表示的图，要确定最小顶点覆盖的基本规则是：不分图，叶单枝优先，否则选择得到多叶单枝优先，得不到单枝，关联度由高到低。

表2  哈密顿图顶点覆盖

最小顶点覆盖集为｛x1,x3,x4,x6,x8,x10,x11,x13,x15,x17,x18,x20｝。

2017-1-23