Máy Tính Luồng Mạng (Luồng Cực Đại)

Tính dòng chảy tối đa từ nguồn đến đích trong mạng có hướng giới hạn dung lượng bằng Ford-Fulkerson với Edmonds-Karp. Hoạt hình mọi đường tăng dòng và hiển thị dung lượng dư, cạnh bão hòa và lát cắt tối thiểu chứng minh.

Sử dụng miễn phíKhông cần đăng kýKết quả tức thì

Máy Tính Luồng Mạng (Luồng Cực Đại)Dùng thử ngay — miễn phí ▼

Ví dụ nhanh:

Sách giáo khoa (6 đỉnh) Mạng nhỏ CLRS cổ điển Dạng phân đôi Đầu vào ma trận

↦ Danh sách cạnh với dung lượng ▦ Ma trận dung lượng

Dữ liệu mạng

Định dạng cạnh: A -> B : 10 (mũi tên kèm dung lượng), hoặc A, B, 10. Định dạng ma trận: mỗi hàng một dòng, C[i][j] là dung lượng của cạnh i → j (dùng 0 nếu không có cạnh). Đường chéo phải bằng 0.

Nhãn ma trận (tùy chọn)

Các nhãn cách nhau bằng dấu phẩy hoặc dấu cách, mỗi nhãn cho một hàng ma trận. Mặc định là S, A, B, …, T.

Đỉnh nguồn ⭘

Đỉnh đích ⬤

Embed Máy Tính Luồng Mạng (Luồng Cực Đại) Widget

Giới thiệu về Máy Tính Luồng Mạng (Luồng Cực Đại)

Máy tính Luồng Mạng Luồng Cực Đại tính toán luồng cực đại từ một nguồn s đã chọn đến một đích t đã chọn trong bất kỳ mạng có hướng nào có dung lượng. Bên dưới hệ thống, nó chạy phương pháp Ford-Fulkerson với các đường tăng luồng tìm kiếm theo chiều rộng (thuật toán Edmonds-Karp), sau đó ghi lại mọi đường đi tìm thấy để bạn có thể xem lại toàn bộ quá trình quyết định qua từng bước lặp. Trang kết quả cũng hiển thị lát cắt tối tiểu (min-cut) — phân hoạch nút thắt cổ chai chứng minh giá trị luồng của bạn thực sự là tối ưu.

Bài toán Luồng Cực đại là gì?

Một mạng luồng là một đồ thị có hướng G = (V, E) cùng với một hàm dung lượng c: E → ℝ_≥0. Hai đỉnh được phân biệt: nguồn s (nơi luồng bắt đầu) và đích t (nơi luồng được tiêu thụ). Một luồng f là bất kỳ sự gán giá trị f(u, v) ≥ 0 nào trên các cạnh tuân thủ:

Dung lượng: 0 ≤ f(u, v) ≤ c(u, v) cho mỗi cạnh (u, v) Bảo toàn: Σ f(w, v) = Σ f(v, w) cho mỗi v ∈ V \ {s, t} Giá trị luồng: |f| = Σ f(s, w) − Σ f(w, s) (luồng thuần túy rời khỏi s)

Bài toán luồng cực đại tìm luồng f sao cho tối đa hóa |f|. Một cách trực quan: nếu các cạnh là các đường ống nước với dung lượng đã cho, bạn có thể vận chuyển bao nhiêu lít mỗi giây từ s đến t?

Cách thuật toán hoạt động — Ford-Fulkerson với BFS

Thuật toán duy trì một đồ thị dư song song với luồng hiện tại. Đối với mỗi cạnh (u, v) với dung lượng c và luồng hiện tại f, đồ thị dư chứa:

một cạnh dư thuận (u, v) với dung lượng c − f (còn có thể đẩy thêm bao nhiêu), và
một cạnh dư nghịch (v, u) với dung lượng f (có thể hủy bỏ bao nhiêu phần luồng đã cam kết).

Tại mỗi bước lặp, nó thực hiện tìm kiếm theo chiều rộng (BFS) từ s đến t trên đồ thị dư. Nếu tìm thấy một đường đi, dung lượng cạnh nhỏ nhất trên đường đó — nút thắt cổ chai — sẽ được cộng vào luồng trên mỗi cạnh thuận và trừ đi trên mỗi cạnh nghịch dọc theo đường đi. Đây được gọi là một đường tăng luồng. Khi BFS không còn có thể chạm tới t, luồng hiện tại là tối ưu.

