Câu hỏi:
39 lượt xem
Lời giải
Hướng dẫn giải:
Đồ 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.
Câu 1:
Câu 2:
Câu 3:
Câu 4:
Câu 5:
Câu 6:
Tự luận
Hãy chỉ ra ít nhất 5 đường đi từ S đến Y trong đồ thị trên Hình 2.38.
5 tháng trước
34 lượt xem
Câu 7:
Câu 8:
Câu 9:
Tự luận
Giải bài toán người đưa thư với đồ thị có trọng số trên Hình 2.41.
5 tháng trước
25 lượt xem
ĐỀ THI LIÊN QUAN:
-
34 câu hỏi 78 lượt thi