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?
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?
Giải Chuyên đề Tin 12 Bài 12: Biểu diễn đồ thị - Kết nối tri thức
Luyện tập 2 trang 61 Chuyên đề Tin học 12: 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?
Lời giải:
Có, từ ma trận kề A của đồ thị G, chúng ta có thể tính được số cạnh của đồ thị bằng cách đếm tổng số lượng phần tử có giá trị 1 trong ma trận kề.
Trong ma trận kề của một đồ thị vô hướng, mỗi cạnh được biểu diễn bởi một phần tử có giá trị 1. Do đó, để tính tổng số cạnh, chúng ta chỉ cần đếm tổng số lượng phần tử có giá trị 1 trong ma trận kề.
Tuy nhiên, trong một đồ thị vô hướng, mỗi cạnh thường được tính hai lần (một lần cho mỗi đỉnh mà nó kết nối). Vì vậy, sau khi đếm số lượng phần tử có giá trị 1 trong ma trận kề, chúng ta cần chia kết quả cho 2 để loại bỏ sự đếm lặp.
Do đó, cách tính số cạnh của đồ thị từ ma trận kề A như sau:
1. Đếm tổng số lượng phần tử có giá trị 1 trong ma trận kề A.
2. Chia kết quả cho 2.
Với một đồ thị vô hướng, số lượng cạnh là nửa số lượng phần tử có giá trị 1 trong ma trận kề.
Lời giải bài tập Chuyên đề Tin 12 Bài 12: Biểu diễn đồ thị hay, ngắn gọn khác:
Câu hỏi 1 trang 57 Chuyên đề Tin học 12: Vẽ đồ thị có tệp dữ liệu ma trận kề Hình 12.5 ....
Câu hỏi 2 trang 59 Chuyên đề Tin học 12: Khi nào ma trận kề A chỉ gồm toàn số 0? ....