Cho đồ thị vô hướng G = (V, E) trong đó tập đỉnh V = {1,2,3,4,5,6,7,8} và tập cạnh E = {(1,2), (1,3), (1,6), (2,3), (2,5)}. Hỏi số cạnh (nối giữa các đỉnh trong V) ít nhất cần bổ sung thêm vào G là bao nhiêu để G trở thành đồ thị Euler?

Để giải bài toán này, ta có thể sử dụng phương pháp đệ quy hoặc quy hoạch động. Gọi $a_n$ là số xâu nhị phân độ dài $n$ không chứa hai bit 1 đứng cạnh nhau.

- Với $n = 1$, ta có 2 xâu là "0" và "1", vậy $a_1 = 2$.
- Với $n = 2$, ta có 3 xâu là "00", "01" và "10", vậy $a_2 = 3$.

Ta có thể xây dựng xâu độ dài $n$ từ xâu độ dài $n-1$ và $n-2$ như sau:

- Nếu xâu độ dài $n-1$ kết thúc bằng 0, ta có thể thêm 0 hoặc 1 vào cuối.
- Nếu xâu độ dài $n-1$ kết thúc bằng 1, ta chỉ có thể thêm 0 vào cuối.

Vậy, số xâu độ dài $n$ sẽ bằng số xâu độ dài $n-1$ kết thúc bằng 0 cộng với số xâu độ dài $n-1$ kết thúc bằng 1 cộng với số xâu độ dài $n-2$ kết thúc bằng 0 khi ta thêm '10' vào. Điều này dẫn đến công thức truy hồi: $a_n = a_{n-1} + a_{n-2}$.

Áp dụng công thức này:
- $a_3 = a_2 + a_1 = 3 + 2 = 5$
- $a_4 = a_3 + a_2 = 5 + 3 = 8$
- $a_5 = a_4 + a_3 = 8 + 5 = 13$

Vậy, có 13 xâu nhị phân độ dài 5 không chứa 2 bít 1 đứng cạnh nhau.

Duyệt đồ thị theo chiều rộng (BFS) bắt đầu từ đỉnh 1:

1. Bắt đầu từ đỉnh 1: Thăm đỉnh 1.
2. Các đỉnh kề của đỉnh 1: Các đỉnh kề của đỉnh 1 là 2, 3, và 6. Vì duyệt theo thứ tự từ điển, ta thăm các đỉnh này theo thứ tự 2, 3, rồi 6.
3. Các đỉnh kề của đỉnh 2: Các đỉnh kề của đỉnh 2 là 1, 3, 5, và 6. Đỉnh 1, 3, 6 đã được thăm, nên ta thăm đỉnh 5.
4. Các đỉnh kề của đỉnh 3: Các đỉnh kề của đỉnh 3 là 1 và 2. Cả hai đỉnh này đều đã được thăm.
5. Các đỉnh kề của đỉnh 6: Các đỉnh kề của đỉnh 6 là 1, 2, 4, và 5. Đỉnh 1, 2, 5 đã được thăm, nên ta thăm đỉnh 4.
6. Các đỉnh kề của đỉnh 5: Các đỉnh kề của đỉnh 5 là 2, 4, 6. Đỉnh 2, 6 đã được thăm, đỉnh 4 đã được thăm.

Vậy, đường đi từ đỉnh 1 đến đỉnh 4 được tìm thấy là 1 – 2 – 6 – 4.

* Phương án A: 1 – 6 – 4: Có thể là một đường đi, nhưng không phải là đường đi được tìm thấy đầu tiên theo BFS (vì đỉnh 2 được xét trước đỉnh 6).
* Phương án B: 1 – 2 – 5 – 4: Có thể là một đường đi, nhưng không phải là đường đi được tìm thấy đầu tiên theo BFS (vì đỉnh 6 được xét trước đỉnh 5 khi duyệt các đỉnh kề của đỉnh 2 để đến đỉnh 4 nhanh hơn).
* Phương án C: 1 – 2 – 6 – 4: Đây là đường đi được tìm thấy đầu tiên theo BFS.
* Phương án D: 1 – 3 – 2 – 5 – 4: Đây không phải là đường đi ngắn nhất và không phải là đường đi BFS tìm thấy đầu tiên.

