Có bao nhiêu xâu nhị phân có độ dài nhỏ hơn hoặc bằng 8 bắt đầu là bít 1?

Đây là một bài toán ứng dụng nguyên lý Dirichlet (hay còn gọi là nguyên lý chuồng bồ câu). Nguyên lý này nói rằng nếu có n chuồng bồ câu và n+1 con bồ câu, thì ít nhất một chuồng phải có ít nhất 2 con bồ câu. Mở rộng ra, nếu có n chuồng và k*n + 1 con bồ câu thì có ít nhất một chuồng có k+1 con bồ câu trở lên. Trong bài toán này, các bậc điểm (A, B, C, D, E, F) đóng vai trò là "chuồng", và sinh viên đóng vai trò là "bồ câu". Ta có 6 "chuồng" (bậc điểm). Chúng ta muốn tìm số lượng sinh viên tối thiểu (số "bồ câu") sao cho chắc chắn có ít nhất 6 sinh viên ("6 con bồ câu") cùng đạt một bậc điểm (cùng "chuồng"). Áp dụng nguyên lý Dirichlet mở rộng: Nếu có n chuồng và k*n + 1 con bồ câu thì có ít nhất một chuồng chứa k+1 con bồ câu trở lên. Ở đây, ta muốn k+1 = 6, tức là k = 5. Và n = 6 (số bậc điểm). Vậy, số sinh viên tối thiểu cần có là k*n + 1 = 5 * 6 + 1 = 30 + 1 = 31. Vì vậy, cần phải có tối thiểu 31 sinh viên để chắc chắn rằng có ít nhất 6 người cùng đạt một điểm thi.

Đồ thị K₅ là đồ thị đầy đủ với 5 đỉnh. Khi bỏ đi một đỉnh và các cạnh liên thuộc với nó, ta được đồ thị đầy đủ với 4 đỉnh, tức là K₄. Đồ thị K₄ là một đồ thị phẳng. Các đồ thị K₆ và K₇ không có tính chất này. Đồ thị K₂ là đồ thị phẳng nên không thỏa mãn điều kiện đề bài.

Thuật toán Prim là một thuật toán tham lam được sử dụng để tìm cây khung nhỏ nhất cho một đồ thị liên thông có trọng số. Các thuật toán khác như Dijkstra (tìm đường đi ngắn nhất), BFS (tìm kiếm theo chiều rộng) và DFS (tìm kiếm theo chiều sâu) không được thiết kế để trực tiếp tìm cây khung nhỏ nhất.

Đỉnh treo trong đồ thị vô hướng là đỉnh có bậc bằng 1. Bậc của một đỉnh là số cạnh liên thuộc với đỉnh đó. Nếu một đỉnh chỉ có đúng một cạnh nối với nó, thì đó là đỉnh treo.

Ma trận kề của đồ thị có hướng biểu diễn mối quan hệ giữa các đỉnh. Một phần tử a(i, j) trong ma trận biểu thị có cạnh nối từ đỉnh i đến đỉnh j hay không. Vì đồ thị có hướng, nên việc có cạnh từ i đến j không nhất thiết kéo theo có cạnh từ j đến i. Do đó, ma trận kề không nhất thiết phải đối xứng. Phương án 1: Ma trận đối xứng là ma trận mà a(i, j) = a(j, i) với mọi i, j. Điều này không phải lúc nào cũng đúng với ma trận kề của đồ thị có hướng. Phương án 2: Ma trận đường chéo trên cũng không phải là đặc điểm bắt buộc của ma trận kề đồ thị có hướng. Ma trận đường chéo trên là ma trận mà tất cả các phần tử dưới đường chéo chính đều bằng 0, điều này không liên quan đến tính chất của ma trận kề. Phương án 3: Ma trận không đối xứng là ma trận mà không phải tất cả các phần tử a(i, j) đều bằng a(j, i). Đây là đặc điểm phổ biến của ma trận kề của đồ thị có hướng. Phương án 4: Tương tự như phương án 2, ma trận đường chéo dưới không phải là đặc điểm bắt buộc của ma trận kề. Vậy, ma trận kề của đồ thị có hướng không nhất thiết phải là ma trận đối xứng, ma trận đường chéo trên hoặc ma trận đường chéo dưới. Vì vậy, đáp án chính xác nhất là "Ma trận đối xứng".