Tập độc lập lớn nhất trên cây
Để phát biểu bài toán ta cần nhắc lại một số khái niệm. Giả sử G = (V,E) là đơn đồ thị vô hướng với trọng số trên đỉnh c(), V. Một tập con các đỉnh của đồ thị được gọi là tập độc lập, nếu như hai đỉnh bất kỳ trong U là không kề nhau trên G. Nếu U là ...
Để phát biểu bài toán ta cần nhắc lại một số khái niệm. Giả sử G = (V,E) là đơn đồ thị vô hướng với trọng số trên đỉnh c(), V. Một tập con các đỉnh của đồ thị được gọi là tập độc lập, nếu như hai đỉnh bất kỳ trong U là không kề nhau trên G.
Nếu U là tập độc lập, thì ta gọi trọng số của U là tổng trọng số của các đỉnh trong nó. Ta sẽ gọi tập độc lập với trọng số lớn nhất là tập độc lập lớn nhất. Bài toán tập độc lập lớn nhất trên đồ thị là một bài toán khó. Tuy nhiên, khi đồ thị G là cây bài toán này có thể giải hiệu quả bởi thuật toán quy hoạch động.
Bài toán phát biểu như sau: Cho cây T = (V,E) với trọng số trên các đỉnh c(), V. Hãy tìm tập độc lập lớn nhất của T.
Dựng cây T có gốc tại đỉnh r, và duyệt cây theo thứ tự sau (postorder). Xét đỉnh tuỳ ý với k con w1, w2, …, wk. Ta có thể tạo tập độc lập của cây con gốc tại theo hai cách, phụ thuộc vào việc ta có chọn đỉnh vào tập độc lập hay không:
• Nếu ta không chọn vào tập độc lập, thì ta có thể kết hợp các tập độc lập của các cây con gốc tại w1, w2, …, wk để tạo tập độc lập gốc tại , bởi vì không có cạnh nối giữa các cây con này.
• Còn nếu ta chọn vào tập độc lập thì ta chỉ có thể sử dụng các tập độc lập không chứa gốc của các cây con tương ứng với w1, w2, …, wk, do và bất kỳ con wi nào của nó không cùng chọn vào tập độc lập
Do đó, với mỗi đỉnh thuật toán phải tính các thông tin sau:
1. big() = trọng lượng lớn nhất của tập độc lập của cây con có gốc tại .
2. bibnotroot() = trọng lượng lớn nhất của tập độc lập không chứa của cây con có gốc tại .
Tại đỉnh , thuật toán sẽ gọi đệ quy tính big(wi) và bignotroot(wi) với mỗi cây con gốc tại các con w1, w2, …, wk của . Sau đó tính bignotroot() và big() sử dụng công thức đệ quy tương ứng với hai tình huống mô tả ở trên:
Nếu là lá thì bignotroot() = 0 và big() = c().
Từ các phân tích trên dễ dàng xây dựng thuật toán tính big(), V với thời gian O(n), trong đó n = .
Ta xét cách thực hiện đệ quy của thuật toán. Rõ ràng trọng số của tập độc lập lớn nhất tại đỉnh sẽ hoặc là bằng trọng lượng của tất cả các tập độc lập của các cây con gốc tại w1, w2, …, wk hoặc bằng tổng trọng lượng của và trọng lượng của các cây con gốc tại các đỉnh là cháu của . Từ đó ta có thuật toán đệ quy sau:
function MaxISTree(r);
(* Tìm tập độc lập lớn nhất của cây con gốc tại r *)
(* Con(r) - danh sách các con của root *)
(* Cháu(r) - danh sách các cháu của root *)
begin
if Con(r) = then return c(r) (* r lµ l¸ *)
else
begin
bignotroot: = 0;
for w size 12{ in } {} Con(r) do
bignotroot: = bignotroot + MaxISTree(w);
bigr: = c(r);
for u size 12{ in } {} Chau(r) do
bigr: = bigr + MaxISTree(u);
return max(bignotroot, bigr);
end;
end;
Lệnh gọi MaxISTree(root) (root là gốc của cây T) sẽ thực hiện thuật toán. Tất nhiên thủ tục đệ qui này là không hiệu quả. Do ở đây chỉ có O(n) bài toán con cần giải, ta có thể viết lại nó dưới dạng thủ tục đệ qui có nhớ để có được thuật toán với thời gian tính O(n).
