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: 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 2: Đồ 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 3: Nếu G = (V,E) là một đơn đồ thị vô hướng thì: (Chọn phương án đúng)

A. Ma trận kề gồm các phần tử đối xứng nhau qua đường chéo chính

B. Ma trận kề gồm các phần tử không đối xứng nhau qua đường chéo chính

C. Các phần tử trên đướng chéo chính bằng 1

D. Các phần tử trên đường chéo phụ bằng 1

Câu 4: Số cạnh của cây với 1000 đỉnh là:

A. 9900

B. 9999

C. 10000

D. 1001

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: Giá trị của luồng cực đại trong mạng:

A. Lớn hơn khả năng thông qua của mọi lát cắt.

B. Bằng khả năng thông qua của một lát cắt.

C. Không vượt quá khả năng thông qua của lát cắt hẹp nhất trong mạng.

D. Không vượt quá khả năng thông qua của lát cắt lớn nhất trong mạng.