Trong biểu diễn đồ thị bằng danh sách kề, mỗi danh sách kề chứa:
Đáp án đúng: B
Trong biểu diễn đồ thị bằng danh sách kề, mỗi phần tử trong danh sách kề của một đỉnh u sẽ chứa thông tin về một đỉnh v kề với đỉnh u. Điều này có nghĩa là, danh sách kề của một đỉnh sẽ liệt kê tất cả các đỉnh mà đỉnh đó có cạnh nối trực tiếp tới.
- Phương án 1 không chính xác vì danh sách kề chứa các đỉnh kề, không phải các cạnh kề. Cạnh kề được ngụ ý từ việc liệt kê đỉnh kề.
- Phương án 2 chính xác vì danh sách kề của một đỉnh chứa các đỉnh kề với nó.
- Phương án 3 không chính xác vì danh sách kề chỉ chứa các đỉnh kề, không chứa tất cả các đỉnh và cạnh kề.
- Phương án 4 không chính xác vì danh sách kề không chứa thông tin về bậc của đỉnh kề.
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
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.
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.
