Bạn An xuất phát từ thư viện $T$, cần đến thăm các trường $A, B, C, D$ (mỗi nơi đúng một lần) rồi quay về $T$. Khoảng cách (km): TA=9, TB=2, TC=9, TD=11, AB=9, AC=9, AD=12, BC=12, BD=5, CD=5. Gọi $L$ là độ dài nhỏ nhất của hành trình khép kín. Hỏi có bao nhiêu hành trình khép kín KHÁC NHAU có độ dài bằng $L$? (Hai hành trình chỉ khác nhau về chiều đi được coi là MỘT.)
ĐÁP ÁN
1
LỜI GIẢI
Bước 1 — Tìm độ dài nhỏ nhất $L$.
Xét mọi thứ tự thăm $p=(v_1,\dots,v_{n-1})$ xuất phát từ $T$, chi phí $C(p)=d_{Tv_1}+\dots+d_{v_{n-1}T}$; giá trị nhỏ nhất là $L=30$ km (đạt tại T $\to$ A $\to$ C $\to$ D $\to$ B $\to$ T).
Bước 2 — Đếm chu trình đạt $L$.
Mỗi chu trình vô hướng tương ứng với HAI thứ tự thăm (chiều xuôi và chiều ngược) có cùng chi phí. Vì vậy số hành trình khác nhau (không kể chiều) $=$ (số thứ tự thăm đạt $L$) $\div\, 2$.
Kết luận: có $1$ hành trình khép kín ngắn nhất (không kể chiều đi).
59% trả lời đúng
261 đúng · 184 sai