algorithm - 模糊图匹配

Question

我有一个模糊图G=(V, E)，其中V是顶点E集，是边集。每个顶点都是一个模糊顶点，这意味着它有一个属性和一个关联函数（以某种方式存储在顶点中）。每条边都是一条模糊边，这意味着它有一个属性和一个关联函数（以某种方式存储在边中）。通过这样做，G就边和顶点而言，是一个模糊图。

给定Gand G2，另一个具有不同（或相等）数量的边和/或顶点的模糊图，我需要以模糊的方式比较两个图。我想检查是否G2是子图或G（反之亦然）。有什么算法可以解决这个问题吗？

标签： algorithmgraphfuzzysubgraph

Answer 1

首先，要比较两个图，您应该解决子图同构问题，它可能是多项式的，也可能不是。

但是你没有图表，你有模糊图表。我不知道是否存在显式算法，但我会尝试两种方法：

1. 如果您可以将成员资格定义为概率P{is member}=1，您可以首先假设通常的图(

2. 您可以使用Monte Carlo 方法定义模糊图之间的度量。作为一个例子，简单地走这两个图，当一步产生一些差异时停止。步数是一个度量。运行n时间并获得max, avg, ... 最终算法很大程度上取决于您的隶属函数是否具有状态，您知道“最大相似度”等等...

前一种方法应该是快速和可靠的，但如果你找不到合适的方程，你什么都没有。后一种方法看起来更可行，但效率要低得多。

无论如何，已定义指标的可用性是主观的（如果您不解释要求，任何指标都可能是有效的）。