JavaScript is required

Giá trị của luồng cực đại trong mạng:

A.

Lớn hơn khả năng thông qua của mọi lát cắt.

B.

Bằng khả năng thông qua của một lát cắt.

C.

Không vượt quá khả năng thông qua của lát cắt hẹp nhất trong mạng.

D.

Không vượt quá khả năng thông qua của lát cắt lớn nhất trong mạng.

Trả lời:

Đáp án đúng: C


Giá trị của luồng cực đại trong mạng bị giới hạn bởi lát cắt hẹp nhất. Lát cắt hẹp nhất (min cut) là lát cắt có khả năng thông qua nhỏ nhất. Luồng cực đại không thể vượt quá khả năng thông qua của lát cắt hẹp nhất này, vì nó tạo thành nút thắt cổ chai cho luồng đi qua mạng. Do đó, đáp án C là chính xác.

Câu hỏi liên quan