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
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?
Giải Chuyên đề Tin 12 Bài 12: Biểu diễn đồ thị - Kết nối tri thức
Câu hỏi 1 trang 59 Chuyên đề Tin học 12: 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?
Lời giải:
Khẳng định này là đúng.
Trong ma trận kề A của một đồ thị vô hướng, mỗi hàng iii tương ứng với một đỉnh, và mỗi phần tử trong hàng đó biểu diễn một cạnh nối từ đỉnh iii đến một đỉnh khác. Nếu giá trị của một phần tử là 111, nghĩa là có cạnh nối từ đỉnh iii đến đỉnh tương ứng với vị trí của phần tử đó trong hàng.
Dãy Adj[i] là danh sách kề của đỉnh iii, tức là nó chứa tất cả các đỉnh kề với đỉnh iii. Vậy nếu số lượng phần tử trong Adj[i] bằng số lượng phần tử có giá trị 1 trong hàng thứ i của ma trận kề A, điều đó có nghĩa là mỗi phần tử có giá trị 1 trong hàng thứ i của A tương ứng với một đỉnh kề của đỉnh i, và do đó, khẳng định này là đúng.
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? ....