Trong các câu sau đây, những câu nào đúng? a) Chỉ có đơn đồ thị có hướng mới biểu diễn được bằng ma trận kề...

a) Sai.

Cả đơn đồ thị vô hướng và đơn đồ thị có hướng đều có thể biểu diễn được bằng ma trận kề.

●  Ma trận kề của một đồ thị G với n đỉnh được ký hiệu là A, là một ma trận vuông n x n, trong đó:

o   A[i, j] = 1 nếu có cạnh nối đỉnh i và đỉnh j.

o   A[i, j] = 0 nếu không có cạnh nối đỉnh i và đỉnh j.

b) Đúng.

Cách biểu diễn đồ thị bằng ma trận kề tuy đơn giản nhưng có thể lãng phí bộ nhớ trong trường hợp đồ thị có nhiều đỉnh nhưng có ít cạnh. Lý do là vì ma trận kề là một ma trận vuông có kích thước n x n, trong đó n là số đỉnh của đồ thị. Do đó, ma trận kề sẽ có kích thước n^2, dẫn đến việc sử dụng nhiều bộ nhớ hơn so với các cách biểu diễn khác như danh sách kề.

c) Sai.

Cả đơn đồ thị vô hướng và đơn đồ thị có hướng đều có thể biểu diễn được bằng danh sách kề.

●  Danh sách kề của một đồ thị G là một mảng gồm n phần tử, trong đó mỗi phần tử i (0 ≤ i < n) là một danh sách chứa tất cả các đỉnh kề với đỉnh i.

d) Đúng.

Cách biểu diễn bằng danh sách kề sẽ phù hợp khi đồ thị có nhiều đỉnh nhưng có ít cạnh. Lý do là vì danh sách kề chỉ lưu trữ thông tin về các cạnh thực sự tồn tại trong đồ thị, do đó sẽ tiết kiệm bộ nhớ hơn so với ma trận kề, đặc biệt là khi đồ thị có nhiều đỉnh nhưng có ít cạnh.