JavaScript is required

Cho đồ thị vô hướng trọng số trên cạnh G = (V, E) trong đó V = {1,2,3,4,5,6} và E = {(1,2),(1,3),(1,6),(2,3),(2,5),(2,6),(4,5),(4,6),(5,6)}. Trọng số trên cạnh w(1,2) = 1, w(1,3) = 1, w(1,6) = 4, w(2,3) = 1, w(2,5) = 2, w(2,6) = 2, w(4,5) = 3, w(4,6) = 5, w(5,6) = 2. Hỏi cây khung nhỏ nhất của G có bao nhiêu cạnh?

A.

3

B.

4

C.

6

D.
5
Trả lời:

Đáp án đúng: C


Cây khung nhỏ nhất của một đồ thị có n đỉnh sẽ có n-1 cạnh. Trong trường hợp này, đồ thị G có 6 đỉnh (V = {1,2,3,4,5,6}), do đó cây khung nhỏ nhất của G sẽ có 6 - 1 = 5 cạnh.

Câu hỏi liên quan