Một nhóm có 9 bạn sinh viên gồm 4 nữ và 5 nam. Hỏi có bao nhiêu cách chọn 3 bạn đi dự hội thảo? Biết rằng trong số 3 bạn đi dự có ít nhất một nữ.

Để một đồ thị vô hướng trở thành đồ thị Euler, tất cả các đỉnh của nó phải có bậc chẵn. Ta kiểm tra bậc của các đỉnh trong đồ thị đã cho:

- Đỉnh 1 có bậc 3 (kết nối với 2, 3, 6)
- Đỉnh 2 có bậc 3 (kết nối với 1, 3, 5)
- Đỉnh 3 có bậc 2 (kết nối với 1, 2)
- Đỉnh 4 có bậc 0
- Đỉnh 5 có bậc 1 (kết nối với 2)
- Đỉnh 6 có bậc 1 (kết nối với 1)
- Đỉnh 7 có bậc 0
- Đỉnh 8 có bậc 0

Các đỉnh có bậc lẻ là 1, 2, 5, 6. Để biến đồ thị thành đồ thị Euler, ta cần thêm cạnh để biến các đỉnh có bậc lẻ thành bậc chẵn. Số lượng cạnh ít nhất cần thêm bằng một nửa số đỉnh bậc lẻ. Ở đây, ta có 4 đỉnh bậc lẻ, nên ta cần ít nhất 4/2 = 2 cạnh.

Ví dụ, ta có thể thêm cạnh (1,5) và (2,6). Khi đó:

- Đỉnh 1 có bậc 4
- Đỉnh 2 có bậc 4
- Đỉnh 3 có bậc 2
- Đỉnh 4 có bậc 0
- Đỉnh 5 có bậc 2
- Đỉnh 6 có bậc 2
- Đỉnh 7 có bậc 0
- Đỉnh 8 có bậc 0

Hoặc ta có thể thêm cạnh (1,2) và (5,6). Khi đó:

- Đỉnh 1 có bậc 4
- Đỉnh 2 có bậc 4
- Đỉnh 3 có bậc 2
- Đỉnh 4 có bậc 0
- Đỉnh 5 có bậc 2
- Đỉnh 6 có bậc 2
- Đỉnh 7 có bậc 0
- Đỉnh 8 có bậc 0

Như vậy, cần thêm ít nhất 2 cạnh.

Để 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.