Bài toán người đưa thư

Cách giải bài toán người đưa thư trong lý thuyết đồ thị

Bài toán người đưa thư là một trong những bài toán kinh điển của Lý thuyết đồ thị, gắn liền với khái niệm đường đi Euler và các bài toán tối ưu trong thực tế. Thông qua chuyên đề này, học sinh Toán 11 không chỉ hiểu sâu hơn về đồ thị mà còn biết cách vận dụng kiến thức để giải quyết các bài toán liên quan đến lộ trình ngắn nhất, giao hàng và quản lý mạng lưới giao thông.

Bài toán người đưa thư là gì?

Trong ngôn ngữ của lí thuyết đồ thị, bài toán người đưa thư tương đương với 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 đưa 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:

• 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.
• 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 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 cho bài toán đã cho.

Ví dụ minh họa bài toán người đưa thư

Hướng dẫn giải

Vì đồ thị là liên thông và các đỉnh đều có bậc chẵn (ở đây 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ị.

Hướng dẫn giải

Đồ thị chỉ có hai đỉnh bậc lẻ là \(A\) và \(D\) nên ta có thể tìm được một đường đi Euler từ \(A\) và \(D\) (đường đi này đi qua mỗi cạnh đúng một lần).

Một đường đi Euler đi từ \(A\) và \(D\)  là \(AEABEDBCD\) và tổng độ dài của nó là:

\(6 + 8 + 1 + 7 + 5 + 4 + 2 + 3 = 36\)

Để quay lại điểm xuất phát và có đường đi ngắn nhất, ta cần tìm một đường đi ngắn nhất từ \(D\) đến \(A\) theo thuật toán đã được mô tả ở mục trước.

Đường đi ngắn nhất từ \(D\) đến \(A\) là \(DAB\) và có độ dài là \(4 + 1 = 5\).

Vậy một chu trình cần tìm là: \(AEABEDBCDBA\) và có độ dài là \(36 + 5 = 41\).

📥 Để xem trọn vẹn nội dung và ví dụ minh họa, bạn vui lòng tải tài liệu tham khảo tại đây.

--------------------------------

FAQ – Bài Toán Người Đưa Thư

1. Vì sao bài toán người đưa thư được gọi là bài toán thực tế?

Bài toán mô phỏng công việc của người phát thư phải đi qua tất cả các tuyến đường trong khu vực để giao thư nhưng vẫn muốn tiết kiệm thời gian và quãng đường di chuyển.

Mô hình này còn được áp dụng trong giao hàng, thu gom rác và kiểm tra hệ thống giao thông.

2. Bài toán người đưa thư liên quan đến kiến thức nào trong Toán 11?

Chuyên đề này liên quan trực tiếp đến:

• Đồ thị vô hướng.
• Bậc của đỉnh.
• Đường đi Euler.
• Chu trình Euler.
• Tối ưu hóa lộ trình.

Đây là nội dung quan trọng của chương Lý thuyết đồ thị.

--------------------------------------

Bài toán người đưa thư là chuyên đề tiêu biểu của Lý thuyết đồ thị Toán 11, giúp học sinh tiếp cận các bài toán tối ưu hóa và ứng dụng thực tế của toán học. Nắm vững đường đi Euler, chu trình Euler và phương pháp tìm hành trình tối ưu sẽ giúp các em giải tốt các dạng bài tập từ cơ bản đến nâng cao, đồng thời phát triển tư duy logic và khả năng mô hình hóa bài toán.