Cho mạng G, điểm phát s điểm thu t. Lát cắt (X, Y) được gọi là lát cắt hẹp nhất nếu:
Trả lời:
Đáp án đúng: D
Trong một mạng luồng, lát cắt (X, Y) là một cách chia tập hợp các đỉnh thành hai tập X và Y sao cho s ∈ X và t ∈ Y. Khả năng thông qua của lát cắt (X, Y) là tổng khả năng thông qua của các cung đi từ X sang Y. Bài toán tìm lát cắt hẹp nhất (min-cut) là tìm lát cắt có khả năng thông qua nhỏ nhất. Theo định lý luồng cực đại - lát cắt cực tiểu, luồng cực đại từ s đến t bằng khả năng thông qua của lát cắt hẹp nhất.
Phương án D đúng vì lát cắt hẹp nhất được định nghĩa là lát cắt có khả năng thông qua bé nhất trong tất cả các lát cắt từ s đến t.