Câu hỏi: 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 1: Nếu G = (V,E) là một đơn đồ thị vô hướng thì:

A. G không có khuyên, không có cạnh bội.

B. G không có khuyên, có thể có cạnh bội.

C. G có khuyên, không có cạnh bội.

D. G có khuyên, có thể có cạnh bội.

Câu 2: Thuật toán Floy được dùng để:

A. Tìm đường đi ngắn nhất giữa mọi cặp đỉnh 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 cặp đỉ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

Câu 3: Ma trận kề của đồ thị có hướng không phải là:

A. Ma trận đối xứng.

B. Ma trận đướng chéo trên.

C. Ma trận không đối xứng.

D. Ma trận đường chéo dưới.

Câu 4: 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 5: 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

Câu 6: 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