3

我正在编写一个函数is_iso(graph1, graph2)，它将两个图作为其输入，然后确定这两个图是否同构。

我可以假设这两个图将具有相同数量的顶点，并且顶点上使用的名称将相同。

is_iso({“A” : [“B”, “C”], “B” : [“A”], “C” : [“A”]}, {“A” : [“B”], “B” : [“A”, “C”], “C” : [“B”]})应该返回True

is_iso({“A” : [“B”, “C”], “B” : [“A”, “C”], “C” : [“A”, “B”]}, {“A” : [“B”, “C”], “B” : [“A”], “C” :[“A”]})应该返回False

def is_iso(graph1,graph2):
    for vertex in graph1:#loops through every vertex in graph1 
         seq1 += [len(graph1[vertex])]#adds the degree of each vertex to the list

    for vertex in graph2: #loops through every vertex in graph2 
        seq2 += [len(graph2[vertex])]#adds the degree of each vertex to the list

    return sorted(seq1) == sorted(seq2)

我所有的方法目前都检查度数序列是否相同，但图可以具有相同的度数序列并且不是同构的。我不确定如何从这里完成检查。我不允许导入任何库。任何帮助是极大的赞赏！

4

1 回答 1

-1

最简单的可能实现就是暴力破解它。我们需要在其中一张图中尝试所有可能的起点：

for all start points v1 in G1
    try to find an isomorphism rooted at v1 in G1 to any of v2 in G2

但是第二行是什么意思？！好吧，就像：

for each neighbour i in G1[v1]
    for each neighbour j in G2[v2]
        match(i, j)

请注意，我们还必须跟踪到目前为止我们匹配的节点，并在找到匹配项后立即返回 true。

我们可以通过使用度数序列来改进问题——显然每个图中具有相同度数的顶点必须匹配，因此仅将这些视为匹配的候选者。

当然，还有更复杂的算法，但这只有在你需要速度或有大图的情况下才真正重要。作为参考，考虑 VF2 算法：

VF2算法步骤举例

于 2017-12-14T13:19:43.163 回答