tailieunhanh - GIÁO TRÌNH TOÁN RỜI RẠC - CHƯƠNG V MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ_4

Xét xích =(v0, v4, v6, v3, v7, v8). Quá trình đánh dấu từ v0 đến v8 để có thể nâng luồng 1 lên một đơn vị bằng cách biến đổi luồng tại các cung thuộc xích được đánh dấu. Sau đó ta có luồng 2. | CHƯƠNGV MỘT SỐ BÀI TOÁN TÓI ƯU TRÊN ĐỒ THỊ Áp dụng thuật toán Ford-Fulkerson để nâng luồng ọ1. 9 V2 vo V6 V8 6 0 4 7 v V4 0 I ọ 3 Xét xích a v0 v4 v6 v3 v7 v8 . Quá trình đánh dấu từ v0 đến v8 để có thể nâng luồng 91 lên một đơn vị bằng cách biến đổi luồng tại các cung thuộc xích a được đánh dấu. Sau đó ta có luồng 92. 4 6 Xét xích 3 v0 v1 v5 v2 v6 v3 v7 v8 . Quá trình đánh dấu từ v0 đến v8 để có thể nâng luồng 92 lên một đơn vị bằng cách biến đổi luồng tại các cung thuộc xích 3 được đánh dấu. Sau đó ta có luồng 93. Tiếp theo ta chỉ có thể đánh dấu được đỉnh v0 nên quá trình nâng luồng kết thúc và ta được giá trị của luồng cực đại là n 6 12 8 26. V8 Mặt khác thiết diện nhỏ nhất r- B với B v1 v2 . v8 là r- B V0 V1 V0 V2 V0 v3 V0 V4 . . BÀI TOÁN DU LỊCH. . Giới thiệu bài toán Một người xuất phát từ một thành phố nào đó muốn tới thăm n-1 thành phố khác mỗi thành phố đúng một lần rồi quay về thành phố ban đầu. Hỏi nên đi theo trình tự nào để độ dài tổng cộng các đoạn đường đi qua là ngắn nhất khoảng cách giữa hai thành phố có thể hiểu là cự ly thông thường hoặc thời gian cần đi hoặc chi phí của hành trình . và xem như cho trước . Xét đồ thị đầy đủ G V E với V 1 2 . n có trọng số với trọng số mịj m i j có thể khác mji m j i . Như vậy ta có thể xem G như là một đồ thị có hướng đầy đủ mạnh theo nghĩa với mọi i j 1 2 . n i j luôn có i j j i eE. Bài toán trở thành tìm chu trình Hamilton có độ dài ngắn nhất trong .