Nếu G = (V, E) là một đơn đồ thị vô hướng thì:
Đáp án đúng: A
Câu hỏi liên quan
* Đáp án A đúng: "Có một cạnh xuất phát từ v" chính xác mô tả định nghĩa của một đỉnh có bậc 1 trong đồ thị vô hướng.
* Đáp án B sai: "Có hơn một cạnh xuất phát từ v" nghĩa là đỉnh v có bậc lớn hơn 1.
* Đáp án C sai: "Có đúng một cạnh đi vào và có hơn một đỉnh đi ra khỏi đỉnh này" không phù hợp với định nghĩa bậc của đỉnh trong đồ thị vô hướng. Hơn nữa, cách diễn đạt "đi vào" và "đi ra" thường được sử dụng cho đồ thị có hướng.
* Đáp án D sai: "Tồn tại khuyên ở đỉnh đó" có nghĩa là có một cạnh nối đỉnh đó với chính nó. Mỗi khuyên sẽ làm tăng bậc của đỉnh lên 2, nên đỉnh đó sẽ có bậc ít nhất là 2.
Đồ thị đầy đủ Kn là đồ thị vô hướng đơn giản có n đỉnh, trong đó giữa hai đỉnh bất kỳ đều có một cạnh nối.
Số đỉnh của đồ thị Kn là n.
Số cạnh của đồ thị Kn được tính bằng công thức tổ hợp chập 2 của n, tức là C(n, 2) = n! / (2! * (n-2)!) = n * (n-1) / 2.
Vậy, đồ thị đầy đủ Kn có n đỉnh và n(n-1)/2 cạnh.
Câu hỏi yêu cầu tìm định nghĩa đúng về cây khung của một đồ thị vô hướng liên thông. Cây khung của đồ thị G là một cây bao gồm tất cả các đỉnh của G và một số cạnh của G sao cho không tạo thành chu trình.
Phân tích các đáp án:
- A. T liên thông và mỗi cạnh của nó đều là cầu: Điều này đúng với một cây, nhưng chưa đủ để định nghĩa một cây khung của đồ thị G, vì nó không đề cập đến việc T phải chứa tất cả các đỉnh của G.
- B. Nếu thêm vào T một cạnh thì ta có ít nhất một chu trình: Điều này đúng với một cây, nhưng lại không liên quan trực tiếp đến định nghĩa cây khung của đồ thị G.
- C. VT = V, ET × E: VT = V có nghĩa là tập đỉnh của T bằng tập đỉnh của G, ET × E có nghĩa là ET là tích Descartes của E, điều này không đúng. Các cạnh của cây khung phải là các cạnh của đồ thị gốc (ET ⊆ E).
- D. T liên thông, có đúng n cạnh và ET × E: Điều này gần đúng, nhưng sai ở chỗ ET × E (tích Descartes) không có nghĩa, phải là ET ⊆ E (ET là tập con của E). Ngoài ra, một cây khung của đồ thị n đỉnh phải có n-1 cạnh, không phải n cạnh.
Tuy nhiên, không có đáp án nào hoàn toàn chính xác. Đáp án gần đúng nhất là C với lỗi sai về ký hiệu của tập cạnh. Đáp án D gần đúng, nhưng sai ở số cạnh và ký hiệu tập cạnh. Do đó, câu hỏi có thể có lỗi hoặc thiếu thông tin.
Nếu phải chọn một đáp án gần đúng nhất, ta chọn C với giả định rằng ký hiệu "×" có thể là một lỗi in ấn và nên được hiểu là "⊆" (tập con). Đáp án này đảm bảo rằng cây khung chứa tất cả các đỉnh của đồ thị gốc và các cạnh của nó là một phần của các cạnh trong đồ thị gốc.
