Đúng Sai

Đúng/Sai

• Thuật toán tìm kiếm theo chiều sâu (DFS) và tìm kiếm theo chiều rộng (BFS) đều có thể được sử dụng để kiểm tra tính chất của đồ thị.

• Trong thực tế, thut toán tìm kiếm theo chiều rộng dễ cài đặt hơn so với tìm kiếm theo chiều sâu.

• Nếu một thành phần liên thông có c đỉnh và chứa c−1 cạnh thì chắc chắn đồ thị đó có chu trình.

• Một thành phần liên thông có nhiều hơn c cạnh sẽ chứa ít nhất một chu trình.

Đúng/

• Thuật toán BFS duyệt các đỉnh theo thứ tự giảm dần của khoảng cách từ đỉnh xuất phát.

• BFS có thể tính toán khoảng cách từ đỉnh xuất phát đến tất cả các đỉnh khác trong đồ thị.

• Thuật toán DFS dễ cài đặt hơn thuật toán BFS.

• DFS duyệt qua tất cả các đỉnh của đồ thị theo đường đi ngẫu nhiên.

Đúng/Sai

• Cầu (Bridge) là một cạnh mà khi loại bỏ nó thì số thành phần liên thông trong đồ thị giảm đi.

• Nếu loại bỏ một khớp (Joint) trong đồ thị vô hướng thì số thành phần liên thông của đồ thị sẽ tăng lên.

• Trong đồ thị vô hướng, một cạnh cầu luôn thuộc về đúng một chu trình.

• Cạnh cầu và đỉnh khớp chỉ tồn tại trong đồ thị vô hướng liên thông.

Đúng/Sai

• Một cạnh (u,v) trong đồ thị vô hướng liên thông là cầu nếu low[v] = id[v] và u là cha trực tiếp của v.

• Đỉnh u là khớp trong cây DFS khi u là gốc và có ít nhất hai nhánh con trong cây DFS đã định hướng.

• Nếu đỉnh u không phải gốc trong cây DFS, thì điều kiện để u là khớp là low[v] >= id[u] với v là cha của u.

• Để xác định khớp và cầu trong đồ thị vô hướng liên thông, ta chỉ cần xây dựng cây DFS và sử dụng mảng id[] mà không cần mảng low[].

Đúng/Sai

• Thuật toán Dijkstra không áp dụng được cho đồ thị có trọng số âm.

• Thuật toán Bellman-Ford không thể nhận biết chu trình âm trong đồ thị có hướng.

• Thuật toán Floyd-Warshall chỉ tìm đường đi ngắn nhất giữa một đỉnh nguồn và một đỉnh đích cụ thể.

• Độ phức tạp của thuật toán Bellman-Ford là O(VE), trong đó V là số đỉnh và E là số cạnh.

Đúng/Sai

• Thuật toán Floyd-Warshall có thể được sử dụng trên đồ thị với cạnh có trọng số âm và nhận biết chu trình âm.

• Độ phức tạp của thuật toán Dijkstra khi sử dụng hàng đợi ưu tiên là O(VlogV).

• Cả ba thuật toán Dijkstra, Bellman-Ford và Floyd-Warshall đều có chung thao tác cập nhật đường đi ngắn nhất.

• Thuật toán Floyd-Warshall có độ phức tạp là O(V²), phù hợp để tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh.

Đúng/Sai

• Trong một chu trình bất kỳ, cạnh có trọng số lớn nhất tuyệt đối sẽ không nằm trên bất kỳ cây khung nhỏ nhất nào.

• Đường đi từ đỉnh u đến v trên cây khung nhỏ nhất có thể chứa các cạnh có trọng số lớn hơn cạnh lớn nhất trên đường đi từ u đến v trong đồ thị ban đầu.

• Nếu tất cả các cạnh trong đồ thị đều có trọng số khác nhau thì cây khung nhỏ nhất của đồ thị là duy nhất.

• Nếu một vài cạnh trong đồ thị có trọng số bằng nhau thì có thể tồn tại nhiều hơn một cây khung nhỏ nhất.

Đúng/Sai

• Cạnh có trọng số nhỏ nhất trong đồ thị sẽ nằm trong mọi cây khung nhỏ nhất nếu nó là duy nhất (không có cạnh nào có trọng số bằng nó).

• Thuật toán Kruskal duyệt các cạnh theo thứ tự trọng số từ lớn đến nhỏ.

• Trong thuật toán Kruskal, mỗi đỉnh ban đầu được coi là một cây riêng biệt.

• Thuật toán Kruskal dừng lại khi tất cả các đỉnh được hợp nhất thành một cây duy nhất.