Ô A[u][v] nói về một cạnh trực tiếp
Đánh số n đỉnh từ 0 đến n−1. Ma trận kề A có n hàng, n cột: A[u][v]=1 nếu có cạnh từ u tới v, ngược lại bằng 0. Với đơn đồ thị, đường chéo chính bằng 0. Nếu vô hướng, A[u][v]=A[v][u].
A[0][5]=0 trong mẫu chỉ nói không có cạnh trực tiếp 0–5; vẫn có thể đi qua 1 và 3 để tới 5. Ma trận kề không phải ma trận khoảng cách hoặc bảng cho biết mọi đường đi gián tiếp.
Ma trận mẫu, hàng/cột theo thứ tự 0,…,6:
```text
0 1 1 0 0 0 0
1 0 0 1 1 0 0
1 0 0 0 1 0 0
0 1 0 0 0 1 0
0 1 1 0 0 1 0
0 0 0 1 1 0 0
0 0 0 0 0 0 0
```
Mỗi hàng liệt kê các chỉ số có cạnh đi tới
Danh sách kề Adj lưu Adj[u] là danh sách các đỉnh có cạnh từ u đi tới. Với mẫu:
```python
Adj = [[1,2], [0,3,4], [0,4], [1,5], [1,2,5], [3,4], []]
```
Hàng ma trận của đỉnh 0 là `[0,1,1,0,0,0,0]`, còn Adj[0] là `[1,2]`. Giá trị 1 trong ma trận là dấu hiệu có cạnh; giá trị 1 trong Adj[0] lại là **chỉ số đỉnh 1**. Đỉnh 6 cần hàng rỗng [] trong Adj; không được bỏ mất hàng này làm đổi số đỉnh.
Với đồ thị vô hướng, mỗi cạnh xuất hiện ở hai danh sách kề. Với đồ thị có hướng, chỉ ghi đỉnh nhận cạnh trong hàng của đỉnh xuất phát. Thứ tự các phần tử trong một hàng Adj có thể thay đổi mà vẫn biểu diễn cùng đồ thị, nhưng có thể làm đổi thứ tự duyệt.
Bài luyện
A[0][5]=0 nhưng có đường 0→1→3→5. Diễn giải nào đúng?
Ma trận kề chỉ biểu diễn cạnh trực tiếp.
Đúng. Phân biệt cạnh với đường đi.
Kết luận vượt quá ý nghĩa của ô 0.
Ô ma trận kề không phải khoảng cách.
Lời giải
A[u][v] ghi có hay không cạnh trực tiếp. A[0][5]=0 không cấm các chuỗi cạnh qua 1,3; vì vậy vẫn có đường 0→1→3→5.
Bài luyện
Trong mẫu, Adj[6] là gì?
Đây là dạng hàng ma trận, không là danh sách đỉnh kề.
Đơn đồ thị không có khuyên tại 6.
Đúng. 6 không có đỉnh kề nhưng vẫn có hàng rỗng.
Cần giữ đủ bảy hàng tương ứng bảy đỉnh.
Lời giải
Đỉnh 6 biệt lập nên danh sách các đỉnh kề của nó rỗng. Adj vẫn dài 7, với phần tử cuối là [], để giữ đúng chỉ số của mọi đỉnh.
Bài luyện
Tính chất nào bắt buộc với ma trận kề đơn đồ thị vô hướng?
Số đỉnh kề có thể khác nhau.
Không có khuyên nên đường chéo không là 1.
Một cạnh vô hướng được ghi ở cả hai chiều.
Đúng. Không có khuyên và cạnh không phân biệt hướng.
Lời giải
Không có khuyên nên A[u][u]=0. Mỗi cạnh u–v có cả hai chiều đi nên A[u][v]=A[v][u]. Hai điều kiện này không ép các hàng có cùng số 1.
Đang học