python - para - juegos con arboles binarios

Algoritmo para generar una descomposición de árbol

Question

Quiero construir una descomposición de árbol: http://en.wikipedia.org/wiki/Tree_decomposition y tengo el gráfico de cordal y un ordenamiento de eliminación perfecto. Estoy siguiendo los consejos dados en un hilo anterior , a saber:

Para construir una descomposición de árbol no agradable (en general) de un gráfico de cordal: encuentre un ordenamiento de eliminación perfecto, enumere las camarillas máximas (los candidatos son un vértice y los vecinos que aparecen después en el orden), use cada camarilla como un nodo de descomposición y conéctelo a la siguiente camarilla en el orden en que se cruza.

Sin embargo, esto no funciona y no puedo entender por qué. Considere el siguiente ejemplo:

Perfecto orden de eliminación:

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

Gráfico de cordal:

Descomposición del árbol:

Estoy usando Python y mi algoritmo actual es el siguiente:

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

donde eo es una lista del ordenamiento perfecto y ''chordal_graph'' es un objeto de gráfico para networkx .

Answer 1

Así que ese fue mi consejo (malo, como resulta). La descomposición de tu árbol tiene algunas camarillas que no son máximas, es decir, {2, 0, 1}, {0, 1} y {1}. La lista de camarillas candidatas es

{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})

Entonces la descomposición debería verse como

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

lo cual también es incorrecto, ya que los 0 vértices no están conectados. Lo siento por eso.

Lo que debería haber hecho es dejar de lado la condición de máxima para el momento y conectar cada camarilla K con el siguiente candidato sembrado con un vértice perteneciente a K. Esto asegura que cada vértice en K que existe en al menos otra camarilla posterior también aparece en el objetivo de la conexión. Entonces la descomposición se ve así

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

y puede empalmar las camarillas no máximas comprobando, para cada camarilla en orden inverso, si se trata de un superconjunto de su elemento primario y, de ser así, reparentándolo a los hijos de sus padres.

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