Câu hỏi:
11/07/2024 167
Cây nhị phân có thể được coi là đồ thị vô hướng, các nút của cây sẽ tương ứng là đỉnh, còn quan hệ cha-con là cạnh nối của đồ thị. Với cây nhị phân hoàn chỉnh, các đỉnh được đánh số theo chỉ số của mảng biểu diễn tương ứng của cây. Hãy tính ma trận kề của đồ thị tương ứng cây nhị phân ở hình bên.
Cây nhị phân có thể được coi là đồ thị vô hướng, các nút của cây sẽ tương ứng là đỉnh, còn quan hệ cha-con là cạnh nối của đồ thị. Với cây nhị phân hoàn chỉnh, các đỉnh được đánh số theo chỉ số của mảng biểu diễn tương ứng của cây. Hãy tính ma trận kề của đồ thị tương ứng cây nhị phân ở hình bê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
Để tính ma trận kề của đồ thị tương ứng với cây nhị phân hoàn chỉnh, chúng ta cần xác định cách biểu diễn cây nhị phân hoàn chỉnh bằng mảng và sau đó chuyển đổi thông tin này thành ma trận kề. Trong cây nhị phân hoàn chỉnh, mỗi nút được đánh số theo chỉ số của mảng biểu diễn, và quan hệ cha-con được duy trì bằng cách tính toán chỉ số của các nút cha và con.
Dưới đây là cách tính ma trận kề của đồ thị tương ứng với cây nhị phân hoàn chỉnh:
1. Xác định số lượng đỉnh của cây nhị phân hoàn chỉnh. Số lượng đỉnh của cây nhị phân hoàn chỉnh có thể tính bằng công thức 2n−1, trong đó nnn là số tầng của cây.
2. Khởi tạo ma trận kề A với kích thước n×n và tất cả các phần tử đều bằng 0 ban đầu.
3. Duyệt qua từng nút của cây và thiết lập các cạnh nối trong ma trận kề:
- Nếu nút ở vị trí i có con trái (nếu có) ở vị trí 2i+1 và con phải (nếu có) ở vị trí 2i+2, thì đặt A[i][2i+1]=A[i][2i+2]=1 (do đỉnh i kết nối với đỉnh 2i+1 và 2i+2).
- Lưu ý rằng trong trường hợp số lượng đỉnh của cây không phải là một lũy thừa của 2, một số phần tử cuối cùng của mảng biểu diễn cây sẽ không có nút con, do đó cần kiểm tra điều kiện 2i+1 và 2i+2 có vượt quá số lượng đỉnh của cây hay không trước khi gán cạnh nối.
Một ví dụ chương trình Python thực hiện việc tính ma trận kề của đồ thị tương ứng với cây nhị phân hoàn chỉnh:
def calculate_adjacency_matrix_complete_binary_tree(levels):
n = 2 ** levels - 1 # Số lượng đỉnh của cây nhị phân hoàn chỉnh
A = [[0] * n for _ in range(n)] # Khởi tạo ma trận kề
# Thiết lập cạnh nối giữa các đỉnh
for i in range(n):
left_child = 2 * i + 1
right_child = 2 * i + 2
if left_child < n:
A[i][left_child] = 1
if right_child < n:
A[i][right_child] = 1
return A
# Số tầng của cây nhị phân hoàn chỉnh
levels = 3
# Tính ma trận kề của cây nhị phân hoàn chỉnh với số tầng là levels
adjacency_matrix = calculate_adjacency_matrix_complete_binary_tree(levels)
# In ma trận kề
for row in adjacency_matrix:
print(row)
Trong ví dụ này, chúng ta tính ma trận kề cho một cây nhị phân hoàn chỉnh có 3 tầng và in ra ma trận kề tương ứng. Đảm bảo rằng số tầng nnn là số nguyên không âm.
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Em hãy trao đổi, thảo luận và trả lời một số câu hỏi sau:
– Nếu đồ thị là vô hướng thì ma trận kề có đặc điểm gì?
– Phân biệt sự giống nhau và khác nhau giữa ma trận kề và danh sách kề?
– Khái niệm bậc của các đỉnh có gì khác nhau trong trường hợp đồ thị là vô hướng, có hướng?
Em hãy trao đổi, thảo luận và trả lời một số câu hỏi sau:
– Nếu đồ thị là vô hướng thì ma trận kề có đặc điểm gì?
– Phân biệt sự giống nhau và khác nhau giữa ma trận kề và danh sách kề?
– Khái niệm bậc của các đỉnh có gì khác nhau trong trường hợp đồ thị là vô hướng, có hướng?
Xem đáp án »
11/07/2024
164
Câu 2:
Viết lại các hàm thiết lập đồ thị BuildGraph(fname) với tệp dữ liệu đầu vào là danh sách các cạnh của đồ thị. Đầu ra của hàm là dãy các giá trị V, E, A, Adj. Viết hàm cho cả hai trường hợp đồ thị vô hướng và đồ thị có hướng.
Viết lại các hàm thiết lập đồ thị BuildGraph(fname) với tệp dữ liệu đầu vào là danh sách các cạnh của đồ thị. Đầu ra của hàm là dãy các giá trị V, E, A, Adj. Viết hàm cho cả hai trường hợp đồ thị vô hướng và đồ thị có hướng.
Xem đáp án »
26/06/2024
67
Câu 3:
Trong Nhiệm vụ 2, chúng ta có thể thấy các đỉnh kề không được in ra theo thứ tự tăng dần của chỉ số trong biểu diễn danh sách kề. Em hãy giải thích tại sao. Có thể chỉnh sửa chương trình để in ra các đỉnh kề theo thứ tự chỉ số tăng dần được không?
Trong Nhiệm vụ 2, chúng ta có thể thấy các đỉnh kề không được in ra theo thứ tự tăng dần của chỉ số trong biểu diễn danh sách kề. Em hãy giải thích tại sao. Có thể chỉnh sửa chương trình để in ra các đỉnh kề theo thứ tự chỉ số tăng dần được không?
Xem đáp án »
26/06/2024
64
Câu 4:
Trong Nhiệm vụ 1, hàm In_danh_sach_dinh_ke() lấy thông tin từ ma trận kề A. Có thể sử dụng hàm này với dữ liệu là danh sách kề Adj được không? Nếu có thì viết lại hàm này với dữ liệu đầu vào là danh sách kề Adj.
Trong Nhiệm vụ 1, hàm In_danh_sach_dinh_ke() lấy thông tin từ ma trận kề A. Có thể sử dụng hàm này với dữ liệu là danh sách kề Adj được không? Nếu có thì viết lại hàm này với dữ liệu đầu vào là danh sách kề Adj.
Xem đáp án »
26/06/2024
59
Bình luận
🔥 Đề thi HOT:
-
263 câu Trắc nghiệm tổng hợp ôn thi tốt nghiệp THPT môn Tin học Chủ đề F. Giải quyết vấn đề với sự trợ giúp của máy tính có đáp án
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 7: HTML và cấu trúc trang web
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 10: Tạo liên kết
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 11: Chèn tệp tin đa phương tiện và khung nội tuyến vào trang web
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 8: Định dạng văn bản
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 9: Tạo danh sách, bảng
-
15 câu Trắc nghiệm Tin học 12 Cánh diều Bài 1: Làm quen với ngôn ngữ đánh dấu siêu văn bản
-
Đề thi học kì 1 Tin học 12 Kết nối tri thức có đáp án- Đề 1
về câu hỏi!