Trong thuật toán Ford – Fullkerson tìm luồng cực đại, thực hiện lặp đi lặp lại thao tác:
Đáp án đúng: A
Thuật toán Ford-Fulkerson là một thuật toán kinh điển để tìm luồng cực đại trong một mạng lưới. Thuật toán này hoạt động bằng cách lặp đi lặp lại hai bước chính cho đến khi không thể tăng luồng được nữa:
- Tìm đường tăng luồng: Tìm một đường đi từ đỉnh nguồn (source) đến đỉnh đích (sink) trên đồ thị còn dư (residual graph). Đồ thị còn dư thể hiện khả năng tăng thêm luồng trên các cạnh của mạng.
- Cải tiến luồng: Nếu tìm thấy đường tăng luồng, sẽ tăng luồng dọc theo đường đi đó. Việc này đồng nghĩa với việc tăng luồng trên các cạnh xuôi (forward edges) và giảm luồng trên các cạnh ngược (backward edges) của đường đi.
Như vậy, thao tác lặp đi lặp lại chính là "Đánh dấu các đỉnh và cải tiến luồng". Việc đánh dấu các đỉnh được thực hiện trong quá trình tìm đường tăng luồng, còn việc cải tiến luồng là bước cập nhật luồng dựa trên đường tăng luồng tìm được.
Bộ 525 câu hỏi trắc nghiệm ôn thi môn Toán rời rạc có đáp án dưới đây sẽ là tài liệu ôn tập hữi ích dành cho các bạn sinh viên. Mời các bạn cùng tham khảo!
Câu hỏi liên quan
Trong đồ thị vô hướng, tổng bậc của tất cả các đỉnh bằng hai lần số cạnh. Vì vậy, tổng bậc của tất cả các đỉnh là một số chẵn. Để tổng này là một số chẵn, số lượng đỉnh bậc lẻ phải là một số chẵn. Vì nếu số đỉnh bậc lẻ là một số lẻ, thì tổng bậc của các đỉnh bậc lẻ sẽ là một số lẻ, và do đó tổng bậc của tất cả các đỉnh cũng sẽ là một số lẻ, điều này mâu thuẫn với thực tế là tổng bậc phải là một số chẵn.
1. Khởi tạo: Chọn một đỉnh bất kỳ làm đỉnh bắt đầu. Trong ví dụ này, ta có thể chọn đỉnh 1.
2. Lặp:
* Tìm cạnh có trọng số nhỏ nhất nối đỉnh đã chọn với một đỉnh chưa được chọn.
* Thêm cạnh này vào cây khung.
* Thêm đỉnh mới vào tập các đỉnh đã chọn.
3. Kết thúc: Lặp lại bước 2 cho đến khi tất cả các đỉnh đều thuộc cây khung.
Áp dụng thuật toán Prim cho đồ thị đã cho:
1. Bắt đầu từ đỉnh 1.
2. Các cạnh kề với đỉnh 1: (1,4) = 5, (1,5) = 9. Chọn cạnh (1,4) vì có trọng số nhỏ nhất. Tập cạnh T = {(1,4)}.
3. Các đỉnh đã chọn: {1, 4}.
4. Các cạnh kề với {1, 4}: (1,5) = 9, (4,7) = 2, (4,5) = 5. Chọn cạnh (4,7) vì có trọng số nhỏ nhất. Tập cạnh T = {(1,4), (4,7)}.
5. Các đỉnh đã chọn: {1, 4, 7}.
6. Các cạnh kề với {1, 4, 7}: (1,5) = 9, (4,5) = 5, (7,3) = 3. Chọn cạnh (7,3) vì có trọng số nhỏ nhất. Tập cạnh T = {(1,4), (4,7), (7,3)}.
7. Các đỉnh đã chọn: {1, 4, 7, 3}.
8. Các cạnh kề với {1, 4, 7, 3}: (1,5) = 9, (4,5) = 5, (3,2) = 4, (3,5) = 6, (3,6) = 7. Chọn cạnh (3,2) vì có trọng số nhỏ nhất. Tập cạnh T = {(1,4), (4,7), (7,3), (3,2)}.
9. Các đỉnh đã chọn: {1, 4, 7, 3, 2}.
10. Các cạnh kề với {1, 4, 7, 3, 2}: (1,5) = 9, (4,5) = 5, (3,5) = 6, (3,6) = 7, (2,5) = 8, (2,6) = 1. Chọn cạnh (2,6) vì có trọng số nhỏ nhất. Tập cạnh T = {(1,4), (4,7), (7,3), (3,2), (2,6)}.
11. Các đỉnh đã chọn: {1, 4, 7, 3, 2, 6}.
12. Các cạnh kề với {1, 4, 7, 3, 2, 6}: (1,5) = 9, (4,5) = 5, (3,5) = 6, (6,5) = 3. Chọn cạnh (6,5) vì có trọng số nhỏ nhất. Tập cạnh T = {(1,4), (4,7), (7,3), (3,2), (2,6), (6,5)}.
13. Các đỉnh đã chọn: {1, 4, 7, 3, 2, 6, 5}.
Vậy cây khung nhỏ nhất H = (V, T) có tập cạnh T = {(4,1), (7,4), (3,7), (2,3), (6,2), (5,6)} tương ứng với đáp án T ={(5,3)(3,7)(2,3)(6,2)(4,1)(7,4)} sau khi sắp xếp lại các đỉnh.
Ta có: \(\overline Q \vee (P \wedge Q) \equiv (\overline Q \vee P) \wedge (\overline Q \vee Q) \equiv (\overline Q \vee P) \wedge 1 \equiv \overline Q \vee P\)
Hay \(P \vee \overline Q \)
Luật kéo theo (hay còn gọi là luật suy ra) trong logic mệnh đề phát biểu rằng: một mệnh đề kéo theo \(p \to q\) tương đương với mệnh đề phủ định của \(p\) hoặc \(q\). Hay nói cách khác, \(p \to q\) đúng khi và chỉ khi \(p\) sai hoặc \(q\) đúng.
Công thức chính xác của luật kéo theo là: \(p \to q \Leftrightarrow \overline{p} \vee q\)
Vậy, đáp án đúng là đáp án 1.
