Một người đưa thư xuất phát từ bưu điện (vị trí A) và phải đi qua các địa điểm B, C, D để phát thư rồi quay trở lại bưu điện. Sơ đồ các địa điểm và thời gian di chuyển giữa các địa điểm được mô tả như hình bên dưới (đơn vị phút). Tính thời gian ít nhất mà người đưa thư cần để hoàn thành công việc.

Nam và ba người bạn lên kế hoạch cho một chuyến đi phượt xuyên Việt, ghé thăm $4$ thành phố: Hà Nội, Đà Nẵng, Thành phố Hồ Chí Minh (TP.HCM) và Cần Thơ. Họ xuất phát từ Hà Nội, đi qua tất cả các thành phố còn lại đúng một lần rồi quay về Hà Nội. Bảng chi phí nhiên liệu (tính bằng lít xăng) giữa các thành phố như sau:



Xe của nhóm hiện đã có sẵn $150$ lít xăng. Để hoàn thành hành trình, họ cần đổ thêm ít nhất bao nhiêu lít xăng?

Công ty giao hàng nhanh có $4$ kho hàng $A,B,C$ và $D$. Quản lý muốn lên kế hoạch cho xe giao hàng đi qua tất cả các kho hàng để lấy hàng và quay lại kho hàng ban đầu, với điều kiện là mỗi kho hàng chỉ ghé qua một lần. Khoảng cách giữa các kho hàng (km) được mô tả trong hình bên. Quãng đường ngắn nhất để xe giao hàng hoàn thành việc lấy hàng ở các kho và quay trở lại kho hàng ban đầu là bao nhiêu?

Trong kì nghỉ hè bạn Phong muốn đi du lịch qua các địa điểm du lịch $A,B,C,D,E$ như hình vẽ. Khoảng cách giữa các địa điểm du lịch như sau $AB=16,BC=17,CD=11,DE=15,EA=14,AC=6,CE=20,EB=5,BD=3,DA=9$ (đơn vị là km). Biết rằng số tiền bạn Phong phải trả cho $1\text{ km}$ là $15000$ đồng. Giả sử rằng bạn Phong xuất phát từ điểm $A$ đi qua các điểm $B,C,D,E$ đúng một lần sau đó trở về điểm $A$. Số tiền bạn Phong phải trả thấp nhất là bao nhiêu (kết quả làm tròn đến hàng nghìn)?

Cho một đồ thị gồm có 6 đỉnh được nối với nhau bằng 12 cạnh (như hình vẽ dưới). Giả sử có một con kiến bắt đầu đi từ đỉnh $A$ và đi trên các cạnh, nhưng không được đi cạnh nào quá 1 lần. Biết con kiến đó đi qua mỗi đỉnh đúng 1 lần trước khi quay trở về đỉnh $A$. Hỏi có bao nhiêu đường đi thỏa mãn?

Câu 4. Một công ty vận tải cần giao hàng đến tất cả các thành phố $A,B,C,D,E$ (hình vẽ bên dưới). Chi phí di chuyển giữa các thành phố được mô tả trên hình (đơn vị tính: triệu đồng). Xe giao hàng của công ty xuất phát từ một thành phố trong năm thành phố trên đi qua tất cả các thành phố còn lại đúng một lần sau đó trở lại thành phố ban đầu. Tìm chi phí thấp nhất của xe giao hàng.

Một người đưa thư xuất phát từ bưu điện (vị trí $A$) và phải đi qua các địa điểm $B,C,D$ để phát thư (mỗi địa điểm chỉ qua một lần) rồi quay lại bưu điện. Sơ đồ các địa điểm cần đi và thời gian (đơn vị: phút) di chuyển qua lại giữa các điểm được mô tả ở hình vẽ bên dưới. Thời gian đi ít nhất của người đưa thư là bao nhiêu phút?
[IMAGE:img_p3_q3]