图形max_bipartite_match函数上的错误匹配输出？

Question

我很难理解max_bipartite_match函数的输出，输出似乎并不对应于匹配，而从输出中可以清楚地看出，算法实际上已经找到了最大匹配。

我试着阅读文档，但它对我没有帮助：

下面是一个示例：

Network

和代码：

library(igraph)
bp <- make_bipartite_graph(types=c(rep(TRUE,3),rep(FALSE,3)),edges = c(1, 4, 1, 5, 1, 6, 2, 4,
                      3, 5, 3, 6), directed = FALSE)
set.seed(512)
E(bp)$weight <- runif(length(igraph::E(bp)), 0, 1)
plot(bp,layout=layout_as_bipartite(bp),edge.label=sprintf("%0.2f",E(bp)$weight))
max_bipartite_match(bp,eps=0.00001)

输出为：

$matching_size
[1] 3

$matching_weight
[1] 2.032942

$matching
[1] 6 4 5 2 3 1

然而，6,4,5都在相同的分量中，因此匹配并不代表边缘序列。我尝试了一些其他的解释(6-2 odes不存在，也不存在4-3)，我仍然不能理解输出。

对我来说，作为边缘序列的最大匹配应该是2-4 5-3 2-6，很明显算法找到了它，因为matching_weight是2.03，这是一致的。

对我来说，它甚至看起来像是一个bug。

有谁能解释一下吗？

谢谢，亚历克西斯

Answer 1

对于未来的用户，我是这样想的：

实际上，匹配的每个元素都对应于该位置对应的顶点和该位置的匹配元素之间的一条边。在我的示例中，与6 4 5 2 3 1对应的匹配为：

1 2 3 4 5 6
| | | | | |
6 4 5 2 3 1

这很令人困惑，因为每条边都列出了两次，因为我的图是无向图，但它是正确的。

我在1000个随机图上测试了这个假设，它每次都有效。