Giá trị của luồng cực đại trong mạng:
Đáp án đúng: C
Câu hỏi liên quan
Vậy đáp án đúng là B: G chứa cạnh bội.
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.
Tổng bậc của đồ thị bằng hai lần số cạnh. Gọi số cạnh của đồ thị là m. Theo đề bài, đồ thị có 10 đỉnh, mỗi đỉnh có bậc bằng 6. Vậy, tổng bậc của đồ thị là 10 * 6 = 60. Suy ra, 2 * m = 60, vậy m = 30.
Trong trường hợp này, bắt đầu từ đỉnh G, ta có thể duyệt theo thứ tự sau:
1. G: Bắt đầu từ đỉnh G.
2. H: Duyệt đến đỉnh H kề với G.
3. N: Duyệt đến đỉnh N kề với H.
4. K: Duyệt đến đỉnh K kề với N.
5. B: Duyệt đến đỉnh B kề với K.
6. A: Duyệt đến đỉnh A kề với B.
7. C: Duyệt đến đỉnh C kề với A.
8. D: Duyệt đến đỉnh D kề với C.
9. E: Duyệt đến đỉnh E kề với D.
10. I: Duyệt đến đỉnh I kề với K.
11. F: Duyệt đến đỉnh F kề với E.
Vậy, thứ tự duyệt đúng là: G, H, N, K, B, A, C, D, E, I, F
tương đương logic với mệnh đề nào sau đây?
