给定消除顺序和图的弦化，我需要一个很好的图树分解。
我的想法是获取图中的所有派系（我可以做到）并从根开始构建二叉树并根据派系共有的验证数来生成子级（即派系）。我想这样做，直到使用所有派系，因此，我有一棵树。问题是团可能有两个以上的顶点，所以我不能递归地为每个顶点运行，因为树可能不是二元的。
http://en.wikipedia.org/wiki/Tree_decomposition http://en.wikipedia.org/wiki/Chordal_graph
我正在用 python 进行实现，目前我有弦图、所有派系的列表和消除排序。想法和/或代码非常受欢迎！
构造一个弦图的非良好（一般）树分解：找到一个完美的消除排序，枚举最大团（候选是一个顶点和在排序中出现在它之后的邻居），使用每个团作为一个分解节点，并按照相交的顺序将其连接到下一个团。我描述得不太对。看我随后的回答。
一个好的树分解定义如下（来自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
任意根非好树分解，并在根处开始递归转换过程。如果当前节点没有子节点，则构建由具有引入祖先的叶节点组成的明显链。否则，请注意，如果某个顶点属于至少两个孩子，则它属于当前节点。递归转换子节点和链忘记祖先，直到它们的集合是当前节点的子集。理论上最简单的方法是将缺失的元素介绍给每个孩子，然后集体加入。然而，由于下一步的运行时间通常以指数方式取决于集合大小，因此在子集完成之前尝试一些启发式方法来加入子集可能是明智的。