R igraph 手册页

is_matching {igraph}

R 文档

图匹配

描述

图中的匹配是指选择一组两两不相邻的边，即它们没有共同的入射顶点。 如果一个匹配不是任何其他匹配的真子集，则该匹配是最大匹配。

用法

is_matching(graph, matching, types = NULL)

is_max_matching(graph, matching, types = NULL)

max_bipartite_match(
  graph,
  types = NULL,
  weights = NULL,
  eps = .Machine$double.eps
)

参数

图	输入图。 它可以是有向的，但边方向将被忽略。
匹配	潜在匹配。 一个整数向量，给出每个顶点的匹配对。 对于没有配对的顶点，请在此处提供 NA。
类型	顶点类型，如果图是二分图。 默认情况下，它们取自“type”顶点属性（如果存在）。
权重	潜在边权重。 如果图具有名为“weight”的边属性，并且此参数为 NULL，则会自动使用该边属性。 在加权匹配中，边的权重必须尽可能匹配。
eps	用于加权二分匹配算法中相等性测试的小实数。 如果两个实数之差小于 eps，则认为它们在算法中相等。 这是避免数值误差累积所必需的。 默认情况下，它设置为最小的 x，使得 1+x \ne 1 成立。 如果您在没有权重的情况下运行该算法，则会忽略此参数。

详细信息

is_matching 检查匹配向量并验证其长度是否与给定图中的顶点数匹配，其值是否介于零（含）和顶点数（含）之间，以及对于每个匹配的顶点对，图中是否存在相应的边。 对于二分图，它还会验证匹配的顶点是否位于图的不同部分。

is_max_matching 检查匹配是否为最大匹配。 当且仅当图中不存在未匹配的顶点，并且其邻居之一也未匹配时，匹配才是最大匹配。

max_bipartite_match 计算二分图中的最大匹配。 二分图中的匹配是第一类顶点到第二类顶点的部分分配，使得第一类的每个顶点最多与第二类的一个顶点匹配，反之亦然，并且匹配的顶点必须通过图中的边连接。 匹配的大小（或基数）是边的数量。 如果不存在具有更大基数的其他匹配，则匹配是最大匹配。 对于加权图，最大匹配是边的总权重在所有可能的匹配中最大的匹配。

二分图中的最大匹配是通过 push-relabel 算法找到的，该算法具有贪婪初始化，并在每 n/2 步后进行全局重标记，其中 n 是图中的顶点数。

值

is_matching 和 is_max_matching 返回一个逻辑标量。

max_bipartite_match 返回一个带有组件的列表

matching_size	匹配的大小，即连接匹配顶点的边的数量。
matching_weight	匹配的权重，如果图是加权的。 对于未加权图，这与匹配的大小相同。
匹配	匹配本身。 数字顶点 ID，如果图已命名，则为顶点名称。 未匹配的顶点用 NA 表示。

作者

Tamas Nepusz ntamas@gmail.com

示例

g <- graph_from_literal( a-b-c-d-e-f )
m1 <- c("b", "a", "d", "c", "f", "e")   # maximal matching
m2 <- c("b", "a", "d", "c", NA, NA)     # non-maximal matching
m3 <- c("b", "c", "d", "c", NA, NA)     # not a matching
is_matching(g, m1)
is_matching(g, m2)
is_matching(g, m3)
is_max_matching(g, m1)
is_max_matching(g, m2)
is_max_matching(g, m3)

V(g)$type <- c(FALSE,TRUE)
print_all(g, v=TRUE)
max_bipartite_match(g)

g2 <- graph_from_literal( a-b-c-d-e-f-g )
V(g2)$type <- rep(c(FALSE,TRUE), length.out=vcount(g2))
print_all(g2, v=TRUE)
max_bipartite_match(g2)
#' @keywords graphs

---