从消元顺序和和弦图获取树分解

Question

我需要一个图的树分解，前提是我已经有了一个消元顺序和这个图的和弦化。

我的想法是先找出图中的所有团（团就是一群互相连接的点），这部分我已经能做到。然后我想从一个根节点开始，建立一个二叉树，树的子节点（也就是团）根据这些团之间有多少个共同的点来决定。我想一直这样做，直到所有的团都用上，这样我就得到了一个树。不过问题是，这些团可能有超过两个点，所以我不能对每个点递归地进行处理，否则树就不一定是二叉的了。

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

我正在用Python实现这个过程，目前我已经有了和弦图、所有团的列表和消元顺序。如果有想法或者代码，欢迎分享！

Answer 1

要构建一个不太好（一般来说）的树分解，针对一个和谐图：找到一个完美的消去顺序，列出所有的最大团（候选者是一个顶点和在顺序中出现在它后面的邻居），用每个团作为分解节点，并把它连接到在顺序中与它相交的下一个团。 我没有描述得很准确；请查看我的 后续回答。

一个好的树分解是这样定义的（定义来自 Daniel Marx）。好的树分解是有根的。每个节点有四种类型。

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

随便给这个不太好的树分解选一个根节点，然后从根节点开始一个递归转换过程。如果当前节点没有孩子节点，那么就构建一个明显的链，这个链由一个叶子节点和引入的祖先组成。否则，如果某个顶点属于至少两个孩子节点，那么它也属于当前节点。递归地转换孩子节点，并把忘记的祖先链在一起，直到它们的集合是当前节点集合的子集。理论上，最简单的做法是把缺失的元素引入到每个孩子节点，然后一起合并。不过，下一步的运行时间通常会随着集合大小的增加而呈指数增长，所以在孩子节点的子集还没完全之前，尝试一些启发式的方法来合并孩子节点可能会更明智。