R igraph 手册页

is_chordal {igraph}

R 文档

图的弦性

描述

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

用法

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

参数

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

详细信息

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

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

将填充边添加到图中使其成为弦图也是正确的。

值

包含三个成员的列表

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

作者

Gabor Csardi csardi.gabor@gmail.com

参考

Robert E Tarjan and Mihalis Yannakakis. (1984). Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal of Computation 13, 566–579.

参见

max_cardinality

示例

## 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)

---