540 câu trắc nghiệm tổng hợp Toán rời rạc có đáp án - Phần 13

Tìm đường đi ngắn nhất giữa các cặp đỉnh bất kì của đồ thị.

Tìm đường đi ngắn nhất từ một đỉnh đến các đỉnh còn lại của đồ thị

Tìm đường đi ngắn nhất giữa hai đỉnh của đồ thị.

Tìm đường đi ngắn nhất giữa một đỉnh nguồn và một đỉnh đích.

O(n3 log2n)

O(n3)

O(n2)

O(n2 log2n)

Tìm đường đi ngắn nhất giữa mọi cặp đỉnh của đồ thị.

Tìm đường đi ngắn nhất từ một đỉnh đến các đỉnh còn lại của đồ thị.

Tìm đường đi ngắn nhất giữa hai cặp đỉnh của đồ thị.

Tìm đường đi ngắn nhất giữa một đỉnh nguồn và một đỉnh đích

9900

9999

10000

1001

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

Thuật toán Floyd.

Thuật toán Prim.

Thuật toán Dijsktra.

Thuật toán Dijsktra.

Tìm kiếm theo chiều rộng (BFS).

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

Thuật toán Prim.

Kết nạp được n-1 cạnh vào cây khung.

Kết nạp được n cạnh vào cây khung.

Kết nạp được n – 2 cạnh vào cây khung.

Kết nạp được n - 3 cạnh vào cây khung.

Dừng khi kết nạp được tất cả các cạnh vào cây khung.

Dừng khi kết nạp được n đỉnh và n cạnh vào cây khung

Thuật toán 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 khung và không tạo ra chu trình.

Thuật toán xây dựng cây khung ngắn nhất.

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.

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.

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.

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ác cạnh nằm ngoài đường đi đánh dấu.

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

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

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

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

Nâng giá trị luồng.

Giảm giá trị luồng.

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

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

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

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

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

r ≠ m– n + 2

r = m– n + 2

r ≥ m– n + 2

r ≤ m– n + 2

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ằng khả năng thông qua của lát cắt lớn nhất tách điểm s và t.

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.

Tất cả các đáp án đều sai

giữa hai đỉnh bất kỳ , có nhiều nhất một cạnh, có kể đến thứ tự các đỉnh.

Giữa hai đỉnh bất kỳ , có nhiều nhất một cạnh.

Giữa hai đỉnh bất kỳ , có thể có nhiều hơn một cạnh, có kể đến thứ tự các đỉnh.

Giữa hai đỉnh bất kỳ , có thể có nhiều hơn một cạnh, không kể đến thứ tự các đỉnh.

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

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

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

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

Tồn tại một cạnh của G là cạnh vô hướng

Mọi cạnh của G là cạnh vô hướng

Có hai cạnh của G là cạnh vô hướng

Mọi cạnh của G là cạnh có hướng

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

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 phần tử trên đướng chéo chính bằng 1

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

G không có khuyên

G chứa cạnh bội

G không có cạnh bội.

G có thể có cạnh có hướng

Nếu bậc của đỉnh v là 0.

Nếu bậc của đỉnh v là một số lẻ.

Nếu bậc của đỉnh v là một số chẵn.

Nếu bậc của đỉnh v là 1.

Giữa hai đỉnh bất kỳ luôn tồn tại đường đi từ u đến v.

Nếu , thì tồn tại v khác u sao cho v liên thông với u.

Nếu , thì với mọi v khác u đều kề với u.

Nếu , thì tồn tại đỉnh v khác u kề với u.

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

Giữa hai đỉnh bất kỳ luôn tìm được đường đi từ u đến v

Giữa hai đỉnh bất kỳ luôn tìm được đường đi từ v đến u

Giữa hai đỉnh bất kỳ không tồn tại đường đi từ u đến v

và u, v có thứ tự

và u, v có thứ tự

và u, v không có thứ tự

Là ma trận đơn vị.

Là ma trận đối xứng.

Là ma trận không đối xứng.

Là ma trận đường chéo trên.

Ma trận đối xứng.

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

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

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

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

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

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

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

Ma trận tam giác trên.

Ma trận tam giác dưới

Ma trận có các phần tử trên đường chéo chính bằng 0, các phần tử khác bằng 1.

Ma trận có các phần tử trên đường chéo chính bằng 1, các phần tử khác bằng 0.

Có cạnh giữa đinh i và đỉnh j

Có cạnh giữa đinh j và đỉnh i

Không có cạnh giữa đinh i và đỉnh j