python - prediccion - Obteniendo una descomposición de árbol de un ordenamiento de eliminación y un gráfico de cordal

prediccion con python

Question

Necesito una buena descomposición en árbol de un gráfico dado un ordenamiento de eliminación y una cororización del gráfico.

Mi idea es obtener todas las camarillas en el gráfico (lo cual puedo hacer) y construir un árbol binario comenzando desde una raíz y hacer niños (es decir, camarillas) dependiendo de cuántas verdades tienen las camarillas en común. Quiero hacer esto hasta que se utilicen todas las camarillas y, por lo tanto, tengo un árbol. El problema es que las clicas podrían tener más de 2 vértices, por lo que no puedo ejecutar recursivamente para cada vértice como entonces, el árbol podría no ser binario.

http://en.wikipedia.org/wiki/Tree_decomposition http://en.wikipedia.org/wiki/Chordal_graph

Estoy haciendo una implementación en python y actualmente tengo el gráfico de cordal, una lista de todas las camarillas y un orden de eliminación. Ideas, y / o código son más que bienvenidos!

Answer 1

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. No lo describí del todo bien; ver mi respuesta posterior .

Una buena descomposición del árbol se define de la siguiente manera (definición de Daniel Marx ). Bonitas descomposiciones de árboles están enraizadas. Cada nodo es de uno de cuatro tipos.

Leaf (no children): a set {v}
Introduce (exactly one child): a set S union {v} with child S (v not in S)
Forget (exactly one child): a set S with child S union {v} (v not in S)
Join (exactly two children): a set S with children S and S

Rootee la descomposición de árbol no agradable de forma arbitraria e inicie un procedimiento de conversión recursivo en la raíz. Si el nodo actual no tiene hijos, construya la cadena obvia que consiste en un nodo de hoja con antepasados ​​introducidos. De lo contrario, observe que, si algún vértice pertenece a al menos dos hijos, entonces pertenece al nodo actual. Conversión recursiva de los hijos y cadenas olvidan antepasados ​​hasta que sus conjuntos sean subconjuntos de los del nodo actual. La forma más fácil de proceder en teoría es introducir los elementos que faltan a cada niño, luego unirse en masa. Sin embargo, dado que el tiempo de ejecución del siguiente paso depende a menudo de forma exponencial del tamaño del conjunto, podría ser conveniente intentar algunas heurísticas para unir a los niños antes de que se completen sus subconjuntos.