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). Chi phí di chuyển giữa các thành phố được mô tả trên hình (tính theo đơn vị nghìn đồng). Xe giao hàng của công ty xuất phát từ thành phố $A$ đ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ố $A$. Tìm chi phí thấp nhất của xe giao hàng (tính theo đơn vị nghìn đồng)?

(AI giải đề cho tôi)
Đồ thị có các cạnh: AB=900, AE=1000, AD=1100, BE=800, BC=1400, EC=1200, DC=1300, DE=1400. Liệt kê các chu trình Hamilton xuất phát từ A (do đối xứng chỉ cần xét một chiều):
- A-B-E-C-D-A: 900+800+1200+1300+1100 = 5300
- A-B-E-D-C-A: 900+800+1400+1300+1000 = 5400
- A-B-C-E-D-A: 900+1400+1200+1400+1100 = 6000
- A-B-C-D-E-A: 900+1400+1300+1400+1000 = 6000
- A-E-B-C-D-A: 1000+800+1400+1300+1100 = 5600
- A-D-E-B-C-A: 1100+1400+800+1400+1000 = 5700
Các thứ tự khác hoặc trùng đảo chiều hoặc không tồn tại cạnh nối. Vậy chi phí thấp nhất là 5300 nghìn đồng (quãng đường A→B→E→C→D→A).