khi còn tồn tại đường tăng luồng P từ s đến t trong đồ thị dư: b ← min c_residual(u, v) cho các cạnh (u, v) trong P đẩy b đơn vị luồng dọc theo P // cập nhật đồ thị dư + luồng trả về tổng luồng |f|

Sử dụng BFS (thay vì tìm đường đi tùy ý) biến Ford-Fulkerson thành Edmonds-Karp, với thời gian chạy được đảm bảo là O(V · E²). Nó cũng đảm bảo kết thúc đối với các dung lượng vô tỷ, điều mà Ford-Fulkerson thuần túy không làm được.

Định lý Luồng Cực đại Lát cắt Tối tiểu

Một lát cắt là một phân hoạch các đỉnh thành hai tập (S, T) với s ∈ S và t ∈ T. Dung lượng của nó là tổng dung lượng của các cạnh đi từ S đến T:

cap(S, T) = Σ c(u, v) cho u ∈ S, v ∈ T

Định lý luồng cực đại lát cắt tối tiểu (Ford & Fulkerson, 1956) phát biểu:

giá trị luồng cực đại = dung lượng lát cắt tối tiểu

Công cụ này tự động tìm lát cắt tối tiểu. Sau khi Edmonds-Karp kết thúc, nó chạy thêm một lần BFS từ s trên đồ thị dư; các đỉnh có thể chạm tới tạo thành S, phần còn lại tạo thành T, và mọi cạnh đi qua S → T trong đồ thị ban đầu đều bão hòa. Tổng dung lượng của chúng đúng bằng giá trị luồng cực đại — có thể thấy trong kết quả chính là "Dung lượng lát cắt tối tiểu ✓ xác nhận tính tối ưu".

Các tính năng được xây dựng để học tập

Hoạt ảnh từng bước. Xem lại mọi đường tăng luồng với các điều khiển phát, tạm dừng và từng bước. Xem BFS đã chọn đường nào, cạnh nào là nút thắt cổ chai và tổng lũy kế đã tăng trưởng như thế nào.
Ba ma trận đồng bộ. Chuyển đổi giữa ma trận dung lượng C, ma trận luồng cuối cùng f và ma trận dư C − f — ba hình ảnh cùng nhau đặc trưng cho bất kỳ luồng nào.
Chế độ xem phân hoạch lát cắt tối tiểu. Các đỉnh phía S và phía T được liệt kê dưới dạng các thẻ (chips) với các cạnh bão hòa đi qua được làm nổi bật bằng màu đỏ.
Bảng kê từng cạnh. Đối với mỗi cạnh: dung lượng, luồng, phần dư, thanh mức độ sử dụng và nhãn bão hòa.
Bố cục phân lớp từ trái sang phải. Bản vẽ đồ thị được tính toán từ khoảng cách BFS từ nguồn, vì vậy luồng nước hiển thị rõ ràng "chảy" từ trái sang phải — đúng như cách các sách giáo khoa trình bày.

Định dạng đầu vào

1. Danh sách cạnh với dung lượng

Mỗi cạnh trên một dòng. Dạng mũi tên là dễ đọc nhất nhưng có một số lựa chọn thay thế khác cũng hoạt động:

S -> A : 10 S -> B : 13 A -> B : 10 B -> A : 4 B -> T : 14

Cũng chấp nhận: A, B, 10 · A B 10 · A -> B , 10. Nhiều cạnh giữa cùng một cặp đỉnh sẽ được cộng dồn.

2. Ma trận dung lượng

Mỗi hàng trên một dòng, các giá trị cách nhau bởi dấu cách hoặc dấu phẩy. Giá trị C[i][j] là dung lượng của cạnh từ đỉnh i đến đỉnh j. Dùng 0 cho trường hợp "không có cạnh". Ma trận phải là ma trận vuông và đường chéo phải bằng 0 (không có vòng lặp tự thân).

