Giáo trình hình thành hệ thống ứng dụng nguyên lý điều khiển luồng theo tiến trình biểu diễn số p8

Tham khảo tài liệu giáo trình hình thành hệ thống ứng dụng nguyên lý điều khiển luồng theo tiến trình biểu diễn số p8, kỹ thuật - công nghệ, kĩ thuật viễn thông phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Giáo trình hình thành hệ thống ứng dụng nguyên lý điều khiển luồng theo tiến trình biểu diễn số p8cầu giữa các nguồn và các đích. Đây là bài toán hết sức quan trọngtrong việc thiết kế mạng và sẽ được nói kỹ ở chương sau.Chú ý rằng trong trường hợp này ta đang xét các liên kết hữu hướng(nghĩa là có sự khác nhau giữa cij và cji). Tuy nhiên có thể giải quyếtcác mạng vô hướng bằng cách thay thế mỗi liên kết vô hướng lij bằnghai liên kết hữu hướng có các dung lượng riêng rẽ. Như chúng ta sẽthấy, trong bất kỳ liên kết nào và ở đâu trong quá trình tìm lời giải chobài toán này, chỉ có luồng theo một hướng.Có thể biểu diễn bài toán này dưới dạng bài toán tìm các luồng fij thoảmãn các điều kiện sau: f   f ji  rij ; i  s ij j j f   f ji  rij ; i  d ij j j f   f ji  0; i  s ij j j f ij  ci j f ij  0; i, jThuật toán Ford-FulkersonThuật toán tốt nhất cho việc giải bài toán luồng đơn hạng là thuật toánFord-Fulkerson. Thuật toán này chỉ ra các đường đi từ nguồn s tới đíchd và gửi các luồng lớn nhất có thể qua mỗi đường mà không vi phạmgiới hạn dung lượng. Thực ra thuật toán được điều khiển nhằm chỉ racác đường đi và điền đầy chúng bằng các luồng. Hình 4.10. Mạng đơn giảnChẳng hạn xét một mạng trong hình 4.10. Giả sử tất cả các liên kết códung lượng là 1. Chúng ta có thể gửi một đơn vị luồng trên đường điSABD v à một trên đường đi SEFD. Vì tổng dung lượng của các liênkết rời S là 2 và mỗi đơn vị luồng từ S tới D phải sử dụng một đơn vịdung lượng rời khỏi S này do đó không có luồng nào khác nữa thỏamãn yêu cầu. Ngoài ra, vì mỗi đơn v ị luồng phải sử dụng ít nhất mộtđơn vị dung lượng của một SD-cut bất kỳ (với SD-cut là một tập cácliên kết mà sự biến mất của nó phân tách S khỏi D) nên luồng từ S tớiD lớn nhất không thể lớn hơn dung lượng của bất kỳ cut nào (dung 77lượng của cut là tổng dung lượng của tất cả các liên kết thuộc cut). Dođó ta có bổ đề sau: Bổ đề 4.1 (Ford-Fulkerson) Luồng từ S tới D lớn nhất không thể lớn hơn dung lượng của cut có dung lượng nhỏ nhấtThực ra, luồng từ S tới D lớn nhất chính bằng dung lượng của SD-cutcó dung lượng bé nhất. Đó chính là định lý Luồng Lớn nhất- CutsetBé nhất nổi tiếng của Ford-Fulkerson.Giới hạn (1) đã nêu trên gọi là điều kiện giới hạn bảo toàn luồng. Điềukiện này đảm bảo rằng với các nút khác với nút nguồn và nút đích thìluồng vào bằng với luồng ra. Trong trường hợp này, các nút nguồn(đích) có luồng ra (vào) phải bằng luồng từ nguồn tới đích. Bất kỳ SD-cut nào cũng phân chia các nút thành hai tập X v à Y với S thuộc X vàD thuộc Y. Nếu điều kiện (1) đối với tất cả các nút thuộc tập X đượccộng lại thì ta thấy rằng luồng tổng từ X tới Y trừ đi luồng tổng từ Y tớiX có kết quả bằng luồng từ S tới D. Chú ý rằng tổng các phần ở vế tráichính bằng tổng các luồng trong các liên kết có một đầu thuộc X cònđầu kia thuộc Y, trừ đi tổng các luồng trong các liên kết có một đầuthuộc Y còn đầu kia thuộc X. Các liên kết có hai đầu cùng thuộc Xkhông tham gia vào tổng này vì chúng xuất hiện trong tổng nhưng códấu ngược nhau. Các liên kết không có đầu nào thuộc X cũng khôngxuất hiện ở trong tổng. S tham gia vào vế phải của điều kiện; tất cả cácnút khác không tham gia.Vì thế, để thoả mãn định lý trên cần phải:Luồng tổng đi qua cut có dung lượng bé nhất phải bằng dung lượngcủa cut đó nghĩa là tất cả các liên kết thuộc cắt phải ở trạng thái bãohoà (luồng bằng dung lượng).Luồng đi ngược cut này phải bằng 0.Thực ra, tất các cut có dung lượng bé nhất phải là bão hoà và điều đóxảy ra vào cuối thuật toán. Thuật toán thực hiện bằng cách chỉ ra cácđường đi có dung lượng bé và gửi luồng đi qua toàn bộ các đường điđó. Khi không tìm ra một đường đi nào cả có dung lượng bé, một cutbão hoà được chỉ ra và thuật toán kết thúc. Các cut có dung lượng békhác cũng bão hoà nhưng chúng không được thuật toán chỉ ra. number mxflow Thuật toán trả về luồng trong mỗi liên kết. Tổng luồng đi từ nguồn tớiđích có thể được tính bằng tổng các luồng đi ra khỏi nguồn (hoặc đi tớiđích). Thuật toán chỉ ra đường đi từ nguồn tới đích bằng cách sử dụngmột thuật toán được cải biến từ thuật toán Bellman. Thuật toán nàycho phép sử dụng một liên kết (i,j) theo hướng tới (nghĩa là từ i tới j)nếu luồng từ i tới j là fij bé hơn dung lượng của liên kết đó cij. Nó cũngcho phép sử dụng liên kết theo chiều ngược lại (nghĩa là liên kết (i.j)được sử dụng để đưa luồng từ j tới i), nhưng điều này chỉ xảy ra nếutrước đó có một luồng từ i tới j là dương. Trong trường hợp này, luồngđược loại ra khỏi liên kết (i,j).Luồng lớn nhất theo chiều từ i tới j là cij - fij. Luồng lớn nhất theo chiềutừ j tới i là fij. Đại l ...