R igraph 手册页

min_separators {igraph}

R 文档

最小尺寸顶点分隔符

描述

查找移除后将图分成更多组件的最小尺寸的顶点集合

用法

min_separators(graph)

参数

图	输入图。 它可以是有向图，但边缘方向将被忽略。

详细信息

此函数实现了 Kanevsky 算法，用于查找无向图中所有最小尺寸的顶点分隔符。 有关详细信息，请参阅下面的参考资料。

在具有 n 个顶点的完全连接输入图的特殊情况下，大小为 n-1 的所有子集都将作为结果列出。

值

数字向量列表。 每个数字向量都是一个顶点分隔符。

参考

Arkady Kanevsky: 寻找图中所有最小尺寸的分隔顶点集。 Networks 23 533–541, 1993。

JS Provan 和 DR Shier: 列出图中 (s,t) 切割的范例, Algorithmica 15, 351–372, 1996。

J. Moody 和 D. R. White。 结构凝聚力和嵌入性：社会群体的分层概念。 American Sociological Review, 68 103–127, 2003 年 2 月。

参见

is.separator

示例

# The graph from the Moody-White paper
mw <- graph.formula(1-2:3:4:5:6, 2-3:4:5:7, 3-4:6:7, 4-5:6:7,
                    5-6:7:21, 6-7, 7-8:11:14:19, 8-9:11:14, 9-10,
                    10-12:13, 11-12:14, 12-16, 13-16, 14-15, 15-16,
                    17-18:19:20, 18-20:21, 19-20:22:23, 20-21,
                    21-22:23, 22-23)

# Cohesive subgraphs
mw1 <- induced.subgraph(mw, as.character(c(1:7, 17:23)))
mw2 <- induced.subgraph(mw, as.character(7:16))
mw3 <- induced.subgraph(mw, as.character(17:23))
mw4 <- induced.subgraph(mw, as.character(c(7,8,11,14)))
mw5 <- induced.subgraph(mw, as.character(1:7))

min_separators(mw)
min_separators(mw1)
min_separators(mw2)
min_separators(mw3)
min_separators(mw4)
min_separators(mw5)

# Another example, the science camp network
camp <- graph.formula(Harry:Steve:Don:Bert - Harry:Steve:Don:Bert,
                      Pam:Brazey:Carol:Pat - Pam:Brazey:Carol:Pat,
                      Holly   - Carol:Pat:Pam:Jennie:Bill,
                      Bill    - Pauline:Michael:Lee:Holly,
                      Pauline - Bill:Jennie:Ann,
                      Jennie  - Holly:Michael:Lee:Ann:Pauline,
                      Michael - Bill:Jennie:Ann:Lee:John,
                      Ann     - Michael:Jennie:Pauline,
                      Lee     - Michael:Bill:Jennie,
                      Gery    - Pat:Steve:Russ:John,
                      Russ    - Steve:Bert:Gery:John,
                      John    - Gery:Russ:Michael)
min_separators(camp)

---