Trong thuật toán Ford – Fullkerson giải bài toán luồng cực đại, bước tăng luồng thực hiện trên.

Thuật toán BFS (Breadth-First Search) duyệt đồ thị theo chiều rộng. Bắt đầu từ đỉnh H, ta duyệt các đỉnh kề với H, sau đó duyệt các đỉnh kề với các đỉnh vừa duyệt, cứ tiếp tục như vậy cho đến khi duyệt hết các đỉnh của đồ thị.

Các bước thực hiện thuật toán BFS(H) như sau:

1. Bắt đầu từ H.

2. Các đỉnh kề với H là G, F, E.

3. Các đỉnh kề với G là B.

4. Các đỉnh kề với F là D, K.

5. Các đỉnh kề với E là A.

6. Các đỉnh kề với K là I.

7. Các đỉnh kề với B là C.

Vậy thứ tự duyệt các đỉnh là: H, G, F, E, B, D, K, A, C, I.

Vậy đáp án đúng là: H, G, F, E, B, D, K, A, C, I.

Thuật toán DFS (Depth-First Search - Tìm kiếm theo chiều sâu) bắt đầu từ đỉnh 1, sau đó duyệt theo chiều sâu đến các đỉnh kề chưa được thăm. Thứ tự duyệt như sau:

• Bắt đầu từ đỉnh 1.


• Đỉnh 1 có các đỉnh kề 2 và 7. Ta chọn duyệt đỉnh 2 trước (vì nó nhỏ hơn).


• Từ đỉnh 2, các đỉnh kề chưa thăm là 3.


• Từ đỉnh 3, các đỉnh kề chưa thăm là 6.


• Từ đỉnh 6, các đỉnh kề chưa thăm là 9.


• Từ đỉnh 9, các đỉnh kề chưa thăm là 8.


• Quay lại đỉnh 1, đỉnh kề chưa thăm là 7.


• Từ đỉnh 7, các đỉnh kề chưa thăm là 4.


• Từ đỉnh 4, các đỉnh kề chưa thăm là 5.


• Từ đỉnh 5, đỉnh kề chưa thăm là 10.

Vậy thứ tự duyệt các đỉnh là: 1, 2, 3, 6, 9, 8, 7, 4, 5, 10.

Quy tắc tam đoạn luận là một quy tắc suy luận cơ bản trong logic mệnh đề. Nó có dạng: Nếu P kéo theo Q và Q kéo theo R, thì P kéo theo R. Điều này có nghĩa là, nếu hai mệnh đề điều kiện (P → Q) và (Q → R) đều đúng, thì mệnh đề điều kiện (P → R) cũng đúng.

Xét các phương án:

• Phương án 1: \((P \wedge (P \to Q)) \to Q\): Đây là quy tắc Modus Ponens, không phải tam đoạn luận.


• Phương án 2: \(((P→Q)\vee(Q→R)) →(P→R)
  \): Đây không phải là quy tắc tam đoạn luận vì nó sử dụng phép tuyển (∨) thay vì phép hội (∧).


• Phương án 3: \(((P→Q)\vee(Q→R)) →(Q→R)\): Đây cũng không phải là quy tắc tam đoạn luận vì nó sử dụng phép tuyển (∨) thay vì phép hội (∧) và kết luận không đúng với tam đoạn luận.


• Phương án 4: \(((P→Q) \wedge (Q→R)) →(P→R)\): Đây chính là quy tắc tam đoạn luận. Nếu P kéo theo Q và Q kéo theo R, thì P kéo theo R.

Vậy, đáp án đúng là phương án 4.