Cho một đồ thị có trọng số như Hình 2.31. Tìm một chu trình xuất phát từ đỉnh $A$ của đồ thị, có tổng trọng số nhỏ nhất và chứa mỗi cạnh ít nhất một lần. [IMAGE:question_images/12-CD35. MOT SO BAI TOAN THUOC CHUYEN DE TOAN HOC 10-11-12/BAI TOAN 4. LY THUYET DO THI/image320.png]

Question

Beedemy · Accepted Answer

Lời 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$ đến $D$ (đường đi này đi qua mỗi cạnh đúng một lần). Một đường đi Euler từ $A$ đến $D$ là $AEABEDBCD$ và tổng độ dài của nó là $6+8+1+7+5+4+2+3=36$ Để quay trở 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 đã mô tả ở Mục 1. Đường đi ngắn nhất từ $D$ đến $A$ là $DBA$ 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$.

Bài tự luận Một số bài toán thuộc chuyên đề Toán học 10–11–12 · Bài 17