Chuyển dữ liệu mà giữ nguyên các cạnh
to_matrix đặt 1 ở ô tương ứng từng cạnh; to_adj lấy các chỉ số cột có giá trị 1. to_edges của đồ thị vô hướng chỉ lấy u<v để mỗi cạnh xuất hiện một lần. Các hàm giả định dữ liệu hợp lệ của đơn đồ thị.
```python
def to_matrix(Adj):
n = len(Adj)
A = [[0]*n for _ in range(n)]
for u in range(n):
for v in Adj[u]:
A[u][v] = 1
return A
def to_adj(A):
return [[v for v in range(len(A)) if A[u][v] == 1]
for u in range(len(A))]
def to_edges(Adj, directed=False):
return [(u, v) for u in range(len(Adj)) for v in Adj[u]
if directed or u < v]
```
Chạy demo.py và đối chiếu ba tệp
Tải bộ mẫu ở bài cuối, giải nén đủ tệp rồi chạy demo.py bằng Python 3. Dòng `Ba tep khop: True` cho biết canh.inp, ma_tran.inp và ke.inp mô tả cùng đồ thị. Dòng bậc là `[2,3,2,2,3,2,0]`; có 7 cạnh và 2 thành phần liên thông.
Có thể kiểm thêm trong chương trình:
```python
Adj = [[1,2], [0,3,4], [0,4], [1,5], [1,2,5], [3,4], []]
A = to_matrix(Adj)
print(to_adj(A) == Adj)
print(len(to_edges(Adj)))
```
Kết quả True và 7. Tổng bậc 14 chia 2 cũng cho 7. Với có hướng, tổng bậc ra hoặc tổng bậc vào bằng số cạnh; không chia 2. Đếm bậc ra u bằng len(Adj[u]); bậc vào u bằng số hàng có chứa u.
Để thực hành, sửa bản sao một cạnh rồi cập nhật cả ba tệp theo đúng hướng. Nếu đối chiếu False, kiểm ô đối xứng, nhãn đầu hàng hoặc cạnh bị bỏ sót. Không ép ma trận có hướng phải đối xứng.
Bài luyện
Vì sao to_edges dùng điều kiện u<v cho đồ thị vô hướng?
Chỉ tránh ghi lặp, không thay quan hệ đi hai chiều.
Đúng. Hai hàng Adj đang ghi hai chiều của cùng cạnh.
Cặp trong danh sách không tự đổi bản chất đồ thị.
u<v không yêu cầu hai số liên tiếp.
Lời giải
Adj vô hướng ghi v trong hàng u và u trong hàng v. Chỉ lấy đầu nhỏ hơn trước giúp ghi cạnh ấy đúng một lần, giữ nguyên ý nghĩa vô hướng.
Bài luyện
Đồ thị vô hướng có tổng bậc 14 thì số cạnh là bao nhiêu?
Mỗi cạnh đã được đếm ở hai đầu.
Cần chia 2, không nhân 2.
Đúng. 14/2=7.
Tổng bậc xác định hai lần số cạnh trong trường hợp này.
Lời giải
Mỗi cạnh vô hướng có hai đầu nên đóng góp 2 vào tổng bậc. Do đó số cạnh bằng 14/2=7.
Bài luyện
Đồ thị có hướng có tổng bậc ra 5. Số cạnh bằng bao nhiêu?
Đúng. Mỗi cạnh có đúng một đầu xuất phát.
Không nhân hai trong tổng bậc ra.
Không chia hai trong tổng bậc ra.
Có các cạnh đi ra nên không thể bằng 0.
Lời giải
Mỗi cạnh có hướng góp một vào bậc ra của đỉnh xuất phát. Cộng bậc ra mọi đỉnh đếm mỗi cạnh một lần nên có 5 cạnh.
Đang học