1749906
Luồng cực đại
https://vi.wikipedia.org/wiki?curid=1749906
Title: Luồng cực đại
Luồng cực đại là một trong những bài toán tối ưu trên đồ thị tìm được những ứng dụng rất rộng rãi trong cả thực tế cũng như trong lý thuyết tổ hợp. Bài toán được đề xuất vào đầu những năm 1950 và gắn liền với tên tuổi của 2 nhà toán học Mỹ Lester Randolph Ford và Delbert Ray Fulkerson.
Mạng.
Mỗi cạnh e = (u, v) ∈ E được gán một số nguyên không âm c(e) = c[u, v] và gọi là khả năng thông qua của cung đó (capacity).
W-(x) = {(u, v) ∈ E | u ∈ V}: tập các cung đi vào đỉnh v.
W+(x) = {(v, u) ∈ E | u ∈ V}: tập các cung đi ra khỏi đỉnh v.
Tính chất của luồng.
Với tập B ⊆ V, ký hiệu:
W-(B) = { (a, b) ∈ E | a ∉ B, b ∈ B } - tập cạnh từ ngoài B đi vào B.
W+(B) = { (a, b) ∈ E | a ∈ B, b ∉ B } - tập cạnh từ B đi ra khỏi B.
Khi đó nếu tập con các đỉnh B không chứa x0 và z thì: t (W-(B)) =t (W+(B)).Theo tính chất b) của luồng: ∑ t (W-(x)) =∑ t (W+(x)).
Cạnh kề với đỉnh x nếu có đỉnh đầu và đỉnh cuối đều nằm trong tập B thì nó sẽ có mặt ở cả hai vế củađẳng thức đúng một lần, do đó có thể giản ước.
Một số thuật toán về luồng cực đại.
Bài toán luồng cực đại trên mạng:.
Lát cắt. Đường tăng luồng.
Định nghĩa. Ta gọi lát cắt (X,X*) là một cách phân hoạch tập đỉnh V của mạng ra thành hai tập X và X*=V \ X, trong đó s ∈ X và t ∈ X*. Khả năng thông qua của lát cắt (X,X*) là số
Lát cắt với khả năng thông qua nhỏ nhất được gọi là lát cắt hẹp nhất.