如何找到两个图的最大公共子图？ [英] How can I find Maximum Common Subgraph of two graphs?

问题描述

我需要一个寻找图算法的帮助

Hi i need a help in finding a graph algorithm

我正在研究与距离函数有关的以下方程式

im working on the following equation related to distance functions

d (g1, g2)   = 1-       │mcs(g1,g2) │  /
             │g1│+│g2│-│mcs (g1, g2) │

其中

• d（g1，g2）：是基于最大公共子图
  的距离函数。


• g1，g2 是两个图。


• mcs（g1，g2）：是两个图g1，g2
  的最大公共子图，其中mcs是两个主题图中都包含的最大图（通过某种程度的节点和边数
  计）。


• │g1│：共同诱导子图g1的基数


• │g2│：常见诱导子图g2的基数

• d (g1,g2) : is a distance function based on maximum common sub graph .
• g1, g2 are two graphs .
• mcs (g1,g2): is the maximum common sub graph of two graphs g1,g2 where mcs is the largest graph (by some measure involving the number of nodes and edges )contained in both subject graphs .
• │g1│: Cardinality of the common induced sub graph g1
• │g2│: Cardinality of the common induced sub graph g2

我的问题：我计算MCS？

我在互联网上进行搜索，但是大多数算法都很复杂，任何人都知道从哪里可以找到一个简单的算法来在Matlab中对该方程进行编程。

My Question: How can I calculate MCS?
I searched the internet but most of the algorithms are complicated anyone know from where i can get a simple algorithm to program this equation in matlab.

推荐答案

问题是 NP完成 ¹ 。

从群体问题 ² 。给定一个集团问题实例-图形 G =（V，E），创建完整的斜体 G'=（V，E'）这样， E'= {（u，v）| u！= v，对于V中的每个u，v）。

The reduction from the Clique Problem². Given an instance of Clique Problem - a graph G=(V,E), create a complete clique G'=(V,E') such that E' = {(u,v) | u != v, for each u,v in V).

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

The solution to the maximal clique problem is the same solution for the maximal subgraph problem for G and G'. Since clique problem is NP-Hard, so does this problem.

因此，没有已知的多项式解。

如果您正在寻找确切的算法，则可以尝试详尽搜索方法和/或分支机构&绑定方法来解决。不好意思，抱歉，但至少您知道不要查找（可能）不存在的东西（除非 P = NP ，当然）

If you are looking for an exact algorithm, you could try exhaustive search approach and/or a branch & bound approach to solve it. Sorry for the bad news, but at least you know not to look for something that (probably) doesn't exist (unless P=NP, of course)

编辑：指数蛮力问题的解决方案：

您只需检查所有可能的子集，然后检查它是否可行。

伪代码：

exponential brute force solution to the problem:
You can just check all possible subsets, and check if it is a feasible solution.
Pseudo Code:

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，[]）（其中 [] 是一个空列表）。

Complexity of the above is O(2^n) (checking all possible subsets), and invoke it with: findMCS(G1.vertices, G1, G2, []) (where [] is an empty list).

注意：

• isCommonSubgrah（G1，G2，currentSubset）是一种易于计算的方法，仅当且仅当 currentSubset 是G1和G2的公共子图时，答案为true。


• | cand1 |和| cand2 |是这些列表的大小。

• isCommonSubgrah(G1,G2,currentSubset) is an easy to calculate method that just answers true if and only if currentSubset is a common subgraph of G1 and G2.
• |cand1| and |cand2| is the sizes of these lists.

（1）假设最大子图为 V 中的子集 U ，这样对于每个 u1，u2 在 U （u1，u2）中是在 E1 中当且仅当（u1，u2）在 E2 中（直觉上，共享该顶点的最大顶点子集）

(1)Assuming that Maximum sub graph is a subset U in V such that for each u1,u2 in U (u1,u2) is in E1 if and only if (u1,u2) is in E2 (intuitively, a maximal subset of the vertices that share the exact same edges in the two graphs)

（2）两个问题：给定 G =（V，E）在 V 中找到最大子集 U ，这样对于每个 u1，u2 U 中的code>： u1 = u2 或（u1，u2）在 E 中。

(2) Clique Problem: Given an instance of G=(V,E) find maximal subset U in V such that for each u1,u2 in U : u1 = u2 or (u1,u2) is in E.

这篇关于如何找到两个图的最大公共子图？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！