生成树分解的算法

Question

我想构建一个树分解:http://en.wikipedia.org/wiki/Tree_decomposition,我有chordal图和完美的消除顺序.我遵循前一个帖子中给出的建议,即:

构造一个非常好的(通常)和弦图的树分解:找到一个完美的消除顺序,枚举最大集团(候选是一个顶点和在排序中出现在它之后的邻居),使用每个集团作为一个分解节点并将其连接到与其相交的排序中的下一个集团.

然而,这不起作用,我无法弄清楚为什么.请考虑以下示例:

完美淘汰订购:

['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()     

where eo是一个完美排序的列表,'chordal_graph'是一个图形对象networkx.

Answer 1

这就是我的建议（事实证明是糟糕的）。您的树分解有一些不是最大的派系，即 {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}