Câu hỏi:
11/07/2024 164
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?
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
Đặc điểm của ma trận kề đối với đồ thị vô hướng:
- zMa trận kề của đồ thị vô hướng là ma trận vuông.
- Các phần tử trên đường chéo chính của ma trận kề đều bằng 0 (vì không có cạnh nào nối đỉnh với chính nó trong đồ thị vô hướng).
- Ma trận kề là ma trận đối xứng qua đường chéo chính (tức là A[i][j]=A[j][i]) vì mỗi cạnh nối hai đỉnh với nhau được biểu diễn bởi một phần tử có giá trị 1 ở cả hai vị trí tương ứng trong ma trận.
Sự giống nhau và khác nhau giữa ma trận kề và danh sách kề:
- Giống nhau:
+ Cả ma trận kề và danh sách kề đều biểu diễn cấu trúc của đồ thị.
+ Cả hai cách biểu diễn đều cho phép xác định trực tiếp các cạnh của đồ thị.
- Khác nhau:
+ Ma trận kề là một ma trận vuông, trong khi danh sách kề là một danh sách có chiều dài bằng số lượng đỉnh trong đồ thị.
+ Ma trận kề có thể lãng phí không gian lưu trữ nếu đồ thị có ít cạnh, trong khi danh sách kề thường tiết kiệm không gian lưu trữ.
+ Truy cập vào một phần tử của ma trận kề có độ phức tạp thời gian là O(1), trong khi truy cập vào một phần tử của danh sách kề có thể có độ phức tạp thời gian là O(degree) (với degree là bậc của đỉnh tương ứng).
Khái niệm bậc của các đỉnh trong trường hợp đồ thị là vô hướng, có hướng:
+ Trong đồ thị vô hướng, bậc của một đỉnh là số lượng cạnh kề với đỉnh đó. Điều này có thể được tính bằng cách đếm số lượng phần tử có giá trị 1 trong hàng hoặc cột tương ứng của ma trận kề. Trong danh sách kề, bậc của một đỉnh là độ dài của danh sách kề tương ứng với đỉnh đó.
+ Trong đồ thị có hướng, bậc vào (in-degree) của một đỉnh là số lượng cạnh có điểm cuối là đỉnh đó. Bậc ra (out-degree) của một đỉnh là số lượng cạnh có điểm đầu là đỉnh đó.
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
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.
Xem đáp án »
11/07/2024
168
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
68
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
65
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!