algorithm - 查找图的集团封面

假设有一个黑箱（/一个算法）给了我一个图的团。有没有办法从中找到那个集团的掩护？
图中给出了一个直观的想法我在找黑匣子的零件。如需进一步澄清，请随时联系。
我有一个想法，通过删除团的边缘来更新图形。我不知道会有多好。期待任何其他想法。
另外，如果能给我提供近似团覆盖算法的好参考，这将是非常有帮助的。

最佳答案

http://mathworld.wolfram.com/CliqueCoveringNumber.html
删除边对您没有帮助，因为新的图形可能缺少一个用于解决封面问题的组。

    B
  / | \
A   |  D
  \ | /
    C

你有2个最大集团，ABC和BCD，如果你从ABC开始，移除它的边AB和BC，你的算法就不能找到BCD集团。
在尝试计算团盖数之前，你需要图的所有最大团。

AllCliques = GetAllCliques()
MaximalCliques = AllCliques
For Each ckA in MaximalCliques
  For Each ckB in MaximalCliques.Excluding(ckA)
    If all vertices in ckA are in ckB Then MaximalCliques.Remove(ckA)
    If all vertices in ckB are in ckA Then MaximalCliques.Remove(ckB)
Return MaximalCliques

然后通过排列和检验来寻找所有最大团的团覆盖数的幼稚方法。

MinCover = MaximalCliques.Count
For Each ckList in Permute(MaximalCliques)
  Cover = 0
  TestSet = Graph.Vertices
  For Each ck in ckList
    TestSet.Remove(ck.Vertices)
    Cover = Cover + 1
    If TestSet.Count = 0 Then Break
  If Cover < MinCover Then MinCover = Cover
Return MinCover