Giải chi tiết

Câu 5: a) Để tìm đường đi ngắn nhất từ A đến F trong đồ thị có trọng số, ta áp dụng thuật toán Dijkstra: - Bước 1: Khởi tạo khoảng cách ban đầu từ A đến tất cả các đỉnh khác là vô cùng, trừ đỉnh A có khoảng cách là 0. - Bước 2: Chọn đỉnh có khoảng cách nhỏ nhất chưa được xử lý (ban đầu là A). - Bước 3: Cập nhật khoảng cách từ đỉnh đã chọn đến các đỉnh kề cận. - Bước 4: Lặp lại các bước 2 và 3 cho đến khi đỉnh F được xử lý. Áp dụng thuật toán: - Khoảng cách ban đầu: A(0), B(∞), C(∞), D(∞), E(∞), F(∞) - Chọn A, cập nhật: A(0), B(2), C(3), D(∞), E(∞), F(∞) - Chọn B, cập nhật: A(0), B(2), C(3), D(5), E(∞), F(∞) - Chọn C, cập nhật: A(0), B(2), C(3), D(5), E(6), F(∞) - Chọn D, cập nhật: A(0), B(2), C(3), D(5), E(6), F(8) - Chọn E, cập nhật: A(0), B(2), C(3), D(5), E(6), F(8) Kết luận: Đường đi ngắn nhất từ A đến F là 8 đơn vị, theo đường A → B → D → F. b) Để người đưa thư đi qua mỗi con đường ít nhất một lần và trở về điểm xuất phát với quãng đường ngắn nhất, ta áp dụng thuật toán tìm đường đi Euler: - Bước 1: Kiểm tra xem đồ thị có thể có đường đi Euler hay không. Đồ thị có đường đi Euler nếu tất cả các đỉnh đều có bậc chẵn hoặc chỉ có hai đỉnh có bậc lẻ. - Bước 2: Nếu đồ thị không thỏa mãn điều kiện trên, thêm các cạnh ảo để thỏa mãn điều kiện. - Bước 3: Áp dụng thuật toán tìm đường đi Euler. Kiểm tra đồ thị: - Các đỉnh A, B, C, D, E, F đều có bậc chẵn. Do đó, đồ thị có đường đi Euler. Ta có thể chọn bất kỳ đỉnh nào làm điểm xuất phát và đi qua mỗi cạnh đúng một lần rồi trở về điểm xuất phát. Tổng độ dài đường đi Euler là tổng trọng số của tất cả các cạnh trong đồ thị: \[ 2 + 3 + 5 + 6 + 8 + 4 + 7 + 9 + 10 + 11 + 12 + 13 = 80 \] Kết luận: Người đưa thư phải đi qua mỗi con đường ít nhất một lần và trở về điểm xuất phát với tổng quãng đường là 80 đơn vị. Câu 6: Để người đưa thư đi qua mỗi con đường ít nhất một lần và quay lại điểm xuất phát với quãng đường đi ngắn nhất, ta cần áp dụng thuật toán tìm đường đi Euler trong đồ thị. Bước 1: Xác định các đỉnh của đồ thị. - Đỉnh A (bưu điện) - Đỉnh B - Đỉnh C - Đỉnh D - Đỉnh E Bước 2: Xác định các cạnh nối giữa các đỉnh. - A liên kết với B, C, D - B liên kết với A, C, D, E - C liên kết với A, B, D, E - D liên kết với A, B, C, E - E liên kết với B, C, D Bước 3: Kiểm tra điều kiện tồn tại đường đi Euler. - Một đồ thị có đường đi Euler nếu và chỉ nếu tất cả các đỉnh đều có bậc chẵn hoặc chỉ có hai đỉnh có bậc lẻ. - Ta kiểm tra bậc của các đỉnh: - A: 3 (lẻ) - B: 4 (chẵn) - C: 4 (chẵn) - D: 4 (chẵn) - E: 3 (lẻ) Như vậy, đồ thị này có hai đỉnh có bậc lẻ là A và E, do đó tồn tại đường đi Euler. Bước 4: Tìm đường đi Euler. - Ta sẽ bắt đầu từ đỉnh A và kết thúc ở đỉnh E, sau đó quay trở lại đỉnh A để hoàn thành đường đi Euler. Một ví dụ về đường đi Euler có thể là: A → B → C → D → E → B → C → A → D → E → A Bước 5: Kết luận. Người đưa thư nên đi theo đường đi Euler trên để đảm bảo đi qua mỗi con đường ít nhất một lần và quay lại điểm xuất phát với quãng đường đi ngắn nhất. Đáp số: Đường đi ngắn nhất là A → B → C → D → E → B → C → A → D → E → A. Câu 7: Để tìm đường đi ngắn nhất từ đỉnh M đến N trong đồ thị có trọng số, ta sẽ áp dụng thuật toán Dijkstra. Các bước thực hiện như sau: 1. Khởi tạo: - Đặt khoảng cách ban đầu từ đỉnh M đến tất cả các đỉnh khác là vô cùng (\(\infty\)), trừ đỉnh M có khoảng cách là 0. - Chọn đỉnh M làm đỉnh xuất phát. 2. Bước lặp: - Xét đỉnh M, tìm các đỉnh kề cận của M và cập nhật khoảng cách đến các đỉnh này. - Chọn đỉnh có khoảng cách nhỏ nhất chưa được xử lý và lặp lại quá trình trên cho đỉnh đó. Cụ thể: - Từ đỉnh M, ta có các đỉnh kề cận là A và B với các khoảng cách lần lượt là 3 và 5. - Cập nhật khoảng cách: \(d(A) = 3\), \(d(B) = 5\). Tiếp theo, chọn đỉnh A (vì có khoảng cách nhỏ nhất từ M): - Từ đỉnh A, ta có các đỉnh kề cận là B và C với các khoảng cách lần lượt là 2 và 4. - Cập nhật khoảng cách: \(d(B) = 3 + 2 = 5\) (không thay đổi vì đã có \(d(B) = 5\)), \(d(C) = 3 + 4 = 7\). Tiếp theo, chọn đỉnh B (vì có khoảng cách nhỏ nhất từ M): - Từ đỉnh B, ta có các đỉnh kề cận là C và N với các khoảng cách lần lượt là 1 và 6. - Cập nhật khoảng cách: \(d(C) = 5 + 1 = 6\) (thay đổi vì \(d(C) = 7\)), \(d(N) = 5 + 6 = 11\). Tiếp theo, chọn đỉnh C (vì có khoảng cách nhỏ nhất từ M): - Từ đỉnh C, ta có các đỉnh kề cận là N với khoảng cách là 2. - Cập nhật khoảng cách: \(d(N) = 6 + 2 = 8\) (thay đổi vì \(d(N) = 11\)). Cuối cùng, chọn đỉnh N (vì có khoảng cách nhỏ nhất từ M): - Đỉnh N là đỉnh đích, ta dừng thuật toán. Kết luận: Đường đi ngắn nhất từ đỉnh M đến N có tổng trọng số là 8, đi qua các đỉnh: M → A → B → C → N. Đáp số: Đường đi ngắn nhất từ đỉnh M đến N là M → A → B → C → N với tổng trọng số là 8.