Thuật toán phân chia và đồng hóa cho cây

Question

Tôi đang cố gắng viết một thuật toán phân chia & cho cây. Đối với bước phân chia, tôi cần một thuật toán phân vùng một đồ thị vô hướng cho trước G = (V, E) với n nút và m cạnh vào các cây con bằng cách loại bỏ một nút . Tất cả các biểu đồ con phải có thuộc tính mà chúng không chứa nhiều hơn n/2 nút (cây nên được chia nhỏ nhất có thể). Đầu tiên tôi đã cố gắng loại bỏ đệ quy tất cả các lá khỏi cây để tìm nút còn lại cuối cùng, sau đó tôi cố gắng tìm đường đi dài nhất trong G và loại bỏ nút giữa của nó. Đồ thị dưới đây cho thấy rằng cả hai phương pháp không làm việc:

Có một số thuật toán làm việc mà những gì tôi muốn (trả về nút H trong trường hợp trên).

Answer 1

Tôi nghĩ bạn có thể làm điều đó với một thuật toán như sau:

Bắt đầu trong thư mục gốc (nếu cây không bắt nguồn từ, chọn bất kỳ nút nào).
Trong mỗi bước, hãy cố gắng đi sâu vào nút con có cây con lớn nhất (số lượng nút "bên dưới" là số lớn nhất).
Nếu làm điều đó sẽ làm cho số lượng nút “ở trên” lớn hơn n/2, dừng lại, nếu không thì tiếp tục với đứa trẻ đó.

Thuật toán này phải là O (log n) nếu cây được cân bằng hợp lý và chúng tôi có kích thước của subtrees precomputed cho mỗi nút. Nếu một trong những điều kiện đó không áp dụng, nó sẽ là O (n).

Answer 2

Một thuật toán chính xác là như thế này,

Bắt đầu từ lá và tạo biểu đồ rời nhau (trong thực tế tất cả đều K1), trong mỗi bước tìm ra mẹ của lá này, và ghép lại thành cây mới, trong mỗi bước nếu nút x có r trẻ đã biết và mức độ nút là j sao cho j = r+1, chỉ cần một nút không nằm trong nút con của x là nút cha của nút hiện tại trong trường hợp này, chúng tôi nói nút x là nice. rằng cây con có nguồn gốc liên quan của chúng không được xây dựng, trong trường hợp này chúng ta nói rằng nút x là bad. Vì vậy, trong mỗi bước kết nối các nút nice với cha mẹ có liên quan của chúng, và rõ ràng mỗi bước mất sum of {degree of parent nice nodes} cũng trong mỗi bước bạn có ít nhất một nút đẹp (vì bạn bắt đầu từ lá), Vì vậy, thuật toán là O (n) , và nó sẽ được thực hiện hoàn toàn, nhưng để tìm nút cần được loại bỏ, Thực tế trong mỗi bước được yêu cầu để kiểm tra kích thước của một danh sách dijoint (danh sách subtree), điều này có thể được thực hiện trong O (1) trong xây dựng, Ngoài ra nếu kích thước của danh sách bằng hoặc lớn hơn n/2, sau đó chọn nút đẹp có liên quan. (trên thực tế tìm thấy nút đẹp trong danh sách tối thiểu thỏa mãn điều kiện này). Điều rõ ràng là nếu có thể chia cây theo cách tốt (mỗi phần có tối đa nút n/2), bạn có thể thực hiện nó bằng thuật toán này, nhưng nếu không phải như vậy (trên thực tế bạn không thể chia nó thành hai phần.). hoặc nhiều hơn một phần của kích thước nhỏ hơn n/2) điều này cung cấp cho bạn xấp xỉ tốt cho nó. Cũng như bạn có thể thấy không có giả định trong cây đầu vào.

lưu ý: Tôi không biết là có thể có một cây như vậy mà nó không thể phân vùng nó vào một số phần của kích thước nhỏ hơn n/2 bằng cách loại bỏ một nút.

Answer 3

Sự cố này có vẻ tương tự như việc tìm kiếm center of mass của một đối tượng. Giả sử mỗi nút của bạn là một khối lượng điểm có khối lượng bằng nhau (khối lượng) và vị trí của nó được cho bởi vị trí trong biểu đồ. Thuật toán của bạn cố gắng tìm trung tâm khối lượng, tức là nút có khối lượng tích lũy tương tự của các nút trong tất cả các cây con được kết nối.

Bạn có thể tính trọng số tích lũy trên tất cả các cây con cho mỗi nút. Sau đó chọn một trong đó là cân bằng nhất, s.t. không có cây con nào nặng hơn n/2. Có lẽ đây là một nhiệm vụ cho một số chương trình động.