顶点覆盖的子句消去法

姜咏江

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

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

1.       图的0和1子句表示

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

图1  

表1  图1的子句表示

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

用0和1表示的图，要确定最小顶点覆盖的基本规则是：从关联边最多的顶点选择消去边和顶点，连接单边的顶点优先。

表1中就可以看出顶点的关联度和连接的单边数量。x1、x2、x3的关联度都是3，但x1有2个单边，x3有一个单边，所以先选x1连同边一起消去（消去x1＝1所在行和列），得到表2。

表2

 表2中关联度最高的是x3，因而选择x3消去，得到表3。

表3

 表3中关联度最高的是x5，因而选择x5消去，得到表4。

表4

 表4中剩余的都是孤立点，说明不在表4中的那些顶点集合｛x1,x3,x5｝为最小顶点覆盖集。

3.       讨论

看来用0和1表示图来计算顶点覆盖十分简单。而且将顶点较高关联度逐一消去，能够轻易看出消去的是最少的顶点集合。

有兴趣的朋友，不妨任意画出一个图，来试试这种求最小顶点覆盖的方法。

2017-1-7