Bron_Kerbosch算法.doc

Bron_Kerbosch算法 /wiki/Bron%E2%80%93Kerbosch_algorithm#cite_note-1l 朴素的Bron_Kerbosch算法最大团问题是在图中找到最大的完全子图的问题，是一个经典的NP完全问题。无向图的最大团确定搜索算法中有一个Bron_Kerbosch算法。该算法在1973年提出 http:/www.dcs.gla.ac.uk/pat/jchoco/clique/enumeration/papers/SMJ0000011.pdf，后有很多变种 http:/www.dcs.gla.ac.uk/pat/jchoco/clique/enumeration/report.pdf，尝试加入一些策略加快搜索速度。朴素的Bron_Kerbosch算法如图1所示。图1：朴素的Bron_Kerbosch算法在该算法中有四个集合：。其中：目前已经在团中的结点的集合(temporary result)：可能在团中的结点的集合(possible candidates)：不被考虑的结点的集合(excluded set，在朴素的Bron_Kerbosch算法表现为：包含该结点的最大团已经被搜索)：结点的所有直接邻居(有边直接相连)结点的集合。其中，。该算法发的文字描述如下：从中选出一个结点找包含的最大团。将放入集合中，并将不在的结点从和中移出。从剩下的中再选出一个结点，重复上述操作。直到成为空集。此时，若也为空，则是新的最大团(如果不为空，则说明是已经找到的最大团的一个子集)。然后，回溯到上一个选择的结点，并将集合也恢复到原来的状态，同时，将本次选择的结点从中移出，加入，从中选出下一个结点重复上述操作。如果为空集，则返回到上一级。 如图3所示，为图2所示的图的Bron_Kerbosch算法的部分步骤。图2：有5个团的图例(四条边和一个三角形)图3：图2所示图的Bron_Kerbosch算法的部分步骤l 带轴的Bron_Kerbosch算法朴素的Bron_Kerbosch算法在有很多非最大团的情况下，效率不是很好。因为，该算法会遍历所有的团。该算法的其中一个变种是加入轴(pivot)，基本思想是选择一个结点轴，最大团要么包含，要么包含的非直接邻居。算法的伪代码如图4所示，以图2为例的执行步骤如图5所示。图4：使用轴的Bron_Kerbosch算法图5：图2所示图的带轴Bron_Kerbosch算法的实现步骤带轴的Bron_Kerbosch算法最理想的情况是选择图的顶点覆盖问题的解，作为候选集。顶点覆盖(vertex cover)问题是，在图中找一个最小的结点集，使得图中的每条边都至少有一个端点在该结点集中。如图9所示，1,3,5为该图的顶点覆盖问题的解。虽然使用顶点覆盖问题的解能提高该算法的效率，但是，顶点覆盖问题本身是一个NP问题。图9：顶点覆盖问题的例子l 有序的Bron_Kerbosch算法在图论中，度(degree)或阶(valency)是指一个图中连接在某个结点上的边的数目。图的最大/最小度数是指图中度数最大/最小的结点的度数。在正则图(regular graph)中，所有结点的度数都相同。诱导子图(induced subgraph)是一个图的一些结点和连接这些结点的所有边构成的一个新图。形式化的定义方式为：给定图诱导子图为，并且，当且仅当 ，。其中。退化 /wiki/Degeneracy_(graph_theory)#cite_note-bh03-1(degeneracy):如果图的结点存在一种序列(degeneracy ordering)，使得每个结点和它所有前驱形成的诱导子图中，该结点度不超过，则称该图为-退化图。图6为2-退化图的例子。图6:2-退化图如果算法在从集合中选结点时，按照退化序(degeneracy ordering)选择， 能够减少算法调用的次数，从而提高效率。其中，退化序能在线性复杂度内计算完成。但，该变种(严格来说，这种变化并没有改变算法，只是在算法执行的时候选择能加快速度的序列)会有退化的时候。图8为图2所示图的退化顺序。图7：有序、带轴的Bron_Kerbosch算法图8：有序Bron_Kerbosch算法在图2所示图中的退化序列由实验