Nếu G là đồ thị Euler thì:
Đáp án đúng: D
Một đồ thị được gọi là đồ thị Euler nếu nó có một chu trình Euler. Chu trình Euler là một chu trình đi qua tất cả các cạnh của đồ thị đúng một lần. Điều kiện cần và đủ để một đồ thị liên thông là đồ thị Euler là tất cả các đỉnh của nó đều có bậc chẵn.
Phương án A sai vì đồ thị Euler có tất cả các đỉnh bậc chẵn.
Phương án B sai vì đồ thị Euler có đường đi Euler (và chu trình Euler).
Phương án C sai vì theo định nghĩa, đồ thị Euler phải có chu trình Euler.
Phương án D đúng vì theo định nghĩa, đồ thị Euler phải có chu trình Euler.
Câu hỏi liên quan
Trong lý thuyết đồ thị, một cây là một đồ thị liên thông không có chu trình. Một tính chất quan trọng của cây là số cạnh của nó luôn ít hơn số đỉnh đúng một đơn vị. Vì vậy, nếu một cây có 1000 đỉnh, số cạnh của nó sẽ là 1000 - 1 = 999.
Tuy nhiên, không có đáp án nào trùng khớp với kết quả này. Có lẽ có sự nhầm lẫn ở đây. Giả sử câu hỏi muốn hỏi số cạnh của một đồ thị đầy đủ (complete graph) thì công thức là n(n-1)/2. Tuy nhiên, các đáp án cũng không phù hợp với giả thiết này.
Vì không có đáp án đúng, tôi sẽ chọn đáp án gần đúng nhất là 1001 (D), coi như là một lỗi đánh máy và số đỉnh lẽ ra là 1002.
Tuy nhiên, với thông tin hiện tại của câu hỏi, không có đáp án nào chính xác theo định nghĩa chuẩn của cây trong lý thuyết đồ thị.
- Phương án A không đúng vì chu trình Euler đi qua mỗi cạnh một lần, không phải mỗi đỉnh một lần. Một đỉnh có thể được ghé thăm nhiều lần.
- Phương án B đúng vì đây chính xác là định nghĩa của chu trình Euler.
- Phương án C không đúng vì chu trình Euler phải đi qua mỗi cạnh đúng một lần, không phải không quá một lần.
- Phương án D không đúng vì chu trình Euler chỉ đi qua đỉnh đầu và đỉnh cuối một lần (trừ điểm bắt đầu và kết thúc của chu trình là cùng một đỉnh).
Trong lý thuyết đồ thị, một lát cắt (X, Y) trong đồ thị G = (V, E) là một sự phân hoạch các đỉnh V thành hai tập hợp X và Y. Tập hợp các cạnh mà một đầu nằm trong X và đầu còn lại nằm trong Y được gọi là tập cạnh cắt của lát cắt (X, Y).
Phân tích các lựa chọn:
- Lựa chọn A: "Tập hợp tất cả các cung (vi, vj) sao cho hoặc vi x X, vj x Y và vj x X, vi x Y" - Có vẻ như có một lỗi nhỏ trong câu này. Theo định nghĩa lát cắt, một cung (vi, vj) thuộc lát cắt nếu vi thuộc X và vj thuộc Y, hoặc vi thuộc Y và vj thuộc X. Tuy nhiên, việc sử dụng liên từ "và" (vi x X, vj x Y và vj x X, vi x Y) là không chính xác vì nó đòi hỏi cả hai điều kiện phải đúng đồng thời, điều này không thể xảy ra.
- Lựa chọn B: "Tập hợp tất cả các cung (vi, vj) sao cho hoặc vi x X, vj x Y hoặc vj x X, vi x Y" - Đây là định nghĩa chính xác của một lát cắt. Nó bao gồm tất cả các cung mà một đầu nằm trong X và đầu kia nằm trong Y, hoặc ngược lại.
- Lựa chọn C: "Tập hợp tất cả các cung (vi, vj) sao cho hoặc vi x X, vj x X hoặc vj x X, vi x Y" - Lựa chọn này không đúng vì nó bao gồm trường hợp cả hai đỉnh vi và vj đều thuộc X, điều này không thuộc định nghĩa của lát cắt giữa hai tập X và Y.
- Lựa chọn D: "Tập hợp tất cả các cung (vi, vj) sao cho hoặc vi x X, vj x Y hoặc vj x Y, vi x Y" - Có vẻ như lựa chọn này có một lỗi nhỏ. Phần "vj x Y, vi x Y" có vẻ như bị lặp. Nó nên là "vj x Y, vi x X".
Vậy đáp án đúng là B.
