gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-04 01:03:55 25 4
gpt4 key购买 nike

给定两个简单的图形:

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)

graphs

为什么它们不是同构的?
graph.isomorphic.vf2(g1,g2)$iso

FALSE



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

最佳答案

(我发布了第一个 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)

iso

现在将被检测为同构:
#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

fail

关于r - 彩色图同构 : 1(red)->2(blue) vs 1(blue)->2(red),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29587032/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com