Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Cho một hình thập nhị diện đều (đa diện đều có 12 mặt, 20 đỉnh và 30 cạnh), mỗi đỉnh của hình mang tên một thành phố nổi tiếng, mỗi cạnh của hình (nối hai đỉnh) là đường đi lại giữa hai thành phố tương ứng. Xuất phát từ một thành phố, hãy tìm đường đi thăm tất cả các thành phố khác, mỗi thành phố chỉ một lần, rồi trở về chỗ cũ. | ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON - PHẦN 2 ĐƯỜNG ĐI HAMILTON VÀ ĐỒ THỊ HAMILTON. Năm 1857 nhà toán học người Ailen là Hamilton 1805-1865 đưa ra trò chơi đi vòng quanh thế giới như sau. Cho một hình thập nhị diện đều đa diện đều có 12 mặt 20 đỉnh và 30 cạnh mỗi đỉnh của hình mang tên một thành phố nổi tiếng mỗi cạnh của hình nối hai đỉnh là đường đi lại giữa hai thành phố tương ứng. Xuất phát từ một thành phố hãy tìm đường đi thăm tất cả các thành phố khác mỗi thành phố chỉ một lần rồi trở về chỗ cũ. Trước Hamilton có thể là từ thời Euler người ta đã biết đến một câu đố hóc búa về đường đi của con mã trên bàn cờ . Trên bàn cờ con mã chỉ có thể đi theo đường chéo của hình chữ nhật 2 x 3 hoặc 3 x 2 ô vuông. Giả sử bàn cờ có 8 x 8 ô vuông. Hãy tìm đường đi của con mã qua được tất cả các ô của bàn cờ mỗi ô chỉ một lần rồi trở lại ô xuất phát. Bài toán này được nhiều nhà toán học chú ý đặc biệt là Euler De Moivre Vandermonde . Hiện nay đã có nhiều lời giải và phương pháp giải cũng có rất nhiều trong đó có quy tắc mỗi lần bố trí con mã ta chọn vị trí mà tại vị trí này số ô chưa dùng tới do nó khống chế là ít nhất. Một phương pháp khác dựa trên tính đối xứng của hai nửa bàn cờ. Ta tìm hành trình của con mã trên một nửa bàn cờ rồi lấy đối xứng cho nửa bàn cờ còn lại sau đó nối hành trình của hai nửa đã tìm lại với nhau. Trò chơi và câu đố trên dẫn tới việc khảo sát một lớp đồ thị đặc biệt đó là đồ thị Hamilton. 4.2.1. Định nghĩa Chu trình t.ư. đường đi sơ cấp chứa tất cả các đỉnh của đồ thị vô hướng hoặc có hướng G được gọi là chu trình t.ư. đường đi Hamilton. Một đồ thị có chứa một chu trình t.ư. đường đi Hamilton được gọi là đồ thị Hamilton t.ư. nửa Hamilton . Thí dụ 3 1 Đồ thị Hamilton hình thập nhị diện đều biểu diẽn trong mặt phẳng với chu trình Hamilton A B C D E F G H I J K L M N O P Q R S T A đường tô đậm . 2 Trong một đợt thi đấu bóng bàn có n n 2 đấu thủ tham gia. Mỗi đấu thủ gặp từng đấu thủ khác đúng một lần. Trong thi đấu bóng bàn chỉ có khả năng thắng hoặc thua.
