图的弦性 — is_chordal • igraph 网络分析库

如果图的每个四个或更多节点的环都有一个弦，即连接环中两个不相邻节点的边，则该图是弦图（或三角图）。一个等效的定义是任何无弦环最多有三个节点。

用法

is_chordal(
  graph,
  alpha = NULL,
  alpham1 = NULL,
  fillin = FALSE,
  newgraph = FALSE
)

参数

graph: 输入图。它可以是有向图，但边的方向将被忽略，因为该算法是为无向图定义的。
alpha: 数值向量，顶点的最大基数排序。如果为NULL，则会自动通过调用max_cardinality()来计算，或者如果给定了alpham1，则从alpham1计算。
alpham1: 数值向量，alpha的逆。如果为NULL，则会自动通过调用max_cardinality()来计算，或者从alpha计算。
fillin: 逻辑标量，是否计算填充边。
newgraph: 逻辑标量，是否计算三角图。

值

具有三个成员的列表

chordal: 逻辑标量，当且仅当输入图是弦图时，它为TRUE。
fillin: 如果被请求，则为数值向量，给出填充边。否则为NULL。
newgraph: 如果被请求，则为三角图，一个igraph对象。否则为NULL。

详细信息

图的弦性通过首先对其执行最大基数搜索来确定（如果alpha和alpham1参数为NULL），然后计算填充边的集合。

当且仅当填充边的集合为空时，图才是弦图。

将填充边添加到图中也会使其成为弦图。

参考文献

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

参见

max_cardinality()

其他弦性相关：max_cardinality()

作者

Gabor Csardi csardi.gabor@gmail.com

示例


## 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 fc5d778:
#> [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 68a85b3:
#>  [1] J H I G C F D B E A
#> 
is_chordal(g2, fillin = TRUE)
#> $chordal
#> [1] TRUE
#> 
#> $fillin
#> numeric(0)
#> 
#> $newgraph
#> NULL
#>