728x90 AdSpace

Theo dõi và chia sẻ các bài viết mới
Tin nhanh

Bài toán chu trình Hamilton - THPT Chuyên Lê Quý Đôn Bình Định

Một nhóm học sinh khóa 17 trường THPT Chuyên Lê Quý Đôn Bình Định đã gửi tặng VietMaths một số tài liệu toán tự biên soạn khá là hay, với lời nhắn chúc cho website thành công và giúp ích cho thật nhiều người đọc nữa. Hôm nay, chúng tôi xin trích đăng giới thiệu tài liệu thứ nhất: Bài toán chu trình Hamilton để mọi người biết thêm.
Bài khá hay: Các bài toán đội nón và toán học giải trí Đặng Nguyễn Đức Tiến từ Trento Italy
Năm  1856, một nhà toán học nổi tiếng người Anh là Willian Rewan Hamilton mang đến một trò chơi với tên gọi “ Đi vòng quanh thế giới “. Ông ấy biểu thị 20 thành phố lớn bởi 20 đỉnh của một khối thập nhị diện đều. Bạn phải đi dọc theo các cạnh đến từng thành phố, mỗi thành phố một lần và cuối cùng trở về điểm xuất phát.
Trò chơi này sau đó được chào đón trên toàn thế giới. Và trong trò chơi này, chúng ta thấy có một chuỗi mà nó đi qua các đỉnh chỉ một lần và chúng ta gọi nó là chuỗi Hamilton ( hay là chu trình Hamilton). Nếu 1 đồ thị chứa 1 chu trình Hamilton thì sẽ được gọi là đồ thị Hamilton.
Mới nhìn qua,  chu trình Hamilton dường như giống với bài toán Euler, nhưng trên thực tế, chúng lại khác ở bản chất. Và bài toán về chu trình Hamilton này là một trong những bài toán khó nhất trong lý thuyết đồ thị và chưa có lời giải. Đến tận ngày nay, chúng ta chưa thể tìm được điều kiện cần và đủ để kiểm tra nó. Vì thế chúng ta cần có một phương pháp khác cho bài toán mới này. Chúng tôi sẽ sử dụng một vài ví dụ dưới đây để minh họa.
Ví dụ 1:  Hình 6.1 có chứa chu trình Hamilton hay không?
hình chứa chu trình Hamilton, hinh chua chu trinh hamilton
Lời giải:   Như chúng ta thấy trên hình 6.1, dựa theo các số sẽ giúp cho chúng ta tìm được chu trình Hamilton.
Ở đây chúng ta sử dụng phương pháp tìm kiếm trực tiếp để giải bài toán. Đó là từ một đỉnh ban đầu, tìm kiếm từng đỉnh một để xem xem có chu trình Hamilton hay không. Và nếu chúng ta tìm được một chuỗi thì coi như đã giải quyết xong bài toán. Nếu không thì không tồn tại lời giải( không chứa chu trình). Cách này luôn luôn có thể sử dụng trong những đồ thị đơn giản hoặc trong những đồ thị có bao hàm chu trình Hamilton.
Ví dụ 2: Trong một cuộc hội nghị toán học quốc tế, có 7 nhà toán học đến từ những nước khác nhau, và ngôn ngữ mà họ có thể nói là :
A: Tiếng Anh
B: Tiếng Anh và Trung Quốc
C: Tiếng Anh, Ý và Tây Ban Nha
D: Tiếng Trung Quốc và Nhật Bản
E: Tiếng Đức và Ý
F: Tiếng Pháp, Nhật Bản và Tây Ban Nha
G: Tiếng Pháp và Đức
Hỏi có cách xếp 7 nhà toán học xung quanh một bàn sao cho ai cũng có thể nói chuyện được với người bên cạnh của mình?
Lời Giải: Ta biểu diễn 7 nhà toán học thành 7 đỉnh A,B,C,D,E,F,G. Nếu hai người cùng nói một ngôn ngữ, ta nối các đỉnh đại diện cho họ và chúng ta có được đồ thị G. Nhìn vào hình 6.2, bài toán xếp chỗ ngồi trở thành bài toán tìm một chu trình Hamilton. Sắp xếp chỗ ngồi theo thứ tự chu trình Hamilton, vì thế mọi người có thể nói chuyện với người bên cạnh của mình.
Ghi chú: Ch là tiếng Trung Quốc, En là tiếng Anh, Fr là tiếng Pháp, Ge là tiếng Đức, It là Ý, Ja là tiếng Nhật, Sp là tiếng Tây Ban Nhà.
hình vẽ bài toán Hamilton, hinh ve bai toan hamilton

