Giải bài 2.28 trang 51 Chuyên đề học tập Toán 11 Kết nối tri thứcGiải bài toán người đưa thư với đồ thị có trọng số trên Hình 2.42.🍨Tổng hợp đề thi học kì 2 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 - SinhQuảng cáo
Đề bài 🐼Giải bài toán người đưa thư với đồ thị có trọng số trên Hình 2.42. Phương pháp giải - Xem chi tiết
Dựa vào bài toán người đưa thư để làm
Lời giải chi tiết Đồ thị Hình 2.42 chỉ có hai đỉnh bậc lẻ là D và E nên ta có thể tìm được một đường đi Euler từ D đến E (đường đi này đi qua mỗi cạnh đúng một lần).Một đường đi Euler từ D đến E là DBACDEBCE và tổng độ dài của nó là2 + 4 + 4 + 2 + 6 + 3 + 5 + 1 = 27.Để 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ừ E đến D theo thuật toán gắn nhãn vĩnh viễn.Đường đi ngắn nhất từ E đến D là ECD và có độ dài là 1 + 2 = 3.Vậy một chu trình cần tìm là DBACDEBCECD và có độ dài là 27 + 3 = 30.
Quảng cáo
Tham Gia Group Dành Cho Lớp 11 Chia Sẻ, Trao Đổi Tài Liệu Miễn Phí |