TAILIEUCHUNG - Giáo trình toán rời rạc - Bài toán luồng cực đại

Cho mạng G=(V,E). Hãy tìm luồng f* trong mạng với giá trị luồng val(f*) là lớn nhất. Luồng như vậy ta sẽ gọi là luồng cực đại trong mạng. Bài toán như vậy có thể xuất hiện trong rất nhiều ứng dụng thực tế. Chẳng hạn khi cần xác định cường độ lớn nhất của dòng vận tải giữa hai nút của một bản đồ giao thông. Trong thí dụ này lời giải của bài toán luồng cực đại sẽ chỉ cho ta các đoạn đường xe đông nhất và chúng tạo thành chỗ hẹp tương ứng của dòng giao thông xét theo hai nút đã. | chỉ ra lượng lớn nhất có thể tăng hoặc giảm luồng theo cung này. Đầu tiên chỉ có đỉnh s được khởi tạo nhãn và nhãn của nó là chưa xét, còn tất cả các đỉnh còn lại đều chưa có nhãn. Từ s ta gán nhãn cho tất cả các đỉnh kề với nó và nhãn của đỉnh s sẽ trở thành đã xét. Tiếp theo, từ một đỉnh v có nhãn chưa xét ta lại gán nhãn cho tất cả các đỉnh chưa có nhãn kề với nó và nhãn của đỉnh v trở thành đã xét. Quá trình sẽ được lặp lại cho đến khi hoặc là đỉnh t trở thành có nhãn hoặc là nhãn của tất cả các đỉnh có nhãn đầu là đã xét nhưng đỉnh t vẫn không có nhãn. Trong trường hợp thứ nhất ta tìm được đường tăng luồng, còn trong trường hợp thứ hai đối với luồng đang xét không tồn tại đường tăng luồng (tức là luồng đã cực đại). Mỗi khi tìm được đường tăng luồng, ta lại tăng luồng theo đường tìm được, sau đó xoá tất cả các nhãn và đổi với luồng mới thu được lại sử dụng phép gán nhãn các đỉnh để tìm đường tăng luồng. Thuật toán sẽ kết thúc khi nào đối với luồng đang có trong mạng không tìm được đường tăng luồng.

• Toán học
• bài toán luồng cực đại
• toán rời rạc
• giáo trình toán rời rạc
• tài liệu toán rời rạc
• tài liệu toán học
• Luồng cực đại
• Thuật toán tìm luồng cực đại
• Mạng hỗn hợp mở rộng
• Luồng cực đại lát cắt cực tiểu
• Mạng thặng dư
• Phương pháp đẩy luồng trước
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Bài toán luồng cực đại trong mạng
• Đường tăng luồng
• Định lý về luồng cực đại
• Luồng trên mạng
• Đồ thị tăng luồng
• Thuật toán Ford Fulkerson
• Mạng mở rộng
• Bài giảng Toán rời rạc
• Ứng dụng bài toán luồng cực đại
• Ứng dụng trong tổ hợp
• Bài toán cặp ghép cực đại
• Đồ thị hai phía
• Discrete Mathematics
• Tìm luồng cực đại trong mạng
• Bài toán luồng cực đại trên mạng
• Lát cắt cực tiểu
• Ý tưởng thuật toán
• Xây dựng thuật toán song song
• Thuật toán song song
• Bài toán tìm luồng cực đại trên mạng
• Hiệu chỉnh tăng luồng
• Tìm luồng cực đại trên mạng
• Tìm luồng cực đại
• Bài tập Luồng trên mạng
• Tìm ghép cặp cực đại
• các cung các đỉnh
• tối ưu trên đồ thị
• lý thuyết tổ hợp
• đồ thị
• Thuật toán Edmond Karp
• Thuật toán Ford
• Bài toán luồng tổng quát
• Độ tin cậy của mạng
• Bài toán phân luồng giao thông
• Xây dựng mô hình mạng giao thông mở rộng
• Phát triển thuật toán xấp xỉ
• Ngôn ngữ Java
• Maximum flow problem
• Luồng trong mạng
• điều hành mạng
• an ninh mạng
• mạng máy tính
• mạng
• bài toán ứng dụng
• Bài toán luồng
• Bài toán phân công vận tải
• Giải thuật di truyền
• Đánh giá độ khó của bài toán phân công vận tải
• Định lí Ford Fulkerson
• Lý thuyết đối ngẫu
• Tiểu luận Lý thuyết đối ngẫu
• Bài toán đường đi ngắn nhất
• Thuật toán Bellmen Ford
• Thuật toán luồng cực đại
• Bài toán luồng đa phương tiện
• Luồng vận tải
• Áp dụng thuật toán Ford Fulkerson
• Biểu diễn đồ thị trên máy tính
• Đồ thị Hamilton
• Bài toán ghép cặp
• Bài toán ghép cặp trên đồ thị