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

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

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

B. Giữa hai đỉnh bất kỳ \(u,v \in V\) luôn tìm được đường đi từ u đến v

C. Giữa hai đỉnh bất kỳ \(u,v \in V\) luôn tìm được đường đi từ v đến u

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

Câu 2: Trong thuật toán Ford – Fullkerson giải bài toán luồng cực đại, bước tăng luồng thực hiện trên.

A. Các cạnh nằm ngoài đường đi đánh dấu.

B. Các cạnh nằm trên đường đi đánh dấu

C. Trên cạnh nối đỉnh phát với đỉnh thu.

D. Trên đỉnh phát và đỉnh thu.

Câu 3: Hãy cho biết đồ thị nào dưới đây là một cây?

A.

B.

C.

D.

Câu 4: Đồ 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 5: Ta nói cặp hai đỉnh (u,v) là cạnh vô hướng của đồ thị G = (V,E) nếu:

A. \(u, v \times V\) và u, v có thứ tự

B. \(u, v \times V\) và u, v có thứ tự

C. \(u, v \times V\) và u, v không có thứ tự

D. \(u, v \times V\) và u, v không có thứ tự

Câu 6: Để xây dựng cây khung nhỏ nhất của đồ thị, ta dùng:

A. Tìm kiếm theo chiều sâu (DFS).

B. Thuật toán Floyd.

C. Thuật toán Prim.

D. Thuật toán Dijsktra.