S A B C D T S [ 0 10 0 10 0 0 ] A [ 0 0 4 2 8 0 ] B [ 0 0 0 0 0 10 ] C [ 0 0 0 0 9 0 ] D [ 0 0 6 0 0 10 ] T [ 0 0 0 0 0 0 ]

Nhập các nhãn đỉnh tương ứng vào trường Nhãn ma trận (cách nhau bằng dấu phẩy hoặc dấu cách). Nếu bỏ trống, nhãn mặc định sẽ là S, A, B, …, T.

Ứng dụng của Luồng Cực đại

Lĩnh vực	Cách luồng cực đại được sử dụng
Vận tải & hậu cần	Mạng lưới đường sắt/đường bộ/đường ống có thể vận chuyển bao nhiêu hàng hóa mỗi ngày từ điểm xuất phát đến điểm đích?
Ghép cặp phân đôi	Gán việc làm cho công nhân, sinh viên cho các dự án. Luồng cực đại với dung lượng đơn vị cho ra cặp ghép cực đại.
Phân đoạn hình ảnh	Lát cắt tối tiểu Boykov–Kolmogorov trong thị giác máy tính tách biệt các điểm ảnh tiền cảnh khỏi hậu cảnh.
Độ tin cậy mạng	Lát cắt tối tiểu xác định các liên kết yếu nhất mà nếu hỏng hóc sẽ làm mất kết nối mạng.
Lập kế hoạch dự án	Các bài toán bao đóng và bài toán lựa chọn được đưa về lát cắt tối tiểu.
Loại trừ trong bóng chày	Xác định xem một đội có bị loại về mặt toán học khỏi cuộc đua giành chức vô địch giải đấu hay chưa.

Ví dụ minh họa

Ví dụ nhanh "Sách giáo khoa" mã hóa một mạng 6 nút với nguồn S và đích T. Chạy Edmonds-Karp cho ra bốn đường tăng luồng:

S → A → B → T với nút thắt 4 (cạnh A-B là điểm giới hạn). Tổng lũy kế: 4.
S → A → D → T với nút thắt 6. Tổng lũy kế: 10.
S → C → D → T với nút thắt 4 (cạnh D-T hiện là điểm giới hạn, chỉ còn 4). Tổng lũy kế: 14.
S → C → D → B → T với nút thắt 5. Tổng lũy kế: 19.

Thuật toán dừng lại — không còn đường tăng luồng nào tồn tại. Lát cắt tối tiểu là (S = {S, C}, T = {A, B, D, T}) với các cạnh đi ngang qua S → A (dung lượng 10) và C → D (dung lượng 9), tổng cộng là 19 — đúng bằng giá trị luồng cực đại.

Cách sử dụng máy tính này

Chọn định dạng đầu vào bằng các tab — danh sách cạnh (khuyên dùng) hoặc ma trận dung lượng.
Nhập mạng của bạn. Bạn có thể bắt đầu từ một ví dụ nhanh và sửa đổi nó. Đối với đầu vào ma trận, hãy cung cấp nhãn nếu bạn muốn tên khác ngoài S, A, B, …, T.
Chỉ định nguồn và đích (hoặc để trống để tự động phát hiện S và T).
Nhấp Tính toán Luồng Cực đại. Trang kết quả hiển thị giá trị luồng cực đại, phân hoạch lát cắt tối tiểu, trực quan hóa đồ thị phân lớp, mọi đường tăng luồng, bảng sử dụng cạnh và ba ma trận (dung lượng, luồng, phần dư).
Phát hoạt ảnh bên dưới đồ thị để xem lại các quyết định của thuật toán. Nhấp vào bất kỳ bước tăng luồng nào để nhảy trực tiếp đến đó.

Giới hạn

Đỉnh: tối đa 30 — để giữ cho việc trực quan hóa và các ma trận dễ đọc.
Cạnh: tối đa 200.
Dung lượng: không âm, lên đến 10⁹. Cho phép dung lượng là số thập phân.
Không có vòng lặp tự thân. Các vòng lặp tự thân không mang luồng trong công thức luồng cực đại tiêu chuẩn và sẽ bị từ chối.

Câu hỏi thường gặp

Bài toán luồng cực đại là gì?

