Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán DFS(C) là:

Một quan hệ hai ngôi từ A tới B là một tập hợp các cặp có thứ tự (x, y), trong đó x thuộc A và y thuộc B. Ta sẽ kiểm tra từng đáp án:

- Đáp án 1: {(1, a), (3, 3), (2, a)}. Ta thấy 1, 2, 3 thuộc A, nhưng 3 không thuộc B. Vậy đây không phải là quan hệ hai ngôi từ A tới B.

- Đáp án 2: {(2, 2), (2, c), (3, b)}. Ta thấy 2, 3 thuộc A và 2, c, b thuộc B. Vậy đây là quan hệ hai ngôi từ A tới B.

- Đáp án 3: {(1, a), (2, 2), (3, 1)}. Ta thấy 1, 2, 3 thuộc A, nhưng 1 không thuộc B. Vậy đây không phải là quan hệ hai ngôi từ A tới B.

- Đáp án 4: {(2, c), (2, 2), (b, 3)}. Ta thấy 2 thuộc A, nhưng b không thuộc A. Vậy đây không phải là quan hệ hai ngôi từ A tới B.

Vậy đáp án đúng là đáp án 2.

Để giải bài toán này, ta cần tìm số lượng phần tử ít nhất cần lấy ra từ tập A để chắc chắn có một cặp số có tổng bằng 20. Các cặp số trong tập A có tổng bằng 20 là: (1, 19), (3, 17), (5, 15), (7, 13), (9, 11).

Ta xét trường hợp xấu nhất, khi ta chọn các số từ tập A sao cho không có cặp nào có tổng bằng 20. Ta có thể chọn các số: 1, 3, 5, 7, 9. Tiếp theo, ta có thể chọn thêm số 10 (nếu có), nhưng trong tập A không có số 10. Vì vậy, ta có thể chọn các số lớn hơn 10 mà không tạo thành cặp có tổng bằng 20, ví dụ các số: 11, 13, 15, 17, 19.

Tuy nhiên, nếu ta chọn các số không tạo thành cặp tổng 20 là {11, 13, 15, 17, 19}, khi ta lấy thêm một số bất kỳ từ các số còn lại của tập A (tức là 1, 3, 5, 7, 9), thì số đó sẽ tạo thành một cặp có tổng bằng 20 với một số đã chọn. Ví dụ, nếu ta chọn thêm số 1, ta có cặp (1, 19). Nếu ta chọn thêm số 3, ta có cặp (3, 17). Nếu ta chọn thêm số 5, ta có cặp (5, 15). Nếu ta chọn thêm số 7, ta có cặp (7, 13). Nếu ta chọn thêm số 9, ta có cặp (9, 11).

Ta có thể chọn tối đa 5 số mà không tạo thành cặp nào có tổng bằng 20 là {11, 13, 15, 17, 19}. Tương tự, ta cũng có thể chọn tối đa 5 số {1, 3, 5, 7, 9} mà không tạo ra cặp nào có tổng bằng 20. Do đó, nếu ta lấy thêm một số nữa, chắc chắn sẽ tạo thành một cặp có tổng bằng 20.

Vậy số phần tử ít nhất cần lấy là: 5 + 1 = 6 phần tử nếu ta chỉ xét 1 nửa các cặp số tạo ra tổng 20, hoặc 5 + 1 = 6 nếu ta chọn các số lớn hơn 10. Xét trường hợp tổng quát ta có thể chọn các số không tạo thành cặp là {9, 11, 13, 15, 17, 19} => ta có thể chọn tối đa 6 số, vậy khi chọn số tiếp theo chắc chắn sẽ tạo thành cặp số có tổng bằng 20.

Vậy ta cần lấy ít nhất 6 phần tử.

Gọi A là tập hợp các xâu nhị phân độ dài 5 có 2 bit đầu tiên là 0, B là tập hợp các xâu nhị phân độ dài 5 có 2 bit cuối là 1.
Ta cần tìm |A ∪ B| = |A| + |B| - |A ∩ B|.
- Tính |A|: Hai bit đầu tiên cố định là 00, 3 bit còn lại có thể là 0 hoặc 1, nên có 2^3 = 8 xâu. Vậy |A| = 8.
- Tính |B|: Hai bit cuối cùng cố định là 11, 3 bit còn lại có thể là 0 hoặc 1, nên có 2^3 = 8 xâu. Vậy |B| = 8.
- Tính |A ∩ B|: Hai bit đầu là 00, hai bit cuối là 11. Bit ở giữa có thể là 0 hoặc 1, nên có 2 xâu. Vậy |A ∩ B| = 2.
Vậy |A ∪ B| = 8 + 8 - 2 = 14.