JavaScript is required

Số đỉnh bậc lẻ trong đồ thị G vô hướng:

A.

Phụ thuộc vào số đỉnh của đồ thị.

B.

Là một số lẻ

C.

Là một số chẵn.

D.

Phụ thuộc vào số cạnh của đồ thị.

Trả lời:

Đáp án đúng: C


Định lý: Trong một đồ thị vô hướng, tổng bậc của tất cả các đỉnh bằng hai lần số cạnh của đồ thị. Gọi V là tập hợp các đỉnh của đồ thị G. Ta có: ∑deg(v) = 2|E|, với v ∈ V, trong đó |E| là số cạnh của đồ thị. Tổng bậc của các đỉnh luôn là một số chẵn. Giả sử V_l là tập hợp các đỉnh bậc lẻ và V_c là tập hợp các đỉnh bậc chẵn. Ta có: ∑deg(v) = ∑deg(v_l) + ∑deg(v_c) = 2|E|, với v ∈ V, v_l ∈ V_l, v_c ∈ V_c Vì ∑deg(v_c) là một số chẵn, nên ∑deg(v_l) cũng phải là một số chẵn để tổng của chúng là một số chẵn. Để ∑deg(v_l) là một số chẵn, số lượng các đỉnh bậc lẻ (|V_l|) phải là một số chẵn, vì mỗi deg(v_l) là một số lẻ. Do đó, số đỉnh bậc lẻ trong đồ thị vô hướng G là một số chẵn. Vậy đáp án đúng là C.

Câu hỏi liên quan