tailieunhanh - 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ả | cầu giữa các nguồn và các đích. Đây là bài toán hết sức quan trọng trong 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 cj và Cji . Tuy nhiên có thể giải quyết các mạng vô hướng bằng cách thay thế mỗi liên kết vô hướng lj bằng hai 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 cho bà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 E f -E fji r vi 5 j j X f -S fji -rỊi vi d Ẹ f -Ẹ ffl vi 5 j J f í cij fij Vi j Thuật toán Ford-Fulkerson Thuậ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án Ford-Fulkerson. Thuật toán này chỉ ra các đường đi từ nguồn s tới đích d và gửi các luồng lớn nhất có thể qua mỗi đường mà không vi phạm giới hạn dung lượng. Thực ra thuật toán được điều khiển nhằm chỉ ra các đường đi và điền đầy chúng bằng các luồng. Hình . Mạng đơn giản Chẳng hạn xét một mạng trong hình . 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 đi SABD và một trên đường đi SEFD. Vì tổng dung lượng của các liên kế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ỏa mã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ác liê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ới D lớn nhất không thể lớn hơn dung lượng của bất kỳ cut nào dung 77 lượ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ổ đề 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ất Thực ra luồng từ S tới D lớn nhất chính bằng dung lượng của SD-cut có dung lượng bé nhất. Đó chính là định lý Luồng Lớn nhất- Cutset