Câu hỏi: G là một đơn đồ thị phẳng liên thông n đỉnh, m cạnh, gọi r là số miền trong biểu diễn phẳng của G khi đó:
A. \(r ≠ m – n +2\)
B. \(r = m – n +2 \)
C. \(r ≥ m – n +2\)
D. \(r ≤ m – n +2\)
Câu 1: Theo định lý Ford – Fulkerson giá trị luồng cực đại từ điểm phát s đến điểm thu t.
A. Bằng khả năng thông qua của lát cắt hẹp nhất tách điểm s và t.
B. Bằng khả năng thông qua của lát cắt lớn nhất tách điểm s và t.
C. Không vượt quá khả năng thông qua của lát cắt lớn nhất tách điểm s và t.
D. Tất cả các đáp án đều sai
30/08/2021 2 Lượt xem
Câu 2: Nếu G = (V,E) là một đa đồ thị vô hướng thì:
A. G không có khuyên
B. G chứa cạnh bội
C. G không có cạnh bội.
D. G có thể có cạnh có hướng
30/08/2021 2 Lượt xem
Câu 3: Sự khác nhau giữa thuật toán Prim và thuật toán Kruskal:
A. Thuật toán Prim chọn các cạnh có trọng số tối thiểu, liên thuộc trong khi thuật toán Kruskal chọn các cạnh có trọng số tối thiểu, mà không nhất thiết phải liên thuộc.
B. Thuật toán Prim chọn các cạnh có trọng số tối thiểu, liên thuộc với một đỉnh thuộc cây khung và không tạo thành chu trình. Thuật toán Kruskal chọn các cạnh có trọng số tối thiểu, mà không nhất thiết phải liên thuộc với các đỉnh đã thuộc cây khung và không tạo thành chu trình.
C. Thuật toán Prim chọn các cạnh có trọng số tối thiểu, mà không nhất thiết phải liên thuộc với các đỉnh đã thuộc cây và không tạo thành chu trình. Thuật toán Kruskal chọn các cạnh có trọng số tối thiểu, liên thuộc với các đỉnh đã thuộc cây và không tạo thành chu trình.
D. Thuật toán Prim chọn các cạnh có trọng số tối thiểu, không liên thuộc với một đỉnh thuộc cây khung và không tạo thành chu trình. Thuật toán Kruskal chọn các cạnh có trọng số tối thiểu, mà không nhất thiết phải liên thuộc với các đỉnh đã thuộc cây khung và không tạo thành chu trình.
30/08/2021 1 Lượt xem
Câu 4: Thuật toán Dijkstra được dùng để:
A. Tìm đường đi ngắn nhất giữa các cặp đỉnh bất kì của đồ thị.
B. Tìm đường đi ngắn nhất từ một đỉnh đến các đỉnh còn lại của đồ thị
C. Tìm đường đi ngắn nhất giữa hai đỉnh của đồ thị.
D. Tìm đường đi ngắn nhất giữa một đỉnh nguồn và một đỉnh đích.
30/08/2021 2 Lượt xem
Câu 5: Để xây dựng cây khung nhỏ nhất của đồ thị, ta dùng: (Chọn phương án đúng)
A. Thuật toán Dijsktra.
B. Tìm kiếm theo chiều rộng (BFS).
C. Tìm kiếm theo chiều sâu (DFS).
D. Thuật toán Prim.
30/08/2021 1 Lượt xem
Câu 6: Thuật toán Kruskal áp dụng cho đồ thì G, n đỉnh sẽ dừng khi:
A. Kết nạp được n-1 cạnh vào cây khung.
B. Kết nạp được n cạnh vào cây khung.
C. Kết nạp được n – 2 cạnh vào cây khung.
D. Kết nạp được n - 3 cạnh vào cây khung.
30/08/2021 1 Lượt xem
Câu hỏi trong đề: Bộ câu hỏi trắc nghiệm môn Toán rời rạc - Phần 14
- 38 Lượt thi
- 60 Phút
- 30 Câu hỏi
- Sinh viên
Cùng chủ đề Bộ câu hỏi trắc nghiệm môn Toán rời rạc có đáp án
- 2.6K
- 206
- 30
-
14 người đang thi
- 967
- 72
- 30
-
38 người đang thi
- 1.0K
- 47
- 30
-
66 người đang thi
- 666
- 33
- 30
-
86 người đang thi
Chia sẻ:
Đăng Nhập để viết bình luận