图中的匹配是指选择一组边，这些边是成对不相邻的，即它们没有共同的入射顶点。如果一个匹配不是任何其他匹配的真子集，则该匹配是最大匹配。
用法
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
)参数
- graph
输入的图。它可能是定向的，但边的方向将被忽略。
- matching
一个潜在的匹配。一个整数向量，给出每个顶点的匹配对。对于没有配对的顶点，请在此处提供
NA。- types
顶点类型，如果图是二分图。默认情况下，它们从“
type”顶点属性中获取（如果存在）。- weights
潜在的边权重。如果图有一个名为“
weight”的边属性，并且此参数为NULL，则自动使用该边属性。在加权匹配中，边的权重必须尽可能匹配。- eps
在加权二分匹配算法中用于相等性测试的一个小实数。如果两个实数之间的差小于
eps，则在该算法中认为它们相等。这是避免数值误差累积所必需的。默认情况下，它设置为最小的\(x\)，使得\(1+x \ne 1\)成立。如果你在没有权重的情况下运行算法，则此参数将被忽略。
值
is_matching()和is_max_matching()返回一个逻辑标量。
max_bipartite_match()返回一个带有以下组件的列表
- matching_size
匹配的大小，即连接匹配顶点的边的数量。
- matching_weight
匹配的权重，如果图是加权的。对于未加权图，这与匹配的大小相同。
- matching
匹配本身。数字顶点 ID，或者如果图已命名，则为顶点名称。未匹配的顶点用
NA表示。
详细信息
is_matching()检查一个匹配向量，并验证其长度是否与给定图中顶点的数量匹配，其值是否介于零（含）和顶点数量（含）之间，以及对于每个匹配的顶点对，图中是否存在相应的边。对于二分图，它还验证匹配的顶点是否位于图的不同部分。
is_max_matching()检查一个匹配是否是最大匹配。当且仅当图中没有未匹配的顶点，并且其邻居之一也是未匹配的顶点时，匹配才是最大匹配。
max_bipartite_match()计算二分图中的最大匹配。二分图中的匹配是将第一类顶点部分分配给第二类顶点，使得第一类的每个顶点最多匹配第二类的一个顶点，反之亦然，并且匹配的顶点必须由图中的边连接。匹配的大小（或基数）是边的数量。如果不存在具有更大基数的其他匹配，则匹配是最大匹配。对于加权图，最大匹配是其边的权重在所有可能的匹配中具有最大总权重的匹配。
二分图中的最大匹配是通过 push-relabel 算法找到的，该算法具有贪婪初始化，并在每\(n/2\)步之后进行全局重新标记，其中\(n\)是图中顶点的数量。
参见
其他结构属性: bfs(), component_distribution(), connect(), constraint(), coreness(), degree(), dfs(), distance_table(), edge_density(), feedback_arc_set(), feedback_vertex_set(), girth(), is_acyclic(), is_dag(), k_shortest_paths(), knn(), reciprocity(), subcomponent(), subgraph(), topo_sort(), transitivity(), unfold_tree(), which_multiple(), which_mutual()
作者
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)
#> [1] TRUE
is_matching(g, m2)
#> [1] TRUE
is_matching(g, m3)
#> [1] FALSE
is_max_matching(g, m1)
#> [1] TRUE
is_max_matching(g, m2)
#> [1] FALSE
is_max_matching(g, m3)
#> [1] FALSE
V(g)$type <- rep(c(FALSE, TRUE), 3)
print_all(g, v = TRUE)
#> IGRAPH 8e09ce2 UN-B 6 5 --
#> + attr: name (v/c), type (v/l)
#> + vertex attributes:
#> | name type
#> | [1] a FALSE
#> | [2] b TRUE
#> | [3] c FALSE
#> | [4] d TRUE
#> | [5] e FALSE
#> | [6] f TRUE
#> + edges from 8e09ce2 (vertex names):
#> [1] a--b b--c c--d d--e e--f
max_bipartite_match(g)
#> $matching_size
#> [1] 3
#>
#> $matching_weight
#> [1] 3
#>
#> $matching
#> a b c d e f
#> "b" "a" "d" "c" "f" "e"
#>
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)
#> IGRAPH 3dab7ef UN-B 7 6 --
#> + attr: name (v/c), type (v/l)
#> + vertex attributes:
#> | name type
#> | [1] a FALSE
#> | [2] b TRUE
#> | [3] c FALSE
#> | [4] d TRUE
#> | [5] e FALSE
#> | [6] f TRUE
#> | [7] g FALSE
#> + edges from 3dab7ef (vertex names):
#> [1] a--b b--c c--d d--e e--f f--g
max_bipartite_match(g2)
#> $matching_size
#> [1] 3
#>
#> $matching_weight
#> [1] 3
#>
#> $matching
#> a b c d e f g
#> "b" "a" "d" "c" "f" "e" NA
#>
#' @keywords graphs