Chu trình Euler đi qua mỗi đỉnh của đồ thị:

Mệnh đề P→Q tương đương logic với mệnh đề \(\overline P \vee Q\). Điều này có nghĩa là "nếu P thì Q" tương đương với "hoặc không P, hoặc Q". Mệnh đề \(\overline Q \to \overline P \) (mệnh đề phản đảo) cũng tương đương với P→Q.

Trong các lựa chọn:

• Lựa chọn 1: \(\overline P \to \overline Q \) không tương đương.

• Lựa chọn 2: \(\overline Q \to \overline P \) tương đương với P→Q.

• Lựa chọn 3: \(P \vee Q \) không tương đương.

• Lựa chọn 4: \(P \vee \overline Q \) không tương đương.

Vậy đáp án đúng là lựa chọn 2.

Để tìm đường đi ngắn nhất từ đỉnh A đến đỉnh E, ta sử dụng thuật toán Dijkstra. Dưới đây là các bước thực hiện thuật toán Dijkstra trên đồ thị đã cho:

Khởi tạo:

• Khoảng cách từ A đến A là 0, khoảng cách đến các đỉnh còn lại là vô cùng.


• Tập các đỉnh chưa xét: {A, B, C, D, E}.

Lặp:

1. Chọn đỉnh có khoảng cách nhỏ nhất từ A trong tập các đỉnh chưa xét. Ban đầu, đỉnh A được chọn.


2. Cập nhật khoảng cách từ A đến các đỉnh lân cận của A (B và C):


3. A -> B: Khoảng cách là 2.


4. A -> C: Khoảng cách là 4.


5. Loại A khỏi tập các đỉnh chưa xét.


6. Chọn đỉnh có khoảng cách nhỏ nhất từ A trong tập các đỉnh chưa xét (B và C). Đỉnh B được chọn (khoảng cách là 2).


7. Cập nhật khoảng cách từ A đến các đỉnh lân cận của B (C và D):


8. B -> C: Khoảng cách từ A đến C là min(4, 2 + 1) = 3.


9. B -> D: Khoảng cách từ A đến D là 2 + 7 = 9.


10. Loại B khỏi tập các đỉnh chưa xét.


11. Chọn đỉnh có khoảng cách nhỏ nhất từ A trong tập các đỉnh chưa xét (C, D, E). Đỉnh C được chọn (khoảng cách là 3).


12. Cập nhật khoảng cách từ A đến các đỉnh lân cận của C (D và E):


13. C -> D: Khoảng cách từ A đến D là min(9, 3 + 2) = 5.


14. C -> E: Khoảng cách từ A đến E là 3 + 2 = 5.


15. Loại C khỏi tập các đỉnh chưa xét.


16. Chọn đỉnh có khoảng cách nhỏ nhất từ A trong tập các đỉnh chưa xét (D, E). Cả D và E đều có khoảng cách là 5. Chọn E.


17. Loại E khỏi tập các đỉnh chưa xét.

Vậy, đường đi ngắn nhất từ A đến E là 5.