Giải mục 2 trang 47, 48, 49 Chuyên đề học tập Toán 11 - Kết nối tri thức

Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.32.

Tổng hợp đề thi học kì 1 lớp 11 tất cả các môn - Kết nối tri thức

Toán - Văn - Anh - Lí - Hóa - Sinh

Quảng cáo

Đề bài

Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.32.

 

Phương pháp giải - Xem chi tiết

Giải bài tán bằng thuật toán tìm đường đi ngắn nhất: Ta xuất phát từ đỉnh A và di chuyển theo các cạnh của đồ thị. Với mỗi đỉnh V, ta gắn một số \(I(V)\) là khoảng cách ngắn nhất để đi từ A đến V, gọi là nhãn vĩnh viễn của đỉnh V. Như vậy, để tìm độ dài của đường đi ngắn nhất nối A với F, ta cần tìm \(I(F)\).

Lời giải chi tiết

Đồ thị Hình 2.32 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à AFEABEDBCD và tổng độ dài của nó là

10 + 9 + 7 + 2 + 8 + 16 + 15 + 3 + 4 = 74.

Để 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 gắn nhãn vĩnh viễn.

Đường đi ngắn nhất từ D đến A là DCBA và có độ dài là 4 + 3 + 2 = 9.

 Vậy một chu trình cần tìm là AFEABEDBCDCBA và có độ dài là 74 + 9 = 83.

Quảng cáo

Tham Gia Group Dành Cho 2K8 Chia Sẻ, Trao Đổi Tài Liệu Miễn Phí

close