Đáp án đúng: D
Câu hỏi liên quan
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
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

Bộ Đồ Án Tốt Nghiệp Ngành Trí Tuệ Nhân Tạo Và Học Máy

Bộ 120+ Đồ Án Tốt Nghiệp Ngành Hệ Thống Thông Tin

Bộ Đồ Án Tốt Nghiệp Ngành Mạng Máy Tính Và Truyền Thông

Bộ Luận Văn Tốt Nghiệp Ngành Kiểm Toán

Bộ 370+ Luận Văn Tốt Nghiệp Ngành Kế Toán Doanh Nghiệp

Bộ Luận Văn Tốt Nghiệp Ngành Quản Trị Thương Hiệu
ĐĂNG KÝ GÓI THI VIP
- Truy cập hơn 100K đề thi thử và chính thức các năm
- 2M câu hỏi theo các mức độ: Nhận biết – Thông hiểu – Vận dụng
- Học nhanh với 10K Flashcard Tiếng Anh theo bộ sách và chủ đề
- Đầy đủ: Mầm non – Phổ thông (K12) – Đại học – Người đi làm
- Tải toàn bộ tài liệu trên TaiLieu.VN
- Loại bỏ quảng cáo để tăng khả năng tập trung ôn luyện
- Tặng 15 ngày khi đăng ký gói 3 tháng, 30 ngày với gói 6 tháng và 60 ngày với gói 12 tháng.