Algorytm dzielenia i podrywania dla drzew

Question

Próbuję napisać algorytm podboju dla drzew o podziale &. W przypadku kroku dzielenia potrzebuję algorytmu, który podzieli dany nieukierunkowany wykres G = (V, E) z n węzłami i m krawędziami na pod-drzewa przez usunięcie węzła węzła. Wszystkie podelgi powinny mieć właściwość, że nie zawierają więcej niż węzłów (drzewo powinno być podzielone jak najbardziej równe). Najpierw próbowałem rekurencyjnie usunąć wszystkie liście z drzewa, aby znaleźć ostatni pozostały węzeł, a następnie spróbowałem znaleźć najdłuższą ścieżkę w G i usunąć środkowy węzeł z tego drzewa. Podana poniżej wykres pokazuje, że oba podejścia nie działają:

Czy istnieje jakiś algorytm pracy, że robi to, co chcę (zwraca węzła H w powyższym przypadku).

Answer 1

Myślę, że można to zrobić za pomocą algorytmu jak ten:

rozpocznie się w katalogu głównym (jeśli drzewo nie jest zakorzenione, wybrać dowolny węzeł).
W każdym kroku spróbuj zejść do węzła podrzędnego, który ma największy poddrzewo (liczba węzłów "poniżej" jest największa).
Jeśli to spowodowałoby, że liczba węzłów "powyżej" jest większa niż n/2, zatrzymaj się, w przeciwnym razie kontynuuj z tym dzieckiem.

Ten algorytm powinien być O (log n), jeśli drzewo jest rozsądnie zrównoważone i mamy rozmiary poddrzew prekomputowanych dla każdego węzła. Jeśli jeden z tych warunków nie ma zastosowania, będzie to O (n).

Answer 2

Jeden dokładny algorytm jest jak ten,

start z listkami i tworzyć rozłączne wykresy (w rzeczywistości wszystkie są K1), w każdym kroku odnaleźć rodzica tej liście, i połączyć je w nowym drzewie, w każdym kroku jeśli węzeł x ma jedno dziecko i stopień węzła to j taki, że j = r+1, po prostu węzeł, który nie jest w węźle podrzędnym x jest elementem nadrzędnym węzła bieżącego w tym przypadku mówimy, że węzeł x to nice, w przeciwnym razie istnieje pewne dziecko, takie jak ten pokrewny ukorzeniony poddrzew nie został skonstruowany, w tym przypadku mówimy, że węzeł x to bad.

Tak więc w każdym kroku podłącz węzły nice do pokrewnego rodzica i oczywistym jest, że każdy krok zajmuje sum of {degree of parent nice nodes} również w każdym kroku masz co najmniej jeden niezły węzeł (ponieważ zaczynasz od liścia), więc algorytm to O (n) , i będzie to wykonane całkowicie, ale dla znalezienia węzła, który powinien zostać usunięty, W rzeczywistości w każdym kroku jest wymagane, aby sprawdzić rozmiar listy rozłącznej (listy poddrzewa), można to zrobić w O (1) w konstrukcji, również jeśli rozmiar listy jest równy lub większy niż n/2, a następnie wybierz powiązany ładny węzeł. (w rzeczywistości znajdź ładny węzeł na liście minimalnej, która spełnia ten warunek).

Oczywistym jest, że jeśli można podzielić drzewo w dobry sposób (każda część ma co najwyżej węzeł n/2), można to zrobić za pomocą tego algorytmu, ale jeśli tak nie jest (w rzeczywistości nie można podzielić go na dwie części lub większa część wielkości mniejszej niż n/2) daje to dobre przybliżenie. Jak widać, nie ma założenia w drzewie wejściowym.

uwaga: Nie wiem, możliwe jest, aby drzewo było takie, że niemożliwe jest podzielenie go na części o wielkości mniejszej niż n/2 przez usunięcie jednego węzła.

Answer 3

Ten problem wydaje się podobny do znalezienia obiektu center of mass. Założono, że każdy z twoich węzłów jest masą punktową o równej masie (wadze), a jego pozycja jest określona przez pozycję na wykresie. Twój algorytm próbuje znaleźć środek masy, tj. Węzeł, który ma podobny skumulowany ciężar węzłów we wszystkich połączonych pod-drzewach.

Możesz obliczyć skumulowaną wagę we wszystkich pod-drzewach dla każdego węzła. Następnie wybierz ten, który jest najbardziej zrównoważony, s.t. żadne pod-drzewo nie waży więcej niż n/2. Prawdopodobnie jest to zadanie do programowania dynamicznego.