Câu hỏi
A B A D E D C C a) b) Hinh 2.23
Giải pháp
3.8
(205 Phiếu)
Quân Thành
thầy · Hướng dẫn 5 năm
Trả lời
Lời giải: - Đồ thị Hình 2.23 a) có 5 đỉnh, trong đó đỉnh A và B đều có bậc 3, các đỉnh còn lại E, D, C đều có bậc 2 nên mỗi đỉnh đều có bậc không nhỏ hơn
. Do đó, theo định lí 4 (suy ra từ định lí Dirac), đồ thị này có đường đi Hamilton. Một đường đi Hamilton của đồ thị này là CBDAE. - Đồ thị Hình 2.23 b) có 4 đỉnh, mỗi đỉnh đều có bậc là 3 nên mỗi cặp đỉnh không kề nhau bất kì đều có tổng bậc là 3 + 3 = 6 > 4. Do đó, theo định lí Ore, đồ thị này có một chu trình Hamilton nên nó có đường đi Hamilton. Một đường đi Hamilton của đồ thị này là ABCD.