TAILIEUCHUNG - Mục đích của việc mô hình hóa và đánh giá đặc tính hoạt động của hệ thống p7

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ết các mạng vô hướng bằng cách thay thế mỗi liên kết vô hướng lij 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. | 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

• Quản trị mạng
• giáo trình quản trị mạng
• thủ thuật quản trị mạng
• kỹ năng quản trị mạng
• phương pháp quản trị mạng
• mẹo quản trị mạng
• giáo trình lập trình
• thủ thuật quản tgiáo trình quản trị mạng
• mẹo quản trị mạngrị mạng
• kỹ năng lập trình
• phương pháp lập trình
• mẹo quản lập trình
• thủ thgiáo trình kế toán
• kỹ thuật kế toán
• thủ thuật kế toán
• phương pháp học kế toán
• bí quyết học kế toánuật quản trị mạng