Cho đồ thị vô hướng G = (V, E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E ={(1,2),(1,3),(1,6),(2,3),(2,5),(2,6),(4,5),(4,6),(5,6),(1,5)}. Hỏi chu trình nào dưới đây là chu trình Hamilton?
Trả lời:
Đáp án đúng: A
Chu trình Hamilton là chu trình đi qua tất cả các đỉnh của đồ thị đúng một lần, trừ đỉnh đầu tiên (cũng là đỉnh cuối cùng).
Xét từng phương án:
- Phương án A: 1 – 3 – 2 – 5 – 4 – 6 – 1. Chu trình này đi qua tất cả các đỉnh {1, 2, 3, 4, 5, 6} mỗi đỉnh đúng một lần (trừ đỉnh 1 lặp lại ở cuối). Đây là một chu trình Hamilton.
- Phương án B: 1 – 2 – 3 – 1 – 5 – 4 – 6 – 1. Đỉnh 1 xuất hiện 3 lần, đỉnh 5, 4, 6 mỗi đỉnh xuất hiện 1 lần, đỉnh 2, 3 xuất hiện 1 lần, không phải chu trình Hamilton.
- Phương án C: 3 – 2 – 1 – 5 – 2 – 6 – 5 – 4 – 6 – 1. Các đỉnh 2, 5, 6 xuất hiện nhiều hơn 1 lần. Không phải chu trình Hamilton.
Vậy, phương án A là đáp án đúng.
