Algoritmo para generar la descomposición de un árbol.

Quiero construir una descomposición de árbol: http://en.wikipedia.org/wiki/Tree_decomposition y tengo el gráfico de cuerdas y un orden 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 acordes: encuentre un orden de eliminación perfecto, enumere las camarillas máximas (los candidatos son un vértice y los vecinos que aparecen después de ella en el ordenamiento), use cada camarilla como Descomponga el nodo y conéctelo a la siguiente camarilla en el orden en que se interseca.

Esto no funciona sin embargo y no puedo entender por qué. Considere el siguiente ejemplo:

Ordenación perfecta eliminación:

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

Grafica de cordal:

introduzca la descripción de la imagen aquí

Descomposición del árbol:

introduzca la descripción de la imagen aquí

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 orden perfecto y ‘chordal_graph’ es un objeto gráfico para networkx .

Así que ese fue mi (mal, como resultado) consejo. La descomposición de su á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 que también es incorrecto, ya que los vértices 0 no están conectados. Lo siento por eso.

Lo que debería haber hecho es dejar de lado la condición de maximalidad por el momento y conectar cada camarilla K al siguiente candidato sembrado con un vértice que pertenezca a K. Esto garantiza que cada vértice en K que existe en al menos otra camarilla posterior también Aparece en el destino 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 dividir las camarillas no máximas al verificar, para cada camarilla en orden inverso, si es un superconjunto de su padre y, si es así, repararlo a los hijos de su padre.

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