Đáp án đúng: B
Câu hỏi liên quan
Phân tích câu hỏi: Câu hỏi kiểm tra kiến thức về thuật toán tìm kiếm theo chiều sâu (DFS) trên đồ thị vô hướng, đặc biệt là khả năng duyệt các đỉnh trong đồ thị.
Đánh giá các phương án:
- A. Đúng. Thuật toán DFS(u) bắt đầu từ đỉnh u và duyệt tất cả các đỉnh có thể đến được từ u. Trong một đồ thị vô hướng, tập hợp các đỉnh có thể đến được từ u chính là thành phần liên thông chứa u.
- B. Sai. DFS(u) chỉ duyệt các đỉnh trong cùng thành phần liên thông với u. Nếu đồ thị có nhiều thành phần liên thông, DFS(u) không thể tìm đường đi đến các đỉnh thuộc thành phần liên thông khác.
- C. Sai. Tương tự như B, DFS(u) chỉ duyệt một thành phần liên thông duy nhất chứa đỉnh u.
- D. Sai. DFS(u) duyệt tất cả các đỉnh trong cùng thành phần liên thông với u mỗi đỉnh đúng một lần. Tuy nhiên, nó không duyệt tất cả các đỉnh của đồ thị nếu đồ thị có nhiều thành phần liên thông.
Kết luận: Phương án A là đúng nhất.
1. Thuật toán Prim: Bắt đầu từ một đỉnh duy nhất, sau đó mở rộng cây bằng cách thêm các cạnh có trọng số nhỏ nhất mà kết nối cây hiện tại với các đỉnh chưa thuộc cây.
2. Thuật toán Kruskal: Sắp xếp tất cả các cạnh theo trọng số tăng dần, sau đó duyệt qua các cạnh đã sắp xếp và thêm cạnh vào cây nếu nó không tạo thành chu trình.
Các phương án khác:
* Tìm kiếm theo chiều sâu (DFS): Là thuật toán duyệt đồ thị theo chiều sâu, không đảm bảo tìm được cây khung nhỏ nhất.
* Thuật toán Floyd: Là thuật toán tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong đồ thị.
* Thuật toán Dijkstra: Là thuật toán tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại trong đồ thị.
Do đó, thuật toán Prim được sử dụng để xây dựng cây khung nhỏ nhất.
Phương án A đúng vì nó đưa ra định nghĩa chính xác về đồ thị liên thông. Một đồ thị được gọi là liên thông nếu có một đường đi giữa mọi cặp đỉnh trong đồ thị.
Phương án B sai vì nó chỉ yêu cầu một đỉnh v khác u liên thông với u, điều này không đảm bảo tính liên thông của toàn bộ đồ thị.
Phương án C sai vì nó yêu cầu mọi đỉnh v khác u đều kề với u, đây là định nghĩa của đồ thị đầy đủ chứ không phải đồ thị liên thông.
Phương án D sai vì nó chỉ yêu cầu tồn tại một đỉnh v khác u kề với u, điều này không đảm bảo tính liên thông của toàn bộ đồ thị.
Trong một đơn đồ thị vô hướng đầy đủ, giữa mọi cặp đỉnh đều có một cạnh nối trực tiếp. Điều này có nghĩa là ma trận kề của nó sẽ có giá trị 1 ở tất cả các vị trí không nằm trên đường chéo chính (vì đường chéo chính biểu thị cạnh nối một đỉnh với chính nó, và trong đơn đồ thị không có khuyên). Vì vậy, đáp án đúng là 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.
Trong ma trận kề A[n, n] của đồ thị vô hướng G với n đỉnh, phần tử A[i, j] biểu diễn thông tin về sự tồn tại của cạnh giữa đỉnh i và đỉnh j. Cụ thể:
- Nếu A[i, j] = 1 (hoặc một giá trị khác 0): Có một cạnh nối giữa đỉnh i và đỉnh j.
- Nếu A[i, j] = 0: Không có cạnh nối giữa đỉnh i và đỉnh j.
Vì đồ thị là vô hướng, cạnh (i, j) và cạnh (j, i) được coi là một, do đó A[i, j] = A[j, i]. Các phương án C và D giống nhau và đều diễn tả việc không có cạnh, nhưng đề bài hỏi giá trị A[i,j] xác định điều gì khi nó khác 0 (thường là 1). Phương án A đúng vì nó mô tả trường hợp có cạnh giữa đỉnh i và đỉnh j. Phương án B tuy cũng đúng về mặt ý nghĩa (do tính vô hướng), nhưng phương án A tường minh hơn.
