Câu hỏi:
12/07/2024 817Cá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?
Sách mới 2k7: 30 đề đánh giá năng lực DHQG Hà Nội, Tp. Hồ Chí Minh, BKHN 2025 mới nhất (600 trang - chỉ từ 140k).
Quảng cáo
Trả lờ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.
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Mỗi đồ thị sau đây có chu trình Euler không? Nếu có, hãy chỉ ra một chu trình như vậy.
Câu 2:
Đồ thị sau có đường đi Euler không? Nếu có, hãy chỉ ra một đường đi như vậy.
Câu 3:
a) Chỉ ra một chu trình Euler của đồ thị G ở Hình 5. Đồ thị này có đỉnh nào bậc lẻ không?
b) Chỉ ra rằng các đồ thị S và T sau đây không có chu trình Euler. Các đồ thị này có đỉnh bậc lẻ không?
Câu 5:
Đồ thị ở Hình 24 có đường đi Euler không? Nếu có hãy chỉ ra một đường đi như vậy.
Câu 7:
Mỗi đồ thị trong Hình 23 có chu trình Euler không? Nếu có hãy chỉ ra một chu trình như vậy.
về câu hỏi!