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:
Đá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
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
1. Đỉnh 1: Bắt đầu từ đỉnh 1.
2. Các đỉnh kề của 1: Duyệt các đỉnh kề của 1 là 2, 4, 7.
3. Đỉnh 2:
4. Đỉnh 4:
5. Đỉnh 7:
6. Các đỉnh kề của 2: Duyệt các đỉnh kề của 2 là 3, 6.
7. Đỉnh 3:
8. Đỉnh 6:
9. Các đỉnh kề của 4: Duyệt các đỉnh kề của 4 là 8, 5, 9.
10. Đỉnh 8:
11. Đỉnh 5:
12. Đỉnh 9:
13. Các đỉnh kề của 7: Duyệt các đỉnh kề của 7 là 10.
14. Đỉnh 10:
Vậy thứ tự duyệt các đỉnh là: 1, 2, 4, 7, 3, 6, 8, 5, 9, 10.
Trong đồ thị đã cho, bắt đầu từ đỉnh 10, ta có thể duyệt theo các bước sau:
1. 10: Bắt đầu từ đỉnh 10.
2. 4: Từ 10, duyệt đến 4 (hoặc 5, thứ tự duyệt có thể khác nhau tùy thuộc vào cách cài đặt, nhưng kết quả cuối cùng phải tuân theo DFS).
3. 5: Từ 4, có thể duyệt đến 5.
4. 1: Từ 5, có thể duyệt đến 1.
5. 2: Từ 1, duyệt đến 2.
6. 3: Từ 2, duyệt đến 3.
7. 6: Từ 3, duyệt đến 6.
8. 9: Từ 6, duyệt đến 9.
9. 8: Từ 9, duyệt đến 8.
10. 7: Từ 8, duyệt đến 7.
Như vậy, kết quả của thuật toán DFS(10) là: 10, 4, 5, 1, 2, 3, 6, 9, 8, 7
Phương án C: ¬(P ∧ Q) ∨ (P ∨ Q) tương đương với (¬P ∨ ¬Q) ∨ (P ∨ Q) tương đương với (¬P ∨ P) ∨ (¬Q ∨ Q) tương đương với True.
tương đương logic với mệnh đề nào sau đây?
