R igraph 手册页

max_cardinality {igraph}

R 文档

最大基数搜索

描述

最大基数搜索是一种简单的顶点排序方法，可用于确定图的弦性。

用法

max_cardinality(graph)

参数

图	输入图。它可以是有向图，但边缘方向会被忽略，因为该算法是为无向图定义的。

详细信息

最大基数搜索以这样一种顺序访问顶点：每次访问具有最多已访问邻居的顶点。平局会被随机打破。

该算法为确定图是否是弦图提供了一个简单的基础，请参阅下面的“参考资料”，以及is_chordal。

值

包含两个组件的列表

alpha	数字向量。图中每个基于 1 的顶点的排名，其中排名为 1 的顶点首先被访问，排名为 2 的顶点第二个被访问，依此类推。
alpham1	数字向量。alpha 的逆。换句话说，这个向量的元素是反向最大基数搜索顺序的顶点。

作者

Gabor Csardi csardi.gabor@gmail.com

参考

Robert E Tarjan 和 Mihalis Yannakakis。（1984）。用于测试图的弦性、测试超图的无环性以及选择性地减少无环超图的简单线性时间算法。SIAM Journal of Computation 13, 566–579。

参见

is_chordal

示例

## The examples from the Tarjan-Yannakakis paper
g1 <- graph_from_literal(A-B:C:I, B-A:C:D, C-A:B:E:H, D-B:E:F,
                E-C:D:F:H, F-D:E:G, G-F:H, H-C:E:G:I,
                I-A:H)
max_cardinality(g1)
is_chordal(g1, fillin=TRUE)

g2 <- graph_from_literal(A-B:E, B-A:E:F:D, C-E:D:G, D-B:F:E:C:G,
                E-A:B:C:D:F, F-B:D:E, G-C:D:H:I, H-G:I:J,
                I-G:H:J, J-H:I)
max_cardinality(g2)
is_chordal(g2, fillin=TRUE)

---