Một dự án đánh số điện thoại có dạng NYX NNX XXXX.Trong đó, X là các số từ 0 đến 9 , Y là các số hoặc 0 hoặc 1, N là các số từ 2 đến 9, hỏi có nhiều nhất là bao nhiêu số điện thoại khác nhau được đánh số?

Để một đồ thị vô hướng tồn tại với một dãy bậc cho trước, dãy đó phải thỏa mãn hai điều kiện: (1) Tổng các bậc phải là một số chẵn (vì mỗi cạnh đóng góp 2 vào tổng bậc). (2) Với dãy bậc đã sắp xếp giảm dần d1 >= d2 >= ... >= dn, với mọi k từ 1 đến n, phải có tổng (d1 + d2 + ... + dk) <= k(k-1) + tổng (min(dk+1, k) + min(dk+2, k) + ... + min(dn, k)). Kiểm tra từng đáp án: 1. 1, 4, 3, 2, 5, 6. Tổng bậc là 1+4+3+2+5+6 = 21, là số lẻ, nên không thể tồn tại đồ thị. 2. 2, 1, 5, 2, 3, 3. Tổng bậc là 2+1+5+2+3+3 = 16, là số chẵn. Sắp xếp lại: 5, 3, 3, 2, 2, 1. - k = 1: 5 <= 0 + (min(3, 1) + min(3, 1) + min(2, 1) + min(2, 1) + min(1, 1)) = 0 + (1+1+1+1+1) = 5. Đúng. - k = 2: 5+3 = 8 <= 2*1 + (min(3, 2) + min(2, 2) + min(2, 2) + min(1, 2)) = 2 + (2+2+2+1) = 9. Đúng. - k = 3: 5+3+3 = 11 <= 3*2 + (min(2, 3) + min(2, 3) + min(1, 3)) = 6 + (2+2+1) = 11. Đúng. - k = 4: 5+3+3+2 = 13 <= 4*3 + (min(2, 4) + min(1, 4)) = 12 + (2+1) = 15. Đúng. - k = 5: 5+3+3+2+2 = 15 <= 5*4 + (min(1, 5)) = 20 + 1 = 21. Đúng. - k = 6: 5+3+3+2+2+1 = 16 <= 6*5 + 0 = 30. Đúng. Như vậy, đáp án này có thể tồn tại. 3. 2, 4, 3, 4, 3, 2. Tổng bậc là 2+4+3+4+3+2 = 18, là số chẵn. Sắp xếp lại: 4, 4, 3, 3, 2, 2. - k = 1: 4 <= 0 + (min(4, 1) + min(3, 1) + min(3, 1) + min(2, 1) + min(2, 1)) = 0 + (1+1+1+1+1) = 5. Đúng. - k = 2: 4+4 = 8 <= 2*1 + (min(3, 2) + min(3, 2) + min(2, 2) + min(2, 2)) = 2 + (2+2+2+2) = 10. Đúng. - k = 3: 4+4+3 = 11 <= 3*2 + (min(3, 3) + min(2, 3) + min(2, 3)) = 6 + (3+2+2) = 13. Đúng. - k = 4: 4+4+3+3 = 14 <= 4*3 + (min(2, 4) + min(2, 4)) = 12 + (2+2) = 16. Đúng. - k = 5: 4+4+3+3+2 = 16 <= 5*4 + (min(2, 5)) = 20 + 2 = 22. Đúng. - k = 6: 4+4+3+3+2+2 = 18 <= 6*5 + 0 = 30. Đúng. Như vậy, đáp án này có thể tồn tại. 4. 1, 4, 3, 2, 2, 3. Tổng bậc là 1+4+3+2+2+3 = 15, là số lẻ, nên không thể tồn tại đồ thị. Vì câu hỏi hỏi đồ thị nào *tồn tại*, và có 2 đáp án thỏa mãn (2 và 3), nên có thể có lỗi trong câu hỏi hoặc các đáp án. Tuy nhiên, nếu chúng ta giả sử chỉ có một đáp án đúng, ta chọn đáp án 3 vì các số bậc có vẻ "cân bằng" hơn.

Đồ thị phân đôi đầy đủ K_m,n có tập đỉnh được chia thành hai tập con rời nhau, một tập có m đỉnh và tập còn lại có n đỉnh. Một cạnh tồn tại giữa hai đỉnh nếu và chỉ nếu một đỉnh thuộc tập con m đỉnh và đỉnh còn lại thuộc tập con n đỉnh. Số đỉnh của đồ thị là m+n và số cạnh là m*n. Phương án sai là phương án 3: "Có một cạnh giữa hai đỉnh nếu và chỉ nếu mỗi đỉnh đều thuộc vào hai tập đỉnh con.", vì mỗi đỉnh chỉ thuộc một trong hai tập con.

Đồ thị vô hướng có đường đi Euler (hay còn gọi là đường đi Euler) khi và chỉ khi nó liên thông và có đúng hai đỉnh bậc lẻ. Đường đi Euler là đường đi đi qua tất cả các cạnh của đồ thị đúng một lần.

• Liên thông: Đồ thị phải liên thông, tức là phải có đường đi giữa mọi cặp đỉnh trong đồ thị.
• Hai đỉnh bậc lẻ: Nếu đồ thị có đúng hai đỉnh bậc lẻ, thì đường đi Euler sẽ bắt đầu từ một trong hai đỉnh bậc lẻ này và kết thúc ở đỉnh bậc lẻ còn lại.

Vậy, đáp án đúng là "Liên thông và có hai đỉnh bậc lẻ."

Một đồ thị có hướng G = (V, E) được gọi là liên thông mạnh nếu giữa hai đỉnh bất kỳ u, v thuộc V, luôn tồn tại đường đi từ u đến v và ngược lại, từ v đến u. Điều này có nghĩa là ta có thể đi từ bất kỳ đỉnh nào đến bất kỳ đỉnh nào khác trong đồ thị theo cả hai chiều.

Cây là một đồ thị vô hướng liên thông và không chứa chu trình. Điều này có nghĩa là giữa hai đỉnh bất kỳ trong cây luôn có một đường đi duy nhất và không có đường đi nào bắt đầu và kết thúc ở cùng một đỉnh mà không đi qua cạnh nào hai lần (chu trình). Các phương án khác không đúng vì chúng vi phạm các tính chất cơ bản của cây: cây phải liên thông, không được chứa chu trình, và số cạnh của cây luôn nhỏ hơn số đỉnh là 1.