Một cây có ít nhất mấy đỉnh treo?

Trong một đồ thị vô hướng G=(V,E) có n đỉnh, ma trận kề là một ma trận vuông kích thước n x n. Phần tử ở hàng i, cột j của ma trận kề biểu diễn cho việc có cạnh nối giữa đỉnh i và đỉnh j hay không. Vì đồ thị là vô hướng, nếu có cạnh nối giữa đỉnh i và đỉnh j thì cũng có cạnh nối giữa đỉnh j và đỉnh i. Do đó, ma trận kề của đồ thị vô hướng đối xứng qua đường chéo chính. Tức là, phần tử ở hàng i, cột j bằng phần tử ở hàng j, cột i.

Phương án A đúng vì ma trận kề của đồ thị vô hướng đối xứng qua đường chéo chính.

Phương án B sai vì ma trận kề phải là ma trận vuông kích thước n x n, không phải 2n.

Phương án C sai vì các giá trị trên đường chéo chính chỉ bằng 1 nếu có cạnh khuyên (loop) tại đỉnh đó. Trong trường hợp tổng quát, giá trị này có thể bằng 0 nếu không có cạnh khuyên.

Phương án D sai vì ma trận kề phải là ma trận vuông kích thước n x n, không phải 2(n – 1).

Tập lũy thừa của một tập A, ký hiệu P(A), là tập hợp tất cả các tập con của A.

Nếu A = {1, 2, a}, thì các tập con của A bao gồm:

• Tập rỗng: ∅
• Các tập con chứa một phần tử: {1}, {2}, {a}
• Các tập con chứa hai phần tử: {1, 2}, {1, a}, {2, a}
• Tập con chứa ba phần tử: {1, 2, a}

Vậy, tập lũy thừa của A là: P(A) = {∅, {1}, {2}, {a}, {1, 2}, {1, a}, {2, a}, {1, 2, a}}

Do đó, đáp án đúng là C.

Tập lũy thừa của một tập hợp A, ký hiệu là P(A), là tập hợp chứa tất cả các tập con của A, kể cả tập rỗng và chính tập A. Với A = {a, b, 5}, ta cần liệt kê tất cả các tập con có thể có của A:

• Tập rỗng: ∅


• Các tập con có 1 phần tử: {a}, {b}, {5}


• Các tập con có 2 phần tử: {a, b}, {a, 5}, {b, 5}


• Tập con có 3 phần tử (chính là A): {a, b, 5}

Vậy, tập lũy thừa của A là: P(A) = {∅, {a}, {b}, {5}, {a, b}, {a, 5}, {b, 5}, {a, b, 5}}

So sánh với các đáp án:

• Đáp án A: {{5, a, b}} không đúng vì đây chỉ là một tập hợp chứa một tập con của A.


• Đáp án B: {∅, {a}, {b}, {5}} thiếu các tập con có 2 và 3 phần tử.


• Đáp án C: {{a}, {b}, {5}, {a, b}, {a, 5}, {b, 5}, {a, b, 5}} thiếu tập rỗng và có một số ký hiệu không chính xác (dùng {{...}} thay vì {...}). Ngoài ra, việc thiếu tập rỗng cũng làm đáp án này sai.


• Đáp án D: {∅, {a}, {b}, {5}, {a, b}, {a, 5}, {5, b}, {5, b, a}} là đáp án đúng vì nó bao gồm tất cả các tập con của A, kể cả tập rỗng. Lưu ý rằng {5, b} và {5, b, a} tương đương với {b, 5} và {a, b, 5} do tính chất không phân biệt thứ tự của các phần tử trong tập hợp.

Tập lũy thừa của một tập hợp S là tập hợp tất cả các tập con của S, kể cả tập rỗng và chính tập S. Nếu tập S có n phần tử, thì tập lũy thừa của S có 2ⁿ phần tử.

Trong trường hợp này, tập S = {a, b, c, d} có 4 phần tử. Vậy, số phần tử của tập lũy thừa của S là 2⁴ = 16.