生成树分解的算法

问题描述

我想构造一个树分解:http://en.wikipedia.org/wiki/Tree_decomposition 和我有和弦图和完美的消除排序.我正在遵循 前一个线程中给出的建议,即:

I want to construct a tree decomposition: http://en.wikipedia.org/wiki/Tree_decomposition and I have the chordal graph and a perfect elimination ordering. I am following advice given in a previous thread,namely:

构造一个弦图的非好(一般)树分解:找到一个完美的消除排序，枚举最大值cliques(候选者是一个顶点和出现的邻居在排序之后)，使用每个集团作为分解节点和按照相交的顺序将其连接到下一个派系.

但是这不起作用，我不知道为什么.考虑以下示例:

This does not work however and I can not figure out why. Consider the following example:

完美消除排序:

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

和弦图:

树分解:

我正在使用 python，我当前的算法如下:

I am using python and my current algorithm is the following:

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 的图形对象.

where eo is a list of the perfect ordering and 'chordal_graph' is a graph object for networkx.

推荐答案

这就是我的(事实证明是糟糕的)建议.您的树分解有一些不是最大的派系，即 {2, 0, 1}, {0, 1} 和 {1}.候选团的名单是

So that was my (bad, as it turns out) advice. Your tree decomposition has some cliques that aren't maximal, i.e., {2, 0, 1}, {0, 1}, and {1}. The list of candidate cliques is

{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 个顶点没有连接.很抱歉.

which is wrong as well, since the 0 vertices aren't connected. Sorry about that.

我应该做的是暂时搁置最大条件，并将每个派系 K 连接到下一个以属于 K 的顶点作为种子的候选者.这确保 K 中的每个顶点至少存在于另一个随后的派系也出现在连接的目标中.然后分解是这样的

What I should have done is to set aside the maximality condition for the moment and to connect each clique K to the next candidate seeded with a vertex belonging to K. This ensures that every vertex in K that exists in at least one other subsequent clique also appears in the target of the connection. Then the decomposition looks like this

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

并且您可以通过以相反的顺序检查每个团是否是其父级的超集，如果是，则将其父级的子级重新设置为父级，从而拼接出非极大团.

and you can splice out the non-maximal cliques by checking, for each clique in reverse order, whether it's a superset of its parent, and if so, reparenting its parent's children to it.

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

这篇关于生成树分解的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！