Câu hỏi: 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:

A. Đánh dấu các đỉnh và cải tiến luồng.

B. Nâng giá trị luồng.

C. Giảm giá trị luồng. 

D. Giảm khả năng thông qua của các cạnh.

Câu 1: Trong biểu diễn đồ thị bởi danh sách kề, mỗi đỉnh của đồ thị có một danh sách:

A. Các cạnh kề với đỉnh đó

B. Các bậc của đỉnh kề với đỉnh đó

C. Các đỉnh kề với đỉnh đó

D. Các cạnh kề với cạnh đó

Câu 2: Đồ thị vô hướng G = (V,E) được gọi là liên thông nếu.

A. Giữa hai đỉnh bất kỳ \(u,v \in V\) luôn tồn tại đường đi từ u đến v.

B. Nếu \(u,v \in V\) , thì tồn tại v khác u sao cho v liên thông với u.

C. Nếu \(u,v \in V\) , thì với mọi v khác u đều kề với u.

D. Nếu \(u,v \in V\) , thì tồn tại đỉnh v khác u kề với u. 

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.

Câu 4: Để 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.

Câu 5: Nếu một đơn đồ thị phẳng liên thông có n đỉnh, m cạnh \((n≥ 3)\) thì:

A. \(m ≠ 2n - 4\)

B. \(m = 2n - 4\)

C. \(m ≤ 2n - 4\)

D. \(m ≥ 2n - 4\)

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.