JavaScript is required

Nếu G = (V, E) là một đơn đồ thị vô hướng thì: (Chọn phương án đúng)

A.

Ma trận kề gồm các phần tử đối xứng nhau qua đường chéo chính

B.

Ma trận kề gồm các phần tử không đối xứng nhau qua đường chéo chính

C.

Các phần tử trên đướng chéo chính bằng 1

D.

Các phần tử trên đường chéo phụ bằng 1

Trả lời:

Đáp án đúng: A


Trong một đơn đồ thị vô hướng G = (V, E), ma trận kề biểu diễn mối quan hệ giữa các đỉnh. Vì đồ thị là vô hướng, nên nếu có một cạnh nối đỉnh i và đỉnh j, thì cũng có một cạnh nối đỉnh j và đỉnh i. Điều này có nghĩa là phần tử ở hàng i, cột j của ma trận kề sẽ bằng phần tử ở hàng j, cột i. Do đó, ma trận kề của một đơn đồ thị vô hướng là một ma trận đối xứng qua đường chéo chính. Phương án A đúng vì nó phản ánh tính chất đối xứng của ma trận kề trong đồ thị vô hướng. Phương án B sai vì nó khẳng định ma trận kề không đối xứng. Phương án C sai vì các phần tử trên đường chéo chính của ma trận kề bằng 1 khi có một vòng lặp (cạnh nối một đỉnh với chính nó), nhưng trong một đơn đồ thị (không có vòng lặp), các phần tử này thường bằng 0. Phương án D sai vì không có quy tắc nào quy định các phần tử trên đường chéo phụ phải bằng 1.

Câu hỏi liên quan