python - 从消除排序和弦图中获得树分解

Question

在给定图的消元排序和弦化的情况下，我需要一个很好的图树分解。

我的想法是获取图中的所有派系(我可以做到)并从根开始构建一个二叉树，并根据派系共有的顶点数生成 child (即派系)。我想这样做直到所有派系都被使用，因此，我有一棵树。问题是团可能有超过 2 个顶点，所以我不能递归地运行每个顶点，因为树可能不是二进制的。

http://en.wikipedia.org/wiki/Tree_decomposition http://en.wikipedia.org/wiki/Chordal_graph

我正在用 python 进行实现，目前我有弦图、所有派系的列表和消除顺序。想法和/或代码非常受欢迎!

Answer 1

构建弦图的非良好(一般)树分解:找到一个完美的消除排序，枚举最大团(候选是一个顶点和排序中出现在它之后的邻居) ，将每个派系用作分解节点，并按照它相交的顺序将其连接到下一个派系。 我没有描述得很正确；看我的subsequent answer .

nice 树分解定义如下(来自 Daniel Marx 的定义)。好的树分解是 Root过的。每个节点都是四种类型之一。

Leaf (no children): a set {v}
Introduce (exactly one child): a set S union {v} with child S (v not in S)
Forget (exactly one child): a set S with child S union {v} (v not in S)
Join (exactly two children): a set S with children S and S

任意根非nice树分解，并在根处开始递归转换过程。如果当前节点没有子节点，则构建由引入祖先的叶节点组成的明显链。否则，请注意，如果某个顶点属于至少两个 child ，则它属于当前节点。递归地转换 child 和链忘记祖先，直到他们的集合是当前节点的子集。从理论上讲，最简单的方法是向每个 child 介绍缺失的元素，然后集体加入。然而，由于下一步的运行时间通常以指数方式取决于集大小，因此在子集完成之前尝试一些启发式方法来加入子集可能是明智的。