Thi thử trắc nghiệm ôn tập Toán rời rạc - Đề #13
Vui lòng cài đặt đề thi trước khi làm bài
Thuật toán Dijkstra được dùng để:
Với đồ thị n đỉnh, độ phức tạp tính toán của thuật toán Dijkstra là:
Thuật toán Floy được dùng để:
Số cạnh của cây với 1000 đỉnh là:
Để xây dựng cây khung nhỏ nhất của đồ thị, ta dùng:
Để xây dựng cây khung nhỏ nhất của đồ thị, ta dùng: (Chọn phương án đúng)
Thuật toán Kruskal áp dụng cho đồ thì G, n đỉnh sẽ dừng khi:
Sự giống nhau giữa thuật toán Prim và thuật toán Kruskal là:
Sự khác nhau giữa thuật toán Prim và thuật toán Kruskal:
Hãy cho biết đồ thị nào dưới đây là một cây?
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.
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:
Giá trị của luồng cực đại trong mạng:
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 đó:
Nếu một đơn đồ thị phẳng liên thông có n đỉnh, m cạnh $(n≥ 3)$ thì:
Theo định lý Ford – Fulkerson giá trị luồng cực đại từ điểm phát s đến điểm thu t.
Đồ thị G = (V,E) được gọi là đơn đồ thị nếu.
Nếu G = (V,E) là một đơn đồ thị vô hướng thì:
Đồ thị G = (V,E) được gọi là đồ thị vô hướng nếu:
Nếu G = (V,E) là một đơn đồ thị vô hướng thì: (Chọn phương án đúng)
Nếu G = (V,E) là một đa đồ thị vô hướng thì:
Ta gọi đỉnh v là đỉnh treo trong đồ thị vô hướng G = (V,E) A).
Đồ thị vô hướng G = (V,E) được gọi là liên thông nếu.
Đồ thị có hướng G =(V,E) được gọi là liên thông mạnh nếu:
Ta nói cặp hai đỉnh (u,v) là cạnh vô hướng của đồ thị G = (V,E) nếu:
Ma trận kề của đồ thị vô hướng G = (V,E) có tính chất:
Ma trận kề của đồ thị có hướng không phải là:
Trong biểu diễn đồ thị bởi danh sách kề, mỗi đỉnh của đồ thị có một danh sách:
Ma trận kề của một đơn đồ thị vô hướng đầy đủ là:
Cho ma trận kề A[n,n] biểu diễn đồ thị G vô hướng, n đỉnh, giá trị A[i,j] của ma trận kề xác định:
