R igraph 手册页

ivs {igraph}

R 文档

独立顶点集

描述

如果顶点集中任意两个顶点之间没有边，则该顶点集称为独立集。这些函数查找无向图中的独立顶点集

用法

ivs(graph, min = NULL, max = NULL)

参数

图	输入图，有向图被视为无向图，环边和多重边被忽略。
min	数值常量，用于查找的独立顶点集的最小大小的限制。NULL 表示没有限制。
max	数值常量，用于查找的独立顶点集的最大大小的限制。NULL 表示没有限制。

详细信息

ivs 查找网络中的所有独立顶点集，并遵守 min 和 max 参数中给出的大小限制。

largest_ivs 查找图中的最大独立顶点集。 如果不存在具有更多顶点的独立顶点集，则独立顶点集是最大的。

maximal_ivs 查找图中的极大独立顶点集。如果无法扩展到更大的独立顶点集，则独立顶点集是极大的。最大的独立顶点集是极大的，但反之并不总是如此。

independece.number 计算最大独立顶点集的大小。

这些函数使用 Tsukiyama 等人描述的算法，请参阅下面的参考文献。

值

ivs, largest_ivs 和 maximal_ivs 返回一个包含数值顶点 ID 的列表，每个列表元素是一个独立的顶点集。

ivs_size 返回一个整数常量。

作者

Tamas Nepusz ntamas@gmail.com 从 Keith Briggs 的 Very Nauty 图库 (http://keithbriggs.info/) 移植了它，Gabor Csardi csardi.gabor@gmail.com 编写了 R 接口和本手册页。

参考

S. Tsukiyama, M. Ide, H. Ariyoshi and I. Shirawaka. A new algorithm for generating all the maximal independent sets. SIAM J Computing, 6:505–517, 1977.

参见

cliques

示例

# Do not run, takes a couple of seconds
## Not run: 

# A quite dense graph
set.seed(42)
g <- sample_gnp(100, 0.9)
ivs_size(g)
ivs(g, min=ivs_size(g))
largest_ivs(g)
# Empty graph
induced_subgraph(g, largest_ivs(g)[[1]])

length(maximal_ivs(g))

## End(Not run)

---