Algoritmo Divide-y-Conquista para árboles

Question

Estoy tratando de escribir una división & algoritmo de conquista para árboles. Para el paso de división, necesito un algoritmo que divida un Gráfico no dirigido G = (V, E) con n nodos y m bordes en subárboles eliminando un nodo . Todos los subgrafos deben tener la propiedad de que no contienen más de n/2 nodos (el árbol debe dividirse lo más posible). Primero traté de eliminar recursivamente todas las hojas del árbol para encontrar el último nodo restante, luego traté de encontrar el camino más largo en G y eliminar el nodo central de él. El gráfico que figura a continuación muestra que ambos enfoques no funcionan:

¿Hay algún algoritmo de trabajo que hace lo que yo quiero (devuelve el nodo H en el caso anterior).

Answer 1

creo que se podría hacer con un algoritmo de esta manera:

de inicio en la raíz (si el árbol no está arraigado, recoger cualquier nodo).
En cada paso, intente descender al nodo secundario que tiene el subárbol más grande (el número de nodos "debajo" es el más grande).
Si hacerlo haría que la cantidad de nodos "por encima" fuera mayor que n/2, deténgase; de ​​lo contrario, continúe con ese niño.

Este algoritmo debe ser O (log n) si el árbol está razonablemente equilibrado y tenemos tamaños de subárboles precalculados para cada nodo. Si una de esas condiciones no se aplica, sería O (n).

Answer 2

Un algoritmo exacto es como esto,

inicio de las hojas y crear gráficos disjuntos (de hecho todos son K1), en cada paso encontrar al padre de este hojas, y fusionarlas en nuevo árbol, en cada paso si el nodo x tiene r niño conocido y grado de nodo es j tal que j = r+1, sólo tiene un nodo que no está en nodo hijo de x es padre del nodo actual en este caso se dice nodo x es nice, de lo contrario, hay algún niño tales que el subárbol enraizado relacionado de ellos no está construido, en este caso decimos que el nodo x es bad.

Así que en cada paso conecte nice nodos a su elemento primario relacionado, y es obvio que cada paso lleva sum of {degree of parent nice nodes} también en cada paso tiene al menos un nodo agradable (porque empieza desde la hoja), Entonces el algoritmo es O (n) , y se hará por completo, pero para encontrar el nodo que debe eliminarse, de hecho, en cada paso se requiere verificar el tamaño de una lista puestaint (listas de subárboles), esto se puede hacer en O (1) en construcción, también si el tamaño de la lista es igual o mayor que n/2, luego seleccione el nodo agradable relacionado. (de hecho, encuentra el nodo agradable en la lista mínima que satisface esta condición).

Lo obvio es que si es posible dividir el árbol en buena forma (cada parte tiene como máximo n/2 nodos) puede hacerlo mediante este algoritmo, pero si no es así (de hecho, no puede dividirlo en dos o más parte del tamaño más pequeño que n/2) esto le da una buena aproximación para ello. Además, como puede ver, no hay ninguna suposición en el árbol de entrada.

nota: No sé si es posible tener un árbol tal que es imposible dividirlo en algunas partes de tamaño más pequeño que n/2 quitando un nodo.

Answer 3

Este problema parece similar a la búsqueda del center of mass de un objeto. Suponga que cada uno de sus nodos es una masa de punto de igual masa (peso) y su posición está dada por la posición en el gráfico. Su algoritmo intenta encontrar el centro de masa, es decir, el nodo que tiene un peso acumulado similar de nodos en todos los subárboles conectados.

Puede calcular los pesos acumulados en todos los subárboles para cada nodo. A continuación, elija el que sea más equilibrado, s.t. ningún subárbol pesa más de n/2. Probablemente esta es una tarea para alguna programación dinámica.