Cho đồ thị vô hướng G = (V, E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E = {(1,4),(1,6),(2,5),(2,6),(3,4),(3,5),(3,6)}. Hỏi G có phải là đồ thị hai phía hay không?

Sắp xếp topo là một thứ tự tuyến tính của các đỉnh trong đồ thị có hướng không chu trình (DAG) sao cho với mọi cung (u, v) trong đồ thị, đỉnh u đứng trước đỉnh v trong thứ tự đó. Một đồ thị có chu trình thì không có thứ tự topo.

Để tìm thứ tự topo của đồ thị đã cho, ta có thể sử dụng thuật toán duyệt đồ thị theo chiều sâu (DFS) kết hợp với việc đánh dấu các đỉnh đã được thăm và các đỉnh đã hoàn thành.

Trong đồ thị G = (V, E) với V = {1, 2, 3, 4, 5, 6} và E = {(1, 6), (2, 1), (2, 5), (2, 6), (3, 1), (3, 2), (5, 4), (5, 6), (6, 4)}:

- Đỉnh 3 không có cung vào, có thể là đỉnh bắt đầu.

- Từ 3 có các cung đến 1 và 2.

- Từ 2 có các cung đến 1, 5, 6.

- Từ 1 có cung đến 6.

- Từ 5 có các cung đến 4 và 6.

- Từ 6 có cung đến 4.

Duyệt theo DFS:

- Bắt đầu từ đỉnh 3.

- Thăm 3, sau đó thăm 1 (vì 3 -> 1).

- Thăm 1, sau đó thăm 6 (vì 1 -> 6).

- Thăm 6, sau đó thăm 4 (vì 6 -> 4).

- Thăm 4 (đã hoàn thành).

- Quay lại 6 (đã hoàn thành).

- Quay lại 1 (đã hoàn thành).

- Quay lại 3, thăm 2 (vì 3 -> 2).

- Thăm 2, sau đó thăm 5 (vì 2 -> 5).

- Thăm 5, sau đó thăm 4 (đã thăm rồi) và 6 (đã thăm rồi).

- 5 hoàn thành.

- 2 hoàn thành.

- 3 hoàn thành.

Như vậy, một thứ tự topo hợp lệ là: 3, 2, 1, 5, 6, 4.

Tập A - B (hiệu của A và B) là tập hợp chứa các phần tử thuộc A nhưng không thuộc B. Trong trường hợp này, A = {1, 2, 3, 4, 5, 6, 7, 8, 9} và B = {1, 2, 3, 9, 10}.

Ta thấy các phần tử 1, 2, 3, 9 thuộc cả A và B, nên khi lấy A - B, ta loại bỏ chúng khỏi A. Các phần tử còn lại của A là 4, 5, 6, 7, 8.

Vậy, A - B = {4, 5, 6, 7, 8}.