Cho đồ thị vô hướng G=(V,E) có n đỉnh, phát biểu nào sau đây là đúng nhất:
Đáp án đúng: A
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).
