Hãy cho biết quy tắc (Luật) nào là cơ sở của mô hình suy diễn sau:

Thuật toán sinh tổ hợp chập k của n phần tử hoạt động bằng cách tìm từ phải sang trái phần tử a[i] đầu tiên mà a[i] < n - k + i. Sau đó tăng a[i] lên 1 đơn vị và cập nhật các phần tử phía sau a[i] theo quy tắc a[j] = a[j-1] + 1 với j > i.

Xét cấu hình 1 4 5 6:

* Phương án A: 2 1 3 5: Đây không phải là một tổ hợp hợp lệ vì các phần tử không được sắp xếp tăng dần.
* Phương án B: 1 2 4 6: Tìm từ phải sang trái, phần tử đầu tiên thỏa mãn a[i] < n - k + i là a[2] = 2 (vì 2 < 6 - 4 + 2 = 4). Tăng a[2] lên 1 thành 3. Các phần tử phía sau sẽ là a[3] = 3 + 1 = 4, a[4] = 4 + 1 = 5. Vậy cấu hình sinh ra là 1 3 4 5, khác với cấu hình 1 4 5 6.
* Phương án C: 1 3 5 6: Tìm từ phải sang trái, phần tử đầu tiên thỏa mãn a[i] < n - k + i là a[2] = 3 (vì 3 < 6 - 4 + 2 = 4). Tăng a[2] lên 1 thành 4. Các phần tử phía sau sẽ là a[3] = 4 + 1 = 5, a[4] = 5 + 1 = 6. Vậy cấu hình sinh ra là 1 4 5 6.
* Phương án D: 2 1 4 5: Đây không phải là một tổ hợp hợp lệ vì các phần tử không được sắp xếp tăng dần.

Vậy, cấu hình 1 3 5 6 sinh ra cấu hình 1 4 5 6 theo thuật toán sinh tổ hợp.

Trong đồ thị đủ Kn, mỗi đỉnh được nối với tất cả các đỉnh còn lại. Vì vậy, mỗi đỉnh sẽ có bậc là n - 1. Đáp án C là đáp án chính xác.

Duyệt đồ thị theo chiều sâu (DFS) bắt đầu từ đỉnh 1. Ta xét các đỉnh kề với đỉnh 1 theo thứ tự từ điển: 2, 3, 6.

- Nếu đi theo đỉnh 2: Ta có đường đi 1 - 2. Từ đỉnh 2, xét các đỉnh kề theo thứ tự từ điển: 3, 5, 6.
- Nếu đi theo đỉnh 3: Ta có đường đi 1 - 2 - 3. Từ đỉnh 3, các đỉnh kề là 1, 2. Đã duyệt 1 và 2 nên quay lui.
- Nếu đi theo đỉnh 5: Ta có đường đi 1 - 2 - 5. Từ đỉnh 5, xét các đỉnh kề theo thứ tự từ điển: 4, 6.
- Nếu đi theo đỉnh 4: Ta có đường đi 1 - 2 - 5 - 4. Từ đỉnh 4, xét các đỉnh kề theo thứ tự từ điển: 5, 6.
- Nếu đi theo đỉnh 5: Đã duyệt.
- Nếu đi theo đỉnh 6: Ta có đường đi 1 - 2 - 5 - 4 - 6. Đây là một đường đi từ 1 đến 6.
- Nếu đi theo đỉnh 6: Ta có đường đi 1 - 2 - 5 - 6. Đây là một đường đi từ 1 đến 6.
- Nếu đi theo đỉnh 6: Ta có đường đi 1 - 2 - 6. Đây là một đường đi từ 1 đến 6.
- Nếu đi theo đỉnh 3: Ta có đường đi 1 - 3. Từ đỉnh 3, các đỉnh kề là 1, 2. Đã duyệt 1 và 2 nên quay lui.
- Nếu đi theo đỉnh 6: Ta có đường đi 1 - 6. Đây là một đường đi từ 1 đến 6.

Như vậy, các đường đi từ 1 đến 6 có thể tìm được bằng DFS là: 1 - 6, 1 - 2 - 6, 1 - 2 - 5 - 6, 1 - 2 - 5 - 4 - 6. Do các đỉnh được xét theo thứ tự từ điển, đường đi tìm thấy đầu tiên sẽ là 1 - 6.