JavaScript is required

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:

A.

khả năng thông qua của lát cắt (X, Y) bằng tổng khả năng thông qua của các cung đi ra khỏi đỉnh s

B.

khả năng thông qua của lát cắt (X, Y) bằng tổng khả năng thông qua của các cung đi vào đỉnh t

C.

khả năng thông qua của lát cắt (X, Y) lớn nhất.

D.

khả năng thông qua của lát cắt (X, Y) bé nhất.

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.

Câu hỏi liên quan