生成树分解的算法

Question

我想构建一个树分解：http://en.wikipedia.org/wiki/Tree_decomposition，我手头有一个和谐图（chordal graph）和一个完美消除顺序（perfect elimination ordering）。我在参考一个之前的讨论中的建议，具体来说：

要构建一个非优雅的（一般来说）和谐图的树分解：找到一个完美消除顺序，列举出所有的最大团（候选者是一个顶点和在顺序中出现在它后面的邻居），使用每个团作为分解节点，并将其连接到在顺序中与之相交的下一个团。

不过，这个方法并不奏效，我也搞不清楚为什么。考虑以下例子：

完美消除顺序：

['4', '3', '5', '7', '6', '2', '0', '1']

和谐图：

树分解：

我正在使用Python，我目前的算法如下：

T=nx.Graph()
    nodelist=[]
    for i in eo:
        vertex=str(i)
        bag=set()
        bag.add(vertex)
        for j in chordal_graph.neighbors(str(i)):
            bag.add(str(j))
        T.add_node(frozenset(bag))
        nodelist.append(frozenset(bag))
        chordal_graph.remove_node(str(i))
    for node1 in range(len(nodelist)):
        found=False
        for node2 in range(node1+1,len(nodelist)):
            if found==False and len(nodelist[node1].intersection(nodelist[node2]))>0:
                T.add_edge(nodelist[node1],nodelist[node2])
                found=True
    nx.draw(T)
    p.show()     

其中 eo 是完美顺序的列表，而 'chordal_graph' 是一个用于 networkx 的图对象。

Answer 1

这就是我之前给出的（结果证明是个坏主意的）建议。你的树分解中有一些团体（cliques）并不是最大的，比如说 {2, 0, 1}、{0, 1} 和 {1}。候选团体的列表是

{4, 5, 6} (maximal)
{3, 2} (maximal)
{5, 6, 2, 0} (maximal)
{7, 2, 1} (maximal)
{6, 2, 0, 1} (maximal)
{2, 0, 1} (not maximal: subset of {6, 2, 0, 1})
{0, 1} (not maximal: subset of {6, 2, 0, 1})
{1} (not maximal: subset of {6, 2, 0, 1})

然后分解应该是这样的

                {3, 2}
                  |
{4, 5, 6}----{5, 6, 2, 0}
                  |
             {7, 2, 1}
                  |
             {6, 2, 0, 1},

但这也是错的，因为0这个点没有连接。对此我很抱歉。

我应该先不考虑最大性条件，而是把每个团体 K 连接到下一个候选团体，连接时用 K 中的一个点作为起始点。这样可以确保 K 中的每个点，如果在后续的某个团体中也出现过，就会出现在连接的目标中。然后分解看起来是这样的

{4, 5, 6}----{5, 6, 2, 0}
                  |
             {6, 2, 0, 1}
                  |
   {3, 2}----{2, 0, 1}----{7, 2, 1}
                  |
                {0, 1}
                  |
                {1}

接着你可以通过反向检查每个团体，看看它是否是其父团体的超集，来剔除那些不是最大的团体。如果是的话，就把它父团体的子团体重新连接到这个团体上。

{4, 5, 6}----{5, 6, 2, 0}
                  |
   {3, 2}----{6, 2, 0, 1}----{7, 2, 1}