Các đỉnh của đồ thị ở Hình 22 biểu thị các điểm du lịch trong một thành phố

Giải Chuyên đề Toán 11 Chân trời sáng tạo Bài 2: Đường đi Euler và đường đi Hamilton

Vận dụng 2 trang 58 Chuyên đề Toán 11: Các đỉnh của đồ thị ở Hình 22 biểu thị các điểm du lịch trong một thành phố, các cạnh biểu thị đường đi giữa các điểm du lịch này. Có hay không một cách đi tham quan tất cả các điểm du lịch của thành phố, mỗi điểm qua đúng một lần, xuất phát và kết thúc tại cùng một điểm du lịch?

Lời giải:

Đồ thị ở Hình 22 có các đỉnh B, K có bậc 2.

Suy ra chu trình Hamilton h (nếu có) phải đi các các cạnh AB, BC, AK, KI.

Do đó h không thể đi qua các cạnh AI, AD, AD, AE.

Nếu xóa đi bốn cạnh trên thì các đỉnh A, D trở thành bậc 2.

Suy ra h phải đi qua các cạnh AB, AK, DC, DF.

Do đó h không thể đi qua các cạnh CE, CF.

Nếu xóa đi thêm hai cạnh trên thì đỉnh E trở thành bậc 2.

Suy ra h phải đi qua các cạnh EI, EF.

Vì vậy ta được chu trình Hamilton h: ABCDFEIKA.

Vậy có cách đi tham quan tất cả các điểm du lịch của thành phố, mỗi điểm qua đúng một lần, xuất phát và kết thúc tại cùng một điểm du lịch.