BÀI TOÁN LUỒNG CỰC ĐẠI VỚI KHẢ NĂNG THÔNG QUA CÁC CUNG – CÁC ĐỈNH - pdf 16

Chia sẻ miễn phí cho các bạn tài liệu: BÀI TOÁN LUỒNG CỰC ĐẠI VỚI KHẢ NĂNG THÔNG QUA CÁC CUNG – CÁC ĐỈNH
2
Thí dụ 1. Hình 1a cho ví dụ mạng G với khả năng thông qua ở cung và đỉnh.
Hình 1b là mạng G’ tương ứng chỉ có khả năng thông qua ở các cung.

Hình 1
Do luồng đi vào đỉnh v
+
phải đi qua cung (v
+
,v
-
) với khả năng thông qua d(v),
nên luồng cực đại trong G’ sẽ bằng luồng cực đại trong G với khả năng thông qua của các cung và đỉnh.
Hai bước trên ta có thể biểu diễn dưới dạng sơ đồ thuật toán sau:
C[v,t]
C[u,t]
C[s,v]
C[s,u]
t
-
d
t
t
+
C[u,v]
v
-
d
v
v
+
u
-
d
u
u
+
s
-
d
s
s
+
(b)
C[u,v]
C[v,t]
C[s,v]
C[u,t]
C[s,u]
t d
t
v d
v
u d
u
s
d
s
(a)
Bài toán luồng cực đại trong mạng là một trong số những bài toán tối ưu trên đồ thị tìm được những ứng dụng rộng rãi trong thực tế cũng như những ứng dụng thú v
Dành riêng cho anh em Ket-noi, bác nào cần download miễn phí bản đầy đủ thì trả lời topic này, Nhóm Mods sẽ gửi tài liệu cho bạn qua hòm tin nhắn nhé.
- Bạn nào có tài liệu gì hay thì up lên đây chia sẻ cùng anh em.
- Ai cần tài liệu gì mà không tìm thấy ở forum, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Music ♫

Copyright: Tài liệu đại học © DMCA.com Protection Status