tailieunhanh - MỘT SỐ BÀI TOÁN VỀ ĐƯỜNG ĐI

Bài toán 7 cây cầu ở Königsberg: Thành phố Königsberg thuộc Phổ (bây giờ gọi là Kaliningrad thuộc Cộng hòa Liên bang Nga) được chia thành bốn vùng bằng các nhánh sông Pregel. Các vùng này gồm 2 vùng bên bờ sông, đảo Kneiphof và một miền nằm giữa 2 nhánh của sông Pregel. Vào thế kỷ thứ XVIII, người ta đã xây 7 cây cầu nối các vùng lại với nhau như sơ đồ sau: | CHƯƠNG II CÁC BÀI TOÁN VỀ ĐƯỜNG ĐI I. Chu trình và đường đi Euler 1. Bài toán mở đầu 2. Đinh nghĩa 3. Chu trình và đường đi Euler trong đồ thi vô hướng 4. Chu trình và đường đi Euler trong đồ thi có hướng II. Chu trình và đường đi Hamilton 1. Chu trình Hamilton 2. Phương pháp tìm chu trình Hamilton 3. Đường đi Hamilton III. Bài toán đường đi ngắn nhất 1. Mở đầu 2. Thuât toán tìm đường đi ngắn nhất IV. Thuât toán Hedetniemi 1. Phép công ma trân Hedetniemi 2. Thuât toán Hedetniemi I. Chu trình và đường đi Euler 1. Bài toán mở đầu Bài toán 7 cây cầu ở Königsberg Thành phố Königsberg thuôc Phổ bây giờ gọi là Kaliningrad thuôc Công hòa Liên bang Nga được chia thành bốn vùng bằng các nhánh sông Pregel. Các vùng này gồm 2 vùng bên bờ sông đảo Kneiphof và môt miền nằm giữa 2 nhánh của sông Pregel. Vào thế kỷ thứ XVIII người ta đã xây 7 cây cầu nối các vùng lại với nhau như sơ đồ sau Vào chủ nhật người dân ở đây thường đi bộ dọc theo các vùng trong thành phố. Họ tự hỏi Cớ thể xuất phát tại một điểm nào đó trong thành phố đi qua tất cả 7 cây cầu mỗi cây một lần rồi trở về điểm xuất phát được không Nhà toán học Thụy Sĩ Leonard Euler đã nghiên cứu giải bài toán này. Lời giải của ông được công bố năm 1736. Bài toán này có thể được coi là một trong những ứng dụng đầu tiên của lý thuyết đồ thị. Ta có thể xây dựng đồ thị G V E mô tả bài toán như sau Đỉnh Lấy các điểm trên mặt phẳng hay trong không gian tương ứng với các vùng đất trong sơ đồ. Đối tượng của bài toán ở đây là một vùng đất trong sơ đồ. Vậy mỗi đỉnh biểu diễn cho một vùng đất. Đồ thị G sẽ có 4 đỉnh A B C D tương ứng với 4 vùng đất. Cạnh Trong đồ thị G các đỉnh và được nối với nhau bằng một cạnh e đại diện cho một chiếc cầu nối giữa hai vùng đất. Đồ thị G sẽ có 7 cạnh tương ứng với 7 chiếc cầu nối giữa các vùng đất trong sơ đồ. Euler đã nghiên cứu bài toán này mô hình nó bằng một đa đồ thị bốn vùng được biểu diễn bằng 4 đỉnh các cầu là các cạnh như đồ thị sau Bài toán tìm đường đi qua tất cả các cầu mỗi cầu không quá .