最大基数搜索

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

用法

max_cardinality(graph)

参数

graph

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

值

包含两个组件的列表

alpha

数值向量。图中每个顶点的基于 1 的排名，使得排名为 1 的顶点首先被访问，排名为 2 的顶点其次被访问，依此类推。

alpham1

数值向量。alpha 的逆。换句话说，该向量的元素是逆最大基数搜索顺序的顶点。

详细信息

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

该算法为判断图是否为弦图提供了一个简单的基础，请参见下面的参考文献和 is_chordal()。

参考文献

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

参见

is_chordal()

其他弦性相关：is_chordal()

作者

Gabor Csardi csardi.gabor@gmail.com

C 库中的相关文档

maximum_cardinality_search().

示例

## 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)
#> $alpha
#> [1] 9 4 6 8 3 5 7 2 1
#> 
#> $alpham1
#> + 9/9 vertices, named, from 6b1f78a:
#> [1] G F D B E C H I A
#> 
is_chordal(g1, fillin = TRUE)
#> $chordal
#> [1] FALSE
#> 
#> $fillin
#>  [1] 2 6 8 7 5 7 2 7 6 1 7 1
#> 
#> $newgraph
#> NULL
#> 

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)
#> $alpha
#>  [1] 10  8  9  6  7  5  4  2  3  1
#> 
#> $alpham1
#> + 10/10 vertices, named, from 7de94d9:
#>  [1] J H I G C F D B E A
#> 
is_chordal(g2, fillin = TRUE)
#> $chordal
#> [1] TRUE
#> 
#> $fillin
#> numeric(0)
#> 
#> $newgraph
#> NULL
#>