Tiêu đề Chuyên đề 37_Đường đi Euler và đường đi Hamiton_Lời giải_TLN.docx ✅

b) Các con số trong sơ đồ ở Hình 2.28 có thể là thời gian để đi dọc con đường đó, hoặc là chi phí khi đi hết con đường đó,. Bởi vậy, ta có thể sử dụng thuật toán giải quyết bài toán gốc về bài toán tìm đường đi ngắn nhất để giải quyết bài toán tìm đường đi nhanh nhất hoặc đường đi có chi phí rẻ nhất,. 4. BÀI TOÁN NGƯỜI ĐƯA THƯ Bài toán người đưa thư phát biểu như sau: Một người đưa thư xuất phát từ bưu điện phải đi qua một số con đường để phát thư rồi quay lại điểm xuất phát, hỏi người đó phải đi như thế nào để đường đi là ngắn nhất. Ở đây các điểm cần phát thư nằm dọc theo các con đường cần phải đi qua. Trong bài toán này, người đưa thư sẽ phải đi trên mỗi con đường ít nhất một lần (để phát được thư cho các điểm cần phát nằm dọc theo con đường đó) và cuối cùng quay lại vị trí xuất phát. Ngoài ra, cần đảm bảo quãng đường phải đi là nhỏ nhất có thể. Trong ngôn ngữ của lí thuyết đồ thị, bài toán người đưa thư tương đương với bài toán tìm chu trình ngắn nhất đi qua tất cả các cạnh của một đồ thị cho trước. Bài toán này có thể phát biểu dưới dạng một đồ thị có trọng số, ở đó đồ thị ứng với hệ thống các con đường, và trọng số của mỗi cạnh là độ dài của con đường tương ứng. Các cạnh của đồ thị này mô tả các con đường cần phải đi qua, các đỉnh của đồ thị là điểm đầu và điểm cuối của các con đường đó (và có thể không phải là điểm cần phát thư). Khi đó ta cần tìm một chu trình có tổng trọng số nhỏ nhất và chứa mỗi cạnh ít nhất một lần. Trong trường hợp tổng quát, nói chung đây là một bài toán khá phức tạp. Trong mục này, ta chỉ xét hai tình huống đơn giản (liên quan đến đồ thị có trọng số, liên thông): 1) Tất cả các đỉnh của đồ thị đều có bậc chẵn. Khi đó đồ thị có chu trình Euler và chu trình Euler đó chính là một đường đi yêu cầu. 2) Chỉ có đúng hai đỉnh của đồ thị có bậc lẻ. Khi đó ta có thể tìm một đường đi Euler từ đỉnh bậc lẻ này đến đỉnh bậc lẻ kia, sau đó dùng thuật toán ở Mục 1 tìm đường đi ngắn nhất để quay trở lại đỉnh xuất phát. Kết hợp hai đường đi đó, ta được lời giải của bài toán đã cho. Dưới đây ta xét hai ví dụ minh hoạ cho hai trường hợp này. Ví dụ 2. Cho đồ thị có trọng số như Hình 2.30. Chứng tỏ rằng đồ thị có chu trình Euler và hãy tìm một chu trình Euler xuất phát từ đỉnh A . Giải Vì đồ thị là liên thông và các đỉnh đều có bậc chẵn (ở đây đều là bậc 4) nên đồ thị có chu trình Euler. Một chu trình Euler xuất phát từ đỉnh A là ABCBECDEADA . Chú ý. Nếu đồ thị có chu trình Euler thì độ dài quãng đường phải đi trong lời giải của bài toán người đưa thư chính là tổng các trọng số gắn trên các cạnh của đồ thị.