5
4

4 回答 4

5

问题是NP-Complete 1。

来自Clique 问题2的减少。给定 Clique Problem - a graph 的一个实例G=(V,E)，创建一个完整的clique G'=(V,E')使得E' = {(u,v) | u != v, for each u,v in V).

最大团问题的解决方案与 G 和 G' 的最大子图问题的解决方案相同。由于 clique 问题是 NP-Hard，所以这个问题也是如此。

因此，这个问题没有已知的多项式解决方案。

如果您正在寻找一个精确的算法，您可以尝试穷举搜索方法和/或分支定界方法来解决它。抱歉这个坏消息，但至少你知道不要寻找（可能）不存在的东西（除非P=NP，当然）

编辑：问题的指数蛮力解决方案：
您可以检查所有可能的子集，并检查它是否是可行的解决方案。
伪代码：

findMCS(vertices,G1,G2,currentSubset):
  if vertices is empty: //base clause, no more candidates to check
      if isCommonSubgraph(G1,G2,currentSubset):
         return clone(currentSubset)
      else:
         return {}
  v <- vertices.pop() //take a look at the first element
  cand1 <- findMCS(vertices,G1,G2,currentSubset) //find MCS if it is NOT in the subset
  currentSubset.append(v)
  if isCommonSubgrah(G1,G2,currentSubset): //find MCS if it is in the subset
     cand2 <- findMCS(vertices,G1,G2,currentSubset)
  currentSubset.remvoe(v) //clean up environment before getting back from recursive call
  return (|cand1| > |cand2| ? cand1 : cand2) //return the maximal subset from all candidates

上面的复杂性是O(2^n)（检查所有可能的子集），并调用它：（findMCS(G1.vertices, G1, G2, [])其中[]是一个空列表）。

笔记：

  • isCommonSubgrah(G1,G2,currentSubset)是一种易于计算的方法，当且仅当currentSubset是 G1 和 G2 的公共子图时才回答 true。
  • |cand1| 和 |cand2| 是这些列表的大小。

（1）假设最大子图是一个子集U，V使得对于每个u1,u2inU (u1,u2)都在E1当且仅当(u1,u2)在E2（直观地，在两个图中共享完全相同的边的顶点的最大子集）

G=(V,E)(2) 派系问题：给定一个在 中找到最大子集U的实例，V使得对于每个u1,u2in U:u1 = u2或(u1,u2)is in E。

于 2013-02-01T10:22:17.970 回答
2

James J. McGregor提出的回溯搜索算法可用于识别两个图之间的 MCS。

于 2018-08-02T02:45:55.380 回答
0

主要问题是找到原始图中节点之间的对应关系（本质上是顶点的重新编号）。例如，如果我们在图g1中有节点p ，在图g2中有节点q ，其中p和q是等价的，我们希望将它们映射到公共子图c中的节点s。

Clique Problem 之所以如此困难的原因在于，没有任何方法可以检查不同图中的两个节点是否实际上指向同一个节点，我们必须尝试所有可能的节点对组合，并检查每对节点是否一致并表示“最好的”通信。

由于这些图中的节点代表地理位置，我们应该能够提出一个合理的距离度量，告诉我们一个图中的节点与另一个图中的任何节点相同的可能性有多大。由于两个节点的 GPS 坐标可能不相同，我们需要根据问题做一些假设。

  • 如果我们有一个数据点所在区域的地图，表示为图m ，我们可以重新编号或重命名g1和g2中的节点以对应于它们在m中最接近的等价物。
  • 距离（原始图与m之间或g1和g2中的点之间）可以是欧几里得距离或曼哈顿距离，具体取决于对您的图更有意义的距离。
  • 在决定两个节点可以相距多远并且仍然被认为是等效的时，您必须小心。太小，你不会得到任何匹配；太大，您的整个图形可能会压缩为一个节点。
  • 原始图中的两个或多个节点可能都映射到c中的同一节点。例如，如果位置数据根据节点之间的距离频繁更新。
  • 相反，如果更新频率相对于距离较低，则原始图中一对连续节点之间的边也可以映射到包含多条边的路径。因此，您必须弄清楚将这些中间节点引入公共图中是否有意义，或者将整个路径视为一条边。

对节点重新编号后，您可以使用 Jens 建议的方法来查找重新编号的图的交集。这一切都很笼统，因为我没有关于您的具体问题的很多细节，但希望这足以让您开始。

于 2013-02-04T23:25:13.077 回答
0

您甚至无法检查一个图是否是另一个图的子图，这是已知为 NP 完全的子图同构问题。因此，您无法找到最大子图，因为您无法检查同构属性（在多项式时间内）。

于 2013-02-01T13:07:21.147 回答