Lời giải của bạn Trương Nhật Minh

Ta thay thể các địa danh bằng các số từ 0 tới 12 như sau:

0: Hà Nội; 1: Vĩnh Yên; 2: Thái Nguyên; 3: Bắc Ninh; 4: Hải Dương; 5: Phủ Lí; 6: Hà Đông; 7: Việt Trì; 8: Bắc Cạn; 9: Bắc Giang; 10: Việt Trì; 11: Nam Định; 12: Hòa Bình (Có hai địa danh Việt Trì, ta gọi là Việt Trì 7 và Việt Trì 10)

Đưa bài toán về dạng như sau:

+ Số 0 là trung tâm, số 0 nối trực tiếp với các số 1; 2; 3; 4; 5; 6.

+ Số 1 nối trực tiếp với các số 2; 6; 7.

+ Số 2 nối trực tiếp với các số 1; 3; 8.

+ Số 3 nối trực tiếp với các số 2; 4; 9.

+ Số 4 nối trực tiếp với các số 3; 5; 10.

+ Số 5 nối trực tiếp với các số 4; 6; 11.

+ Số 6 nối trực tiếp với các số 1; 5; 12.

+ Số 7 nối trực tiếp với các số 1; 8; 12.

+ Số 8 nối trực tiếp với các số 2; 7; 9.

+ Số 9 nối trực tiếp với các số 3; 8; 10.

+ Số 10 nối trực tiếp với các số 4; 9; 11.

+ Số 11 nối trực tiếp với các số 5; 10; 12.

+ Số 12 nối trực tiếp với các số 6; 7; 11.

Các đường nối màu cam gồm: 0-1; 0-2; 0-3; 0-5; 1-7; 3-9; 5-11.

các đường nối giữa hai số không có màu cam thì là màu xanh. Tìm các đường đi xuất phát từ số 0 và đi qua tất cả các số còn lại một lần rồi quay trở về số 0 sao cho lộ trình có nhiều đường đi màu cam nhất.

Ta có chương trình python kiểm tra các tất cả các lộ trình có thể, để giảm thời gian chạy code, ta chỉ xét các lộ trình có đường màu cam lớn hơn 3. Sau khi chạy chương trình ta thu được lộ trình có nhiều đường màu cam nhất (đường sắt) là 5 và có 4 lộ trình như sau:

Đường đi với 5 cạnh cam: [0, 1, 7, 12, 6, 5, 11, 10, 4, 3, 9, 8, 2, 0]

Hà Nội➜Vĩnh Yên➜Việt Trì 7➜Hòa Bình➜Hà Đông➜Phủ Lí➜Nam Định➜Việt Trì 10➜Hải Dương➜Bắc Ninh➜Bắc Giang➜Bắc Cạn➜Thái Nguyên➜Hà Nội

Đường đi với 5 cạnh cam: [0, 2, 8, 7, 1, 6, 12, 11, 5, 4, 10, 9, 3, 0]

Hà Nội➜Thái Nguyên➜Bắc Cạn➜Việt Trì 7➜Vĩnh Yên➜Hà Đông➜Hòa Bình➜Nam Định➜Phủ Lí➜Hải Dương➜Việt Trì 10➜Bắc Giang➜Bắc Ninh➜Hà Nội

Đường đi với 5 cạnh cam: [0, 2, 8, 9, 3, 4, 10, 11, 5, 6, 12, 7, 1, 0]

Hà Nội➜Thái Nguyên➜Bắc Cạn➜Bắc Giang➜Bắc Ninh➜Hải Dương➜Việt Trì 10➜Nam Định➜Phủ Lí➜Hà Đông➜Hòa Bình➜Việt Trì 7➜Vĩnh Yên➜Hà Nội

Đường đi với 5 cạnh cam: [0, 3, 9, 10, 4, 5, 11, 12, 6, 1, 7, 8, 2, 0]

Hà Nội➜Bắc Ninh➜ Bắc Giang➜ Việt Trì 10➜Hải Dương➜Phủ Lí➜Nam Định➜Hòa Bình➜Hà Đông➜Vĩnh Yên➜Việt Trì 7➜Bắc Cạn➜Thái Nguyên➜Hà Nội

Code python:

python

from typing import List, Set, Tuple

# Danh sách kề của đồ thị
graph = {
    0: [1, 2, 3, 4, 5, 6],
    1: [0, 2, 6, 7],
    2: [0, 1, 3, 8],
    3: [0, 2, 4, 9],
    4: [0, 3, 5, 10],
    5: [0, 4, 6, 11],
    6: [0, 1, 5, 12],
    7: [1, 8, 12],
    8: [2, 7, 9],
    9: [3, 8, 10],
    10: [4, 9, 11],
    11: [5, 10, 12],
    12: [6, 7, 11]
}

# Các cạnh màu cam
orange_edges = {(0, 1), (0, 2), (0, 3), (0, 5), (1, 7), (3, 9), (5, 11)}

max_orange = 0
best_paths = []

MIN_ORANGE_THRESHOLD = 4

def dfs(current: int, visited: Set[int], path: List[int], orange_count: int):
    global max_orange, best_paths

    if len(visited) == 13:
        if 0 in graph[current]:
            edge = (min(current, 0), max(current, 0))
            final_orange = orange_count + (1 if edge in orange_edges else 0)
            if final_orange >= MIN_ORANGE_THRESHOLD:
                path.append(0)

                if final_orange > max_orange:
                    max_orange = final_orange
                    best_paths = [list(path)]
                    print(f"Tìm được đường đi mới với {final_orange} cạnh cam: {path}")
                elif final_orange == max_orange:
                    best_paths.append(list(path))
                    print(f"Tìm thêm đường đi với {final_orange} cạnh cam: {path}")

                path.pop()
        return

    for neighbor in graph[current]:
        if neighbor not in visited:
            edge = (min(current, neighbor), max(current, neighbor))
            new_orange = orange_count + (1 if edge in orange_edges else 0)

            visited.add(neighbor)
            path.append(neighbor)
            dfs(neighbor, visited, path, new_orange)
            path.pop()
            visited.remove(neighbor)

# Khởi động
dfs(0, {0}, [0], 0)

print(f"\nSố cạnh cam tối đa đạt được: {max_orange}")
print(f"Tổng số đường đi đạt được {max_orange} cạnh cam: {len(best_paths)}")