Ta có dãy số: 1, 3, 2, 7, 6, 8, 4, 2, 6, 7.
Đếm số lượng dãy con có tổng chẵn:
- Dãy 1 phần tử: 2, 6, 8, 4, 2, 6 (6 dãy)
- Dãy 2 phần tử:
+ (1, 3) = 4 (chẵn)
+ (3, 2) = 5 (lẻ)
+ (2, 7) = 9 (lẻ)
+ (7, 6) = 13 (lẻ)
+ (6, 8) = 14 (chẵn)
+ (8, 4) = 12 (chẵn)
+ (4, 2) = 6 (chẵn)
+ (2, 6) = 8 (chẵn)
+ (6, 7) = 13 (lẻ)
=> 5 dãy
- Dãy 3 phần tử:
+ (1, 3, 2) = 6 (chẵn)
+ (3, 2, 7) = 12 (chẵn)
+ (2, 7, 6) = 15 (lẻ)
+ (7, 6, 8) = 21 (lẻ)
+ (6, 8, 4) = 18 (chẵn)
+ (8, 4, 2) = 14 (chẵn)
+ (4, 2, 6) = 12 (chẵn)
+ (2, 6, 7) = 15 (lẻ)
=> 5 dãy
- Dãy 4 phần tử:
+ (1, 3, 2, 7) = 13 (lẻ)
+ (3, 2, 7, 6) = 18 (chẵn)
+ (2, 7, 6, 8) = 23 (lẻ)
+ (7, 6, 8, 4) = 25 (lẻ)
+ (6, 8, 4, 2) = 20 (chẵn)
+ (8, 4, 2, 6) = 20 (chẵn)
+ (4, 2, 6, 7) = 19 (lẻ)
=> 3 dãy
- Dãy 5 phần tử:
+ (1, 3, 2, 7, 6) = 19 (lẻ)
+ (3, 2, 7, 6, 8) = 26 (chẵn)
+ (2, 7, 6, 8, 4) = 27 (lẻ)
+ (7, 6, 8, 4, 2) = 27 (lẻ)
+ (6, 8, 4, 2, 6) = 26 (chẵn)
+ (8, 4, 2, 6, 7) = 27 (lẻ)
=> 2 dãy
- Dãy 6 phần tử:
+ (1, 3, 2, 7, 6, 8) = 27 (lẻ)
+ (3, 2, 7, 6, 8, 4) = 30 (chẵn)
+ (2, 7, 6, 8, 4, 2) = 29 (lẻ)
+ (7, 6, 8, 4, 2, 6) = 33 (lẻ)
+ (6, 8, 4, 2, 6, 7) = 33 (lẻ)
=> 1 dãy
- Dãy 7 phần tử:
+ (1, 3, 2, 7, 6, 8, 4) = 31 (lẻ)
+ (3, 2, 7, 6, 8, 4, 2) = 32 (chẵn)
+ (2, 7, 6, 8, 4, 2, 6) = 35 (lẻ)
+ (7, 6, 8, 4, 2, 6, 7) = 40 (chẵn)
=> 2 dãy
- Dãy 8 phần tử:
+ (1, 3, 2, 7, 6, 8, 4, 2) = 33 (lẻ)
+ (3, 2, 7, 6, 8, 4, 2, 6) = 38 (chẵn)
+ (2, 7, 6, 8, 4, 2, 6, 7) = 42 (chẵn)
=> 2 dãy
- Dãy 9 phần tử:
+ (1, 3, 2, 7, 6, 8, 4, 2, 6) = 39 (lẻ)
+ (3, 2, 7, 6, 8, 4, 2, 6, 7) = 45 (lẻ)
=> 0 dãy
- Dãy 10 phần tử:
+ (1, 3, 2, 7, 6, 8, 4, 2, 6, 7) = 46 (chẵn)
=> 1 dãy
Tổng: 6 + 5 + 5 + 3 + 2 + 1 + 2 + 2 + 0 + 1 = 27
Vậy có 27 dãy con có tổng chẵn.

Vì A là tập con của B (A⊆B), nên tất cả các phần tử của A đều nằm trong B. Do đó, khi hợp hai tập A và B (A∪B), kết quả sẽ là tập B. Vậy |A∪B| = |B| = 20.