Danh mục : Toán học

Upload vào lúc : 1 năm trước

File gốc : Giao trinh Toan roi rac - Phu luc 2.pdf

Số lần xem : 233

Số lượt tải xuống : 0

Kích thước : 0.22 Mb

Số trang : 10

Tải xuống (0.22 Mb)

Xem trên điện thoại
Đọc Giáo trình toán rời rạc - Phụ Lục 2 trên điện thoại

Tags

Giới thiệu về tài liệu

Phụ lục 2
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ọn. Một thí dụ khác là nếu xét đồ thị tương ứng với một hệ thống đường ống dẫn dầu, trong đó các ống tương ứng với các cung, điểm phát có thể coi là tàu chở dầu, điểm thu là bể chứa, còn các điểm nối giữa các ống là các nút của đồ thị, khả năng thông qua của các cung tương ứng với tiết diện các ống. Cần phải tìm luồng dầu lớn nhất có thể bơm dầu từ tàu chở dầu vào bể chứa.

Tài liệu liên quan

Tải ứng dụng Tài Liệu PDF
giúp trải nghiệm tốt hơn

Lịch sử tải

Chưa có ai tải tài liệu này!