Trong hình 6.2 chúng ta vẽ một chu trình theo các dòng( chắc là theo các đường nối hoặc là cạnh) và sau đó chúng ta có được lời giải, điều đó cũng có nghĩa là nếu chúng ta có thể sắp xếp chỗ ở(theo) thứ tự A,B,C,D,E,F,G thì mọi người có thể nói chuyện với người bên cạnh họ. Chung ngôn ngữ là tách dấu với mỗi cạnh tương ứng trong hình 6.3.
Ví dụ 3. Hãy Xác Định xem đồ thị G trong hình 6.4 có chứa một chuỗi hay một Chu trình Hamiltonian không?
hình vẽ biểu diễn bài toán chu trình Hamilton, bai toan chu trinh hamilton
Lời giải: Chúng ta kí hiệu một đỉnh trong Graph G là A. Ví dụ, chúng ta kí hiệu đỉnh a là A và tất cả các đỉnh kề với đỉnh a là B, đỉnh kề với đỉnh B là A. sau đó chúng ta kí hiệu các đỉnh kề với đỉnh mà đã được kí hiệu B là A và các đỉnh kề với đỉnh mà được kí hiệu A là B cho đến khi chúng ta kí hiệu tất cả các đỉnh. Giống như hình 6.5 cho chúng ta thấy, Nếu G chứa một chu trình Hamiltonian, chu kì phải đi qua A và B lần lượt. Vì vậy sự khác biệt giữa số lượng của các đỉnh kí hiệu A và các đỉnh kí hiệu B là không nhiều hơn 1. Nhưng hình 6.5 có 9 đỉnh A và 7 đỉnh B. Sự khác biệt là 2, vì vậy không có chuỗi hoặc chu trình Hamiltonian.
Nói chung với một đồ thị lưỡng phân $G=(V_1, V_2, E)$ có một cách đơn giản để xem xét Graph có chứa một chuỗi Hamiltonian hoặc một chu trình Hamiltonian.
Định Lý 1: Cho một đồ thị lưỡng phân $G=(V_1, V_2, E)$. Nếu $|V_1 |≠|V_2 |$, đồ thị G trên không thể chứa chu trình Hamiltonian. Nế sự khác biệt giữa $|V_1 |$ và $|V_2 |$ là nhiều hơn 1. Đồ thị G không thể chứa Đường đi Hamiltonian.
Ví Dụ 4: Cho một nửa bàn cờ vua như trong hình 6.6. 1 quân mã đang ở tại ô góc dưới bên phải. Câu hỏi đặt ra là liệu quân mã có thể đi hết tất cả các ô trên bàn cờ trong một lượt đi hay không? Và khi xóa đi 2 ô màu đen ở 2 góc bàn cờ thì chuyện gì sẽ xảy ra?
 Lời giải:  Chúng ta sẽ xét đồ thị sau: xem các ô vuông trên nửa bàn cờ như các đỉnh trên 1 đồ thị. Nếu quân mã có thể đi từ ô này đến ô khác trong 1 bước đi, ta sẽ nối 2 đỉnh đại diện cho 2 ô tương ứng trên bàn cờ lại với nhau. Ta sẽ chuyển bài toán sang việc xác định xem liệu đồ thị có chứa dây truyền Hamiltonian hay không? Trong đồ thị, 2 đỉnh được gọi là kề nhau nếu chúng được xác định bằng cách di chuyển của quân Mã tưc là 2 đỉnh này nằm ow vị trí đầu và cuối của khối 1x3 chữ L (). Tô màu từng đỉnh của đồ thị bằng màu tương ứng của các ô vuông trên bàn cờ, khi đó màu của 2 đỉnh kề nhàu luôn khác nhau. Như vậy giữa 2 đỉnh kề nhau trong đồ thị luôn có 1 đỉnh được tô màu đen, 1 đỉnh tô màu trắng. Vì số đỉnh màu trắng và số đỉnh màu đen là như nhau nên sẽ tồn tại dây truyền Hamiltonian.
ban co vua trong chu trinh hamilton
 Bây giờ chúng ta sẽ xem xét vấn đề thứ hai của bài toán này. Một lần nữa, chúng ta lại dùng các tương tự như trên để chuyển bài toán sang việc xác định xem đồ thị này có chứa dây chuyền Hamilton hay không? Sô ô vuông màu đen là 14, còn số ô vuông màu trắng là 16. Theo định lý 1 ta xác định đồ thị này không thể chứa dây chuyền Hamiltonian. Điều đó có nghĩa là quân Mã sẽ không thể đi hết toàn bộ bàn cờ trong một lượt đi nếu ta xóa đi 2 ô đen ở hai góc.
bai toan ve chu trinh hamiltonian
Cho đến bây giờ chúng ta vẫn chưa biết được điều kiện cần và đủ của bài toán Hamiltonian. Chỉ có thể là liệu một đồ thị liên thong có chứa chu trình (hay dây truyền) Hamilton hay không? Mặc dù các nhà toán học ở các thế hệ đầu tiên đã nghiên cứu hơn 1 thế kỉ, nhưng họ cũng chỉ tìm được vài điều kiện cần và vài điều kiện đủ  để xác định bài toán Hamiltonian. Trong phần tiếp theo, chúng tôi sẽ đưa ra 1 điều kiện đủ cho bài toán Hamilton rằng liệu đồ thị đơn có chứa dây truyền Hamiltonian hay không?

Trên đây là một vài thí dụ, nhằm giới thiệu về tài liệu mà một nhóm bạn học sinh chuyên toán trường Lê Quý Đôn Bình Định, bạn đọc tải về File đầy đủ: Download Hamilton's Problem
Bài toán chu trình Hamilton - THPT Chuyên Lê Quý Đôn Bình Định Reviewed by Tân Phúc on 05:52:00 Rating: 5 Một nhóm học sinh khóa 17 trường THPT Chuyên Lê Quý Đôn Bình Định đã gửi tặng VietMaths một số tài liệu toán tự biên soạn khá là hay, vớ...

Không có nhận xét nào:

Xin vui lòng để lại vài dòng nhận xét hoặc đánh giá có nội dung. Sự quan tâm, chia sẻ của quý độc giả sẽ tạo ra những trải nghiệm tuyệt vời cho cộng đồng bạn đọc cả nước.