Để xây dựng cây khung nhỏ nhất của đồ thị, ta dùng:
Đáp án đúng: B
Câu hỏi liên quan
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.
Áp dụng DFS bắt đầu từ A:
1. A được thăm.
2. Các đỉnh kề của A là B, C, K. Chọn B (theo thứ tự abc) thăm trước.
3. Các đỉnh kề của B là D, I. Chọn D thăm trước.
4. Các đỉnh kề của D là F. Chọn F thăm.
5. Các đỉnh kề của F là H. Chọn H thăm.
6. Từ H đến G.
7. Từ G đến E.
8. Quay lại B, thăm I.
9. Từ I thăm N.
10. Từ N thăm K.
11. Cuối cùng thăm C.
Vậy thứ tự duyệt đúng là: A, B, D, F, H, G, E, I, N, K, C
Bước 1: Sắp xếp các cạnh theo trọng số tăng dần.
Bước 2: Chọn cạnh có trọng số nhỏ nhất. Kiểm tra xem cạnh này có tạo thành chu trình với các cạnh đã chọn trước đó hay không. Nếu không tạo thành chu trình, thêm cạnh này vào cây khung. Ngược lại, bỏ qua cạnh này.
Bước 3: Lặp lại bước 2 cho đến khi có đủ (V-1) cạnh, với V là số đỉnh của đồ thị.
Áp dụng thuật toán Kruskal cho đồ thị đã cho, ta có cây khung nhỏ nhất với tập cạnh là: T = {(1,2), (1, 4), (2, 3), (4,5) ,(2, 6), (6, 7)}.
