Tiếng Việt
English
中文
Français
日本語
한국어
Español
Русский
Deutsch
ไทย
ລາວ
हिन्दी
Português
Bài toán đường đi Hamilton trong kỳ thi IMSO 2018
24/1/2019, 00:00
Lượt đọc : 2.076
Từ tháng 1 năm 2019, chúng tôi sẽ sưu tầm những bài toán hay để thầy và trò cùng nhau "thư giãn" sau những tiết học căng thẳng. Sau đây là bài toán đường đi Hamilton trong kỳ thi IMSO 2018.
Đường đi Hamilton có nguồn gốc từ bài toán: "Xuất phát từ một đỉnh của khối thập nhị diện đều, hãy đi dọc theo các cạnh của khối đó sao cho đi qua tất cả đỉnh khác, mỗi đỉnh đúng một lần sau đó quay về đỉnh xuất phát", được gọi theo tên của nhà Toán học người Ireland William Rowan Hamilton (1805-1865).
Một đồ thị Hamilton có ít nhất một đường đi Hamilton. Đường đi Hamilton có ý nghĩa thực tiễn khi cần xác định lộ trình du lịch tối ưu tham quan hết n địa điểm du lịch mà không cần phải đi hết các đường đi kết nối. Sau đây là một bài toán thú vị về đồ thị Hamilton trong kỳ thi IMSO 2018
Problem: A regular octahedron is shown in the diagram below. There are 6 vertices altogether connected by a total of 12 edges. An ant starts from vertex A and moves along any edge but cannot go through any edge more than once. If the ant visits each vertex exactly once before it returns to vertex A, how many different routes are there?
 |
Dịch đề: Cho một khối bát diện đều như hình vẽ. Bát diện có 6 đỉnh được nối với nhau bằng 12 cạnh. Một con kiến bắt đầu đi từ đỉnh A và đi trên các cạnh, nhưng không được đi cạnh nào quá 1 lần. Biết con kiến đã đi qua mỗi đỉnh đúng 1 lần trước khi quay trở về đỉnh A. Hỏi có bao nhiêu đường đi thỏa mãn?
Tin cùng chuyên mục
Kinh nghiệm ôn thi Tiếng Anh THPT đạt kết quả cao
Các thí sinh từng đạt 10 điểm tuyệt đối môn Tiếng Anh trong các kỳ thi tốt nghiệp THPT chia sẻ phương pháp học, ôn luyện môn này khoa học, hiệu quả.Học liệu điện tử
Sở GD&ĐT Thành phố Hà Nội Hệ thống học và thi trực tuyến HanoiStudy
5 cách ghi nhớ cụm động từ hiệu quả
Học cụm động từ theo chủ đề, nhóm, ngữ cảnh, tiểu từ hay kể chuyện sẽ giúp ghi nhớ chúng tốt hơn, theo cô Tạ Thị Hải Quỳnh, giáo viên tiếng Anh ở Vĩnh Phúc.
Tám cách học giúp thành thạo ngoại ngữ nhanh chóng
Không chỉ là luyện ngữ pháp, từ mới, người học ngoại ngữ nên học cách suy nghĩ bằng ngôn ngữ mới, chấp nhận và tận dụng sai lầm để nhanh tiến bộ.
