Câu hỏi:
13/07/2024 1,911
Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.32.
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
Lời giải:
Đồ 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.
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Tìm đường đi ngắn nhất từ A đến D trong đồ thị có trọng số trên Hình 2.33.
Xem đáp án »
12/07/2024
1,287
Câu 2:
Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.35.
Xem đáp án »
13/07/2024
731
Câu 3:
Tìm đường đi ngắn nhất từ đỉnh S đến mỗi đỉnh khác của đồ thị có trọng số trên Hình 2.34.
Xem đáp án »
13/07/2024
619
Câu 4:
Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.36.
Xem đáp án »
11/07/2023
550
Câu 5:
Cho sơ đồ như trên Hình 2.28, ở đó A, B, C, D, E, F là các địa điểm nối với nhau bởi các con đường với độ dài của mỗi con đường được cho như trên hình.
a) Hãy chỉ ra 2 đường đi từ A đến F và so sánh độ dài của hai đường đi đó.
b) Với mỗi đỉnh V của sơ đồ trên Hình 2.28, ta gắn số I(V) là khoảng cách ngắn nhất để đi từ A đến V và gọi là nhãn vĩnh viễn của đỉnh V. Như vậy, ta có ngay I(A) = 0. Dựa vào Hình 2.28, hãy tìm các nhãn vĩnh viễn I(B), I(C) của hai đỉnh kề với A là B, C.
Cho sơ đồ như trên Hình 2.28, ở đó A, B, C, D, E, F là các địa điểm nối với nhau bởi các con đường với độ dài của mỗi con đường được cho như trên hình.
a) Hãy chỉ ra 2 đường đi từ A đến F và so sánh độ dài của hai đường đi đó.
b) Với mỗi đỉnh V của sơ đồ trên Hình 2.28, ta gắn số I(V) là khoảng cách ngắn nhất để đi từ A đến V và gọi là nhãn vĩnh viễn của đỉnh V. Như vậy, ta có ngay I(A) = 0. Dựa vào Hình 2.28, hãy tìm các nhãn vĩnh viễn I(B), I(C) của hai đỉnh kề với A là B, C.
Xem đáp án »
12/07/2024
425
về câu hỏi!