Uncategorized

You are currently browsing the archive for the Uncategorized category.

Một cây là một đồ thị, liên thông và không có chu trình. Bậc của một nút trong cây là số cạnh kề với nút đó. Một nút được gọi là nút lá của cây nếu nó có bậc 1 (nói cách khác, nó chỉ có đúng một cạnh kề).

Câu hỏi: Một cây có $n$ nút lá và không có hai nút bậc 2 nào kề nhau. Hỏi cây có tối đa bao nhiêu nút?

Trong câu hỏi trên, ta không có bất kì điều kiện gì với các nút có bậc > 2.

Gợi ý trả lời: Ta có nhận xét sau:

Nhật xét 1: Một cây với $n$ lá và không có nút nào có bậc 2 có tối đa $2n-2$ nút.

Gọi $T$ là cây như trong câu hỏi. Gọi $F$ là cây thu được từ $T$ như sau: với mỗi nút bậc $2$ $x$ và hai hàng xóm $y,z$ của $x$, ta xoá $x$ khỏi $T$ và thêm một cạnh nối giữa $y$ và $z$. Theo nhận xét 1, $F$ có tối đa $2n-2$ nút. Do đó, $F$ có tối đa $2n-3$ cạnh. Mỗi cạnh của $F$ tương ứng với tối đa một nút bậc $2$ của $T$. Do đó, $T$ có tối đa:

2n-2 + (2n-3) = 4n-5

nút (dpcm).


Câu hỏi cho bạn: Tìm một cây thoả mãn điều kiện của câu hỏi 1 có đúng $4n-5$ nút.

« Older entries § Newer entries »