Tin học 12 · SGK Chuyên đề Khoa học máy tính

Bài 13. Thực hành thiết lập đồ thị

BÀI 13 THỰC HÀNH THIẾT LẬP ĐỒ THỊ

Sau bài học này em sẽ:

Em hãy trao đổi, thảo luận và trả lời một số câu hỏi sau:

Nhiệm vụ 1: Viết chương trình hiển thị danh sách kề

Đơn đồ thị vô hướng G = (V, E) được cho bởi ma trận kề A. Ma trận A được cho trong tệp văn bản có dạng:

Yêu cầu: Xác định danh sách kề của đồ thị trên, kết quả thể hiện ra màn hình, ví dụ như sau:

Đỉnh kề với 0: 1 2
Đỉnh kề với 1: 0 2 3
Đỉnh kề với 2: 0 1 3
Đỉnh kề với 3: 1 2

Hướng dẫn

Trong bài trước, chúng ta đã thiết lập hàm BuildGraph(fname) lấy dữ liệu từ tệp ma trận kề và trả về cặp dữ liệu V, A là danh sách đỉnh và ma trận kề của đồ thị. Hàm sau thể hiện danh sách kề trên màn hình theo đúng yêu cầu trên với tham số đầu vào là ma trận kề A.

def In_danh_sach_dinh_ke(A):
n = len(A)
for i in range(n):
print("Đỉnh kề với", i, end=": ")
for j in range(n):
if A[i][j] == 1:
print(j, end=" ")
print()

Phần chương trình chính của lời giải bài toán như sau:

f = "Data.inp"
V, A = BuildGraph(f)
In_danh_sach_dinh_ke(A)

Nhiệm vụ 2: Viết chương trình hiển thị ma trận kề, danh sách kề và bậc của đồ thị

Đơn đồ thị vô hướng G = (V, E) được cho bởi danh sách các cạnh. Danh sách các cạnh được cho trong tệp văn bản, trong đó dòng đầu tiên là số các đỉnh của đồ thị, các dòng tiếp theo mỗi dòng mô tả một cạnh của đồ thị.

4
0	1
1	3
0	2
2	3
1	2

Yêu cầu: Tính ma trận kề, danh sách kề và bậc của tất cả các đỉnh của đồ thị G.

Kết quả đưa ra màn hình được thể hiện như sau:

Ma trận kề	Danh sách kề	Bậc của các đỉnh của đồ thị
0 1 1 0	0 1 2	Đỉnh 0: 2
1 0 1 1	Đỉnh 3
1 1 0 1	2 0 3 1	Đỉnh 2: 3
0 1 1 0	3 1 2	Đỉnh 3: 2

Hướng dẫn

Trong bài trước, chúng ta đã thiết lập hàm BuildGraph(fname) lấy dữ liệu từ tệp văn bản và trả về cặp dữ liệu V, Adj là danh sách đỉnh và danh sách kề của đồ thị.

Nhiệm vụ yêu cầu tính và đưa ra màn hình ma trận kề của đồ thị. Chúng ta thiết lập hàm AdjacencyMatrix(Adj), đầu vào là danh sách kề Adj, đầu ra là ma trận kề A của đồ thị như sau:

def AdjacencyMatrix(Adj):
n = len(Adj)
A = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
for k in range(len(Adj[i])):
j = Adj[i][k]
A[i][j] = 1
return A

def show(A, op):
n = len(A)
for i in range(n):
if op == 1:
print(i, end=" ")
for j in range(len(A[i])):
print(A[i][j], end=" ")
print()

def show_deg(Adj):
n = len(Adj)
for i in range(n):
print("Đỉnh", i, len(Adj[i]))

Phần chương trình chính của bài toán như sau:

f = "Edges.inp"
V, Adj = BuildGraph(f)
A = AdjacencyMatrix(Adj)
print("Ma trận kề")
show(A, 0)
print("Danh sách kề")
show(Adj, 1)
print("Bậc của các đỉnh của đồ thị")
show_deg(Adj)

Bài 13. Thực hành thiết lập đồ thị