Câu hỏi:
11/07/2023 544
Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.36.
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.36 chỉ có hai đỉnh bậc lẻ là C và E nên ta có thể tìm được một đường đi Euler từ C đến E (đường đi này đi qua mỗi cạnh đúng một lần).
Một đường đi Euler từ đỉnh C đến đỉnh E là CABCEBDE và tổng độ dài của nó là
2 + 1 + 4 + 10 + 5 + 3 + 6 = 31.
Để 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 C theo thuật toán gắn nhãn vĩnh viễn.
Đường đi ngắn nhất từ E đến C là EBAC và có độ dài là 5 + 1 + 2 = 8.
Vậy một chu trình cần tìm là CABCEBDEBAC và có độ dài là 31 + 8 = 39.
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.32.
Xem đáp án »
13/07/2024
1,904
Câu 2:
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,286
Câu 3:
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 4:
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 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
423
về câu hỏi!