tailieunhanh - Giáo trình đồ thị - Một số ứng dụng của bài toán luồng lớn nhất

Bài toán luồng lớn nhất có rất nhiều ứng dụng trong việc giải quyết các bài toán khác nhau của lý thuyết đồ thị. | BÀI 16 . Một số ứng dụng của bài toán luồng lớn nhất Bài toán luồng lớn nhất có rất nhiều ứng dụng trong việc giải quyết các bài toán khác nhau của lý thuyết đồ thị. . Bài toán luồng nhỏ nhất Ngược lại với bài toán luồng lớn nhất chúng ta xét bài toán sau đây Bài toán Cho mạng G c . Tìm luồng t qua mạng có giá trị tz nhỏ nhất và thoả mãn điều kiện a thay cho điều kiện a như sau a V e G E t e c e . Thuật toán Tìm luồng bé nhất Ta dùng phương pháp cải tiến luồng giống như phương pháp giải bài toán luồng lớn nhất. Xuất phát từ một luồng t nào đó thoả mãn điều kiện c ta dùng phương pháp sau đây để giảm giá trị của luồng t. Bước 1 Đánh dấu các đỉnh Đầu tiên đánh dấu cho đỉnh thu z số 0. Nếu đỉnh y đã được đánh dấu có cạnh x y với đỉnh đầu chưa được đánh dấu và t x y c x y thì đánh dấu cho đỉnh x là y. Nếu đỉnh x đã được đánh dấu có cạnh x y thì đánh dấu cho đỉnh y là -x. Với cách đánh dấu này mà đi tới được đỉnh phát x0 thì ta đã tìm được một đường đi vô hướng từ z tới x0 được đánh dấu. Bước 2 Giảm luồng Bây giờ ta có thể giảm luồng đi 1 bằng cách chọn luồng mới t như sau Nếu cạnh e không thuộc đường đi trên thì giữ nguyên luồng nghĩa là t e t e Nếu cạnh e thuộc đường đi này và cùng chiều với chiều từ x0 tới z thì đặt t e t e - 1 vì trên cạnh đó t e c e còn nếu cạnh e ngược chiều thì đặt t e t e 1 . Lặp lại quá trình giảm luồng trên cho đến khi không đánh dấu được tới đỉnh phát x0. Khi đó luồng nhận được có giá trị nhỏ nhất. Ví dụ Xét mạng vận tải sau đây. Hình . Mạng vận tải và luồng đã giảm Luũng cũ cú giỏ trũ là tz 19. Luũng mũi sau khi cũi tiũn cú giỏ trũ là tz 18 và là luũng nhũ nhũt. . Bài toán luòng trên mạng có nhiều đỉnh phát và đỉnh thu Giả sử G c là một mạng vận tải với n đỉnh phát P1 p2 . pn và m đỉnh thu qi q2 . qm. Bài toán tìm luồng lớn nhất từ nhiều đỉnh phát tới nhiều đỉnh thu có thể đưa về bài toán luồng lớn nhất từ một đỉnh phát tới một đỉnh thu bằng cách thêm vào một đỉnh phát giả X0 một đỉnh thu giả Z các cạnh nối X0 với tất