r - 彩色图同构 : 1(red)->2(blue) vs 1(blue)->2(red)

Question

给定两个简单的图形:

library(igraph)

g <- graph.empty()
g <- g + vertices(1,2,3)
g <- g + path(1,2,3)


g1 <- g
V(g1)$color = c(1,2,2)
g2 <- g
V(g2)$color = c(2,1,1)

看起来像:

par(mfrow=c(1,2))
palette(rainbow(3))
plot(g1)
plot(g2)

为什么它们不是同构的？

graph.isomorphic.vf2(g1,g2)$iso

FALSE

最重要的是，如果这不是同构，我如何在 igraph 中检测到这种等价性?

Answer 1

(我发布了第一个 hack 作为保持问题整洁的答案。这个 hack 并不总是有效 因此是错误的，请参见下面的第二个示例。

对于有效的黑客，请参阅我的第二个答案或其他人的答案!)

我找到标签的规范排列，然后找到这个新规范图的规范着色，然后我可以使用 vf2。

我们为图形重新着色的函数是:

# Convert aaabbccdefaa -> 111223345611
canonical <- function(input){
  labels <- unique(input)
  match(input, labels)
}

现在回到正题:

g <- graph.empty()
g <- g + vertices(1,2,3)
g <- g + path(1,2,3)


g1 <- g
V(g1)$color = c(1,2,2)
g2 <- g
V(g2)$color = c(2,1,1)

# Find canonical topological labeling and then canonical coloring
g1 <- permute.vertices(g1, canonical.permutation(g1)$labeling)
g2 <- permute.vertices(g2, canonical.permutation(g2)$labeling)
V(g1)$color <- canonical(V(g1)$color)
V(g2)$color <- canonical(V(g2)$color)                     

par(mfrow=c(1,2))
palette(rainbow(3))
plot(g1)
plot(g2)

现在将被检测为同构:

#vf2 wants colors to be the same, not "up to a relabeling"
# this is why we use canonical colors
graph.isomorphic.vf2(g1, g2)$iso

TRUE

失败示例 :

对于这个例子，它不起作用:

g1 <- graph.empty()
g1 <- g1 + vertices(1,2)
g1 <- g1 + edge(1,2)
V(g1)$color = c(1,2)

g2 <- graph.empty()
g2 <- g2 + vertices(1,2)
g2 <- g2 + edge(2,1)
V(g2)$color = c(2,1)

# Find canonical topological labeling and then canonical coloring
g1 <- permute.vertices(g1, canonical.permutation(g1)$labeling)
g2 <- permute.vertices(g2, canonical.permutation(g2)$labeling)
V(g1)$color <- canonical(V(g1)$color)
V(g2)$color <- canonical(V(g2)$color)                     

par(mfrow=c(1,2))
palette(rainbow(3))
plot(g1)
plot(g2)

graph.isomorphic.vf2(g1,g2)$iso
# FALSE