Câu hỏi:
11/07/2024 389
Một đơn đồ thị, vô hướng có n đỉnh, có thể có số cạnh lớn nhất là bao nhiêu?
Một đơn đồ thị, vô hướng có n đỉnh, có thể có số cạnh lớn nhất là bao nhiêu?
Câu hỏi trong đề:
Giải chuyên đề Tin 12 KNTT Bài 12: Biểu diễn đồ thị có đáp án !!
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
Trong một đơn đồ thị vô hướng có n đỉnh, số cạnh lớn nhất có thể có được là khi mỗi cặp đỉnh đều được nối với nhau bằng một cạnh. Điều này xảy ra khi đồ thị là đồ thị đầy đủ.
Một đồ thị đầy đủ có nnn đỉnh sẽ có tất cả các cặp đỉnh đều được nối với nhau bằng một cạnh.
Số cạnh của một đồ thị đầy đủ với n đỉnh được tính bằng công thức sau:
Do mỗi cặp đỉnh được nối với nhau bằng một cạnh, và số lượng cặp đỉnh là
(lấy một đỉnh, sau đó chọn một đỉnh từ n−1 đỉnh còn lại).
Vì vậy, số cạnh lớn nhất của một đơn đồ thị vô hướng với n đỉnh làNhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Từ ma trận kề A của đồ thị G có thể tính được số các cạnh của đồ thị không? Nếu được thì tính bằng cách nào?
Từ ma trận kề A của đồ thị G có thể tính được số các cạnh của đồ thị không? Nếu được thì tính bằng cách nào?
Xem đáp án »
11/07/2024
148
Câu 3:
Cho ma trận kề A của đồ thị vô hướng G. Viết hàm GraphEdge(A) trả lại danh sách E các cạnh của đồ thị G.
Cho ma trận kề A của đồ thị vô hướng G. Viết hàm GraphEdge(A) trả lại danh sách E các cạnh của đồ thị G.
Xem đáp án »
26/06/2024
106
Câu 5:
Tìm hiểu, thảo luận cách thiết lập dữ liệu của đồ thị trong trường hợp tệp dữ liệu biểu diễn danh sách các cạnh.
Tìm hiểu, thảo luận cách thiết lập dữ liệu của đồ thị trong trường hợp tệp dữ liệu biểu diễn danh sách các cạnh.
Xem đáp án »
11/07/2024
93
Câu 6:
Tìm hiểu, thảo luận về các cách biểu diễn dữ liệu của một đồ thị G.
Tìm hiểu, thảo luận về các cách biểu diễn dữ liệu của một đồ thị G.
Xem đáp án »
11/07/2024
84
về câu hỏi!