Cho một mạng có hướng trong đó mỗi cạnh có một dung lượng không âm, bài toán luồng cực đại đặt câu hỏi: có thể đẩy bao nhiêu luồng từ một đỉnh nguồn s được chỉ định đến một đỉnh đích t được chỉ định, tuân theo các quy tắc rằng luồng trên mỗi cạnh không được vượt quá dung lượng của nó và luồng đi vào mọi đỉnh không phải nguồn, không phải đích phải bằng luồng đi ra khỏi nó? Câu trả lời được gọi là giá trị luồng cực đại.

Phương pháp Ford-Fulkerson là gì?

Ford-Fulkerson là một kỹ thuật tổng quát để tính toán luồng cực đại. Nó lặp đi lặp lại việc tìm một đường tăng luồng từ nguồn đến đích trong đồ thị dư và đẩy lượng luồng lớn nhất có thể dọc theo đường đó (dung lượng nút thắt cổ chai), sau đó cập nhật đồ thị dư. Quy trình kết thúc khi không còn đường tăng luồng nào tồn tại. Khi được triển khai với tìm kiếm theo chiều rộng để chọn đường đi, nó được gọi là Edmonds-Karp và chạy trong thời gian O(V · E²) thời gian.

Lát cắt tối tiểu của mạng luồng là gì?

Một lát cắt là một phân hoạch các đỉnh thành hai tập S và T sao cho nguồn nằm trong S và đích nằm trong T. Dung lượng của lát cắt là tổng dung lượng của các cạnh từ S đến T. Lát cắt tối tiểu là lát cắt có dung lượng nhỏ nhất. Định lý luồng cực đại lát cắt tối tiểu nổi tiếng chứng minh rằng giá trị luồng cực đại luôn bằng dung lượng lát cắt tối tiểu, vì vậy việc tìm thấy cái này sẽ cho bạn cái kia miễn phí.

Đồ thị dư là gì?

Đồ thị dư theo dõi lượng luồng còn lại có thể được đẩy trên mỗi cạnh. Đối với mỗi cạnh ban đầu (u, v) với dung lượng c và luồng hiện tại f, đồ thị dư chứa một cạnh thuận (u, v) với dung lượng c trừ f (dung lượng còn lại) và một cạnh nghịch (v, u) với dung lượng f (luồng có thể hủy bỏ). Một đường tăng luồng sử dụng các cạnh của đồ thị dư, cho phép thuật toán hoàn tác các quyết định trước đó.

Tại sao công cụ sử dụng BFS cho các đường tăng luồng?

Việc chọn các đường tăng luồng bằng tìm kiếm theo chiều rộng (Edmonds-Karp) đảm bảo kết thúc trong thời gian đa thức bất kể dung lượng cạnh. Ford-Fulkerson thuần túy với chiến lược tìm đường đi tùy ý có thể lặp lại số lần mũ trên các đầu vào bệnh lý, và trên các dung lượng vô tỷ, nó có thể không bao giờ kết thúc. BFS cũng tạo ra các đường tăng luồng ngắn nhất, dễ đọc và dễ suy luận hơn.

Cạnh bão hòa có nghĩa là gì?

Một cạnh được gọi là bão hòa khi luồng của nó bằng dung lượng của nó, vì vậy không thể đẩy thêm luồng nào qua nó nữa. Các cạnh bão hòa là các nút thắt cổ chai của mạng, và mọi lát cắt tối tiểu đều bao gồm toàn bộ các cạnh bão hòa từ phía S sang phía T của lát cắt. Công cụ làm nổi bật các cạnh bão hòa bằng màu đỏ để bạn có thể thấy cấu trúc nút thắt cổ chai ngay lập tức.

Đọc thêm

Tham khảo nội dung, trang hoặc công cụ này như sau:

"Máy Tính Luồng Mạng (Luồng Cực Đại)" tại https://MiniWebtool.com/vi/may-tinh-luong-mang-luong-cuc-ai/ từ MiniWebtool, https://MiniWebtool.com/

bởi đội ngũ miniwebtool. Cập nhật: 22 tháng 4, 2026

Bạn cũng có thể thử AI Giải Toán GPT của chúng tôi để giải quyết các vấn đề toán học của bạn thông qua câu hỏi và trả lời bằng ngôn ngữ tự nhiên.