Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán DFS(A) là:

 

Thuật toán Kruskal được sử dụng để tìm cây khung nhỏ nhất của một đồ thị có trọng số. Thuật toán này hoạt động bằng cách thêm các cạnh vào cây khung theo thứ tự trọng số tăng dần, miễn là việc thêm cạnh đó không tạo ra chu trình.

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)}.

Thuật toán Prim để tìm cây khung nhỏ nhất bắt đầu từ một đỉnh, 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 một đỉnh chưa thuộc cây. Ta thực hiện thuật toán Prim như sau:

1. Bắt đầu từ đỉnh 1:
* Các cạnh kề với đỉnh 1 là (1,2) = 5 và (1,8) = 4. Chọn cạnh (1,8) vì nó có trọng số nhỏ hơn. Vậy T = {(1,8)}.

2. Mở rộng cây từ đỉnh 8:
* Các cạnh kề với đỉnh 8 là (8,2) = 2, (8,5) = 4, (8,3) = 8, và (1,8) đã có.
* Chọn cạnh (8,2) vì nó có trọng số nhỏ nhất. Vậy T = {(1,8), (8,2)}.

3. Mở rộng cây từ đỉnh 2:
* Các cạnh kề với đỉnh 2 là (2,4) = 7, (1,2) = 5, (8,2) = 2 (đã có).
* Chọn cạnh (2,4) vì nó có trọng số nhỏ hơn các cạnh khác kề với các đỉnh đã có trong cây và đỉnh chưa có trong cây. Vậy T = {(1,8), (8,2), (2,4)}.

4. Mở rộng cây từ đỉnh 4:
* Các cạnh kề với đỉnh 4 là (4,7) = 9, (2,4) = 7 (đã có).
* Chọn cạnh (4,7) vì nó có trọng số nhỏ nhất và kết nối với đỉnh chưa có trong cây. Vậy T = {(1,8), (8,2), (2,4), (4,7)}.

5. Mở rộng cây từ đỉnh 7:
* Các cạnh kề với đỉnh 7 là (7,6) = 1, (4,7) = 9 (đã có), (7,5) = 3.
* Chọn cạnh (7,6) vì nó có trọng số nhỏ nhất. Vậy T = {(1,8), (8,2), (2,4), (4,7), (7,6)}.

6. Mở rộng cây từ đỉnh 6:
* Các cạnh kề với đỉnh 6 là (6,3) = 5, (7,6) = 1 (đã có), (6,5) = 6.
* Chọn cạnh (6,3) vì nó có trọng số nhỏ nhất và kết nối với đỉnh chưa có trong cây. Vậy T = {(1,8), (8,2), (2,4), (4,7), (7,6), (6,3)}.

7. Mở rộng cây từ đỉnh 3:
* Các cạnh kề với đỉnh 3 là (3,8) = 8, (3,6) = 5 (đã có).
* Chọn cạnh (8,5) vì nó có trọng số nhỏ nhất và kết nối với đỉnh chưa có trong cây. Vậy T = {(1,8), (8,2), (2,4), (4,7), (7,6), (6,3), (8,5)}.

Vậy, cây khung nhỏ nhất H = (V, T) có tập cạnh T = {(1,8), (8,2), (2,4), (4,7), (7,6), (6,3), (8,5)}.

So sánh với các đáp án, ta thấy đáp án B phù hợp.

Luật tam đoạn luận rời (Disjunctive Syllogism) có dạng: P ∨ Q, ¬P ⊢ Q. Trong trường hợp này, P là "An học giỏi", Q là "An công tác tốt". Tiền đề là "An được khen thưởng nếu học giỏi hoặc công tác tốt" (P ∨ Q), và "An không học giỏi" (¬P). Kết luận là "An phải công tác tốt" (Q). Như vậy, suy luận này tuân theo đúng luật tam đoạn luận rời.

Hình ảnh trong câu hỏi mô tả một mô hình suy diễn, trong đó có một mệnh đề điều kiện (P → Q) và một mệnh đề P. Từ đó, suy ra mệnh đề Q. Đây chính là hình thức của Luật khẳng định (Modus Ponens). Do đó, đáp án đúng là A. Luật khẳng định.