Cho đồ thị G vô hướng, đỉnh \(v \times G\) có bậc bằng 1 khi:

Thuật toán Kruskal để tìm cây khung nhỏ nhất thực hiện như sau: 1. Sắp xếp các cạnh theo trọng số tăng dần. 2. Chọn cạnh có trọng số nhỏ nhất mà không tạo thành chu trình trong cây khung. 3. Lặp lại bước 2 cho đến khi có đủ n-1 cạnh (với n là số đỉnh). Trong trường hợp này, n = 7, vậy ta cần 6 cạnh. Áp dụng vào đồ thị đã cho: - (1,2): trọng số 1 (chọn) - (1,4): trọng số 2 (chọn) - (2,3): trọng số 3 (chọn) - (4,5): trọng số 3 (chọn) - (2,6): trọng số 4 (chọn) - (6,7): trọng số 4 (chọn) Vậy tập cạnh của cây khung nhỏ nhất là T = { (1,2), (1, 4), (2, 3), (4,5) ,(2, 6), (6, 7) }

Để xác định giá trị của biểu thức logic \(A = (p \to q) \wedge (\neg r \vee \neg q)\), chúng ta cần xem xét tất cả các trường hợp có thể xảy ra của các biến mệnh đề p, q và r. Tuy nhiên, câu hỏi không cung cấp giá trị cụ thể cho p, q, và r. Do đó, giá trị của A phụ thuộc vào giá trị của các biến này. Ví dụ: * Nếu p = True, q = True, r = True: * \(p \to q\) = True * \(\neg r\) = False * \(\neg q\) = False * \(\neg r \vee \neg q\) = False * A = True \(\wedge\) False = False (0) * Nếu p = True, q = False, r = False: * \(p \to q\) = False * \(\neg r\) = True * \(\neg q\) = True * \(\neg r \vee \neg q\) = True * A = False \(\wedge\) True = False (0) * Nếu p = False, q = True, r = False: * \(p \to q\) = True * \(\neg r\) = True * \(\neg q\) = False * \(\neg r \vee \neg q\) = True * A = True \(\wedge\) True = True (1) Vì giá trị của A có thể là True (1) hoặc False (0) tùy thuộc vào giá trị của p, q và r, chúng ta không thể xác định giá trị cụ thể của A mà không có thêm thông tin.

Cây khung của một đồ thị liên thông G là một cây bao gồm tất cả các đỉnh của G và một số cạnh của G sao cho không có chu trình. Nếu cây khung có n đỉnh, thì nó sẽ có n-1 cạnh. Trong trường hợp này, đồ thị G có 5 đỉnh, do đó cây khung của G cũng sẽ có 5 đỉnh và 5-1 = 4 cạnh.