Đang chuẩn bị liên kết để tải về tài liệu:
Đồ thị và các thuật toán - Chương 7

Tài liệu tham khảo giáo trình Đồ thị và các thuật toán - Chương 7 Mạng vận tải | Chương 7 Mạng vận tải 7.1 Mở đậu Một trong những bai toán lý thu và quan trọng của ly thuyết đồ thi là xác dinh giá tri lớn nhất của luong được truyộn tìr một dính nguồn s của đế thi đến một dính đích t. Trong khung canh đo moi cung vi Vj của do thi G được gýn với một kha nang thong qua qij la sế lượng luông lớn nhat cá thể tai qua cung nay. Bai toan nay va những cai biên ciỉa no cá rột nhiều ứng đung trong thực tộ chẳng han xác đinh một độ giao thong lorn nhột giữa hai vung trong ban đồ giao thong được biộu điên bởi một đồ thi. Trong ví đu nay loi giai ciia bai toan luong lớn nhát cung chỉ ra những nơi bảo hoa trộn mang giao thong va tao một tác nghẽn khi Mộng tập trung vao giữa hai vi trá nao đo. Phương pháp giai bai toan luồng lấn nhất từ s độn t đưa ra lan đau tiền bởi Forđ va Fulkerson 27 va ky thuột gan nhan ciia ho la co s o cho những thuột toán khác giai quyột những van độ liền quan. co một sộ cai bi0n ciỉa bai toán Mộng lớn nhát 1. Gia sii rang moi cung ciỉa đo thi khộng chỉ được gắn với kha nang qij cho biột cộn trộn ciỉa luong trộn cung vi Vj ma con kha năng rij cho cạn dùýi ciỉa Mộng trộn cung nay. Trong trường hợp nhu1 vộy khộng phai luc nao một tộp chap nhộn được các gia tri cua luong cung thoa mẽn cung luc hai rang buộc nay. Tuy nhi0n-noi chung-nhi 0u Mộng thoa diêủ kiộn nay va nộu ngoai cac Idia năng con co cac chi phá cij tương ứng một đơn vi luong đoc theo các cung thỉ bai toan tro thanh tìm luồng chấp nhận được vấi chi phí nhồ nhất tù s độn t. 2. Xát trường hợp đòi hoi luồng lán nhất giữậ mợi cập đính. Mạc đu bai toán nay cá thộ giai bang n n 1 2 lan lặp cac bai toan luong lớn nhat tù s độn t nhưng cách lam nay qua thộ Tương tạr với tìm tat ca các đường đi ngan nhát o đay cung cộn 173 một thuật toán chuyên dụng dể giéỉi nó-và trong trường hợp do thi vô hướng phương pháp giái quyêt no khong liên quan đôn loi giái cUá bái toán luong lorn nhát giữá hái đỉnh s vá t. 3. Nêu tháy cho một đỉnh nguon và một đỉnh đích tá kh io sát một sô nguôn và một so .