Cho thuật toán sau:
Xét một cây,ta lấy lá có giá trị bé nhất và xóa nó đi và đọc giá trị số cùng liên thuộc 1 cạnh với nó .Cứ thực hiện thuật toán cho đến khi cây đó chỉ còn lại dạng một đoạn thẳng:
Như hình vẽ trên là 1 cây gồm 9 đỉnh : đầu tiên ta
Xóa lá $3$ ta có $2$
$\rightarrow$ Xóa lá $6$ ta có $5$
$\rightarrow$ Xóa lá $7$ ta có $5$
$\rightarrow$ Xóa lá $5$ ta có $4$
$\rightarrow$ Xóa lá $4$ ta có $1$
$\rightarrow$ Xóa lá $1$ ta có $2$
$\rightarrow$ Xóa lá $8$ ta có $2$ .Còn lại đoạn thẳng $(2,9)$
Lúc này ta thu được bộ số gồm $9-2=7$ số là $(2,5,5,4,1,2,2)$
Câu hỏi ngược lại: Nếu có bộ số $(2,5,5,4,1,2,2)$ hãy tìm thuật toán xây dựng một cây cụ thể
Tổng quát với bộ số $(x_1,x_2,......,x_{n-2})$
Bài viết đã được chỉnh sửa nội dung bởi KnightA0: 23-06-2015 - 16:20
