Câu hỏi:
26/06/2024 37Một đơn đồ thị, vô hướng có n đỉnh, có thể có số cạnh lớn nhất là bao nhiêu?
Siêu phẩm 30 đề thi thử THPT quốc gia 2024 do thầy cô VietJack biên soạn, chỉ từ 100k trên Shopee Mall.
Quảng cáo
Trả lời:
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:
(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à
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
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.
Câu 2:
Khẳng định dãy Adj[i] có số lượng phần tử bằng số các phần tử có giá trị 1 của hàng thứ i của ma trận kề A là đúng hay sai?
Câu 3:
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.
Câu 6:
Bổ sung thêm đoạn chương trình kiểm tra khi đọc dữ liệu danh sách các cạnh đồ thị của Hoạt động 3 như sau: Với mỗi dòng dữ liệu, nếu hai chỉ số i = j thì bỏ qua dòng này.
về câu hỏi!