Cho đồ thị như hình vẽ. Hãy cho biết kết quả thực hiện thuật toán BFS(2):
Đáp án đúng: B
Câu hỏi liên quan
Ta có X = 0, Y = 0, Z = 1. Thay vào biểu thức (¬X→ ¬Y) v (¬Y → ¬Z) và (¬X → ¬Z):
¬X = ¬0 = 1
¬Y = ¬0 = 1
¬Z = ¬1 = 0
(¬X→ ¬Y) = (1 → 1) = 1
(¬Y → ¬Z) = (1 → 0) = 0
(¬X → ¬Z) = (1 → 0) = 0
(¬X→ ¬Y) v (¬Y → ¬Z) = 1 v 0 = 1
Vậy (¬X→ ¬Y) v (¬Y → ¬Z) và (¬X → ¬Z) = 1 và 0
Ta có X = 0, Y = 0, Z = 1.
- Xét biểu thức (¬X→Y) ∧ (¬Y → Z):
¬X = ¬0 = 1
¬Y = ¬0 = 1
(¬X→Y) = (1 → 0) = 0
(¬Y → Z) = (1 → 1) = 1
(¬X→Y) ∧ (¬Y → Z) = 0 ∧ 1 = 0
- Xét biểu thức (¬X →Z):
(¬X →Z) = (1 → 1) = 1
Vậy, chân trị của biểu thức (¬X→Y) ∧ (¬Y → Z) là 0 và chân trị của biểu thức (¬X →Z) là 1.
Đồ thị đơn (simple graph) là đồ thị không có khuyên (loop) và không có cạnh bội (multiple edges). Khuyên là cạnh nối một đỉnh với chính nó. Cạnh bội là hai đỉnh được nối với nhau bởi nhiều hơn một cạnh.
Vậy, một đồ thị G là đơn đồ thị khi và chỉ khi G không có khuyên và bất kỳ hai đỉnh phân biệt nào cũng được nối với nhau bởi không quá một cạnh.
Tổng bậc của các đỉnh là: 2 + 3 + 3 + 4 + 2 + 2 = 16
Vậy, 2E = 16 => E = 8
Do đó, số cạnh của đồ thị là 8.
