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 59
(Sở Phú Thọ 2025) Một trò chơi điện tử quy định như sau: Có sáu trụ $ A,B,C,D,E,F $ với số lượng các thử thách trên đường đi giữa các cặp trụ được mô tả như trong hình vẽ. Người chơi xuất phát từ một trụ nào đó đi qua tất cả các trụ còn lại, mỗi khi đi qua một trụ thì trụ đó sẽ bị phá hủy và không thể quay trở lại trụ đó được nữa, nhưng người chơi vẫn phải quay trở về trụ ban đầu. Tổng số thử thách của đường đi thỏa mãn điều kiện trên nhận giá trị nhỏ nhất bằng bao nhiêu?
Xem lời giải
Lời giải
Đáp án: 34
Vì đồ thị liên thông có số đỉnh $ n=6 $ và bậc của mọi đỉnh đều thoả mãn lớn hơn hoặc bằng $ \frac { n } { 2 }=3 $ nên đồ thị có chu trình Hamilton.
Dùng thuật toán láng giềng gần nhất, ta xét các chu trình sau:
$ ABCDFEA: $ có số thử thách là: $ 4+5+7+3+10+5=34 $
$ BAECFDB: $có số thử thách là: $ 4+5+9+8+3+6=35 $
$ CBAEFDC: $có số thử thách là: $ 5+4+5+10+3+7=34 $
$ DFEABCD: $có số thử thách là: $ 3+10+5+4+5+7=34 $
$ EABCDFE: $có số thử thách là: $ 5+4+5+7+3+10=34 $
$ FDBAECF: $có số thử thách là: $ 3+6+4+5+9+8=35 $
Vậy tổng số thử thách của đường đi thỏa mãn điều kiện trên nhận giá trị nhỏ nhất bằng 34.
