Câu hỏi:

26/06/2024 218

Cho ma trận kề A của đồ thị vô hướng G. Viết hàm GraphEdge(A) trả lại danh sách E các cạnh của đồ thị G.

Xem lời giải

Câu hỏi trong đề: Giải chuyên đề Tin 12 KNTT Bài 12: Biểu diễn đồ thị có đáp án !!

Bắt đầu thi

Quảng cáo

Trả lời:

Giải bởi Vietjack

Để viết hàm GraphEdge(A) trả về danh sách các cạnh của đồ thị vô hướng từ ma trận kề A, chúng ta có thể sử dụng phương pháp duyệt qua ma trận kề và tạo danh sách các cạnh dựa trên các phần tử có giá trị 1.

Dưới đây là cách triển khai hàm này bằng Python:

def GraphEdge(A):

n = len(A)

edges = []

for i in range(n):

for j in range(i+1, n): # Chỉ cần duyệt nửa phần tam giác trên của ma trận

if A[i][j] == 1: # Nếu có cạnh nối từ đỉnh i đến đỉnh j

edges.append((i, j)) # Thêm cạnh vào danh sách cạnh

return edges

# Ví dụ sử dụng

A = [

[0, 1, 1, 0],

[1, 0, 0, 1],

[0, 1, 1, 0]

]

print(GraphEdge(A)) # In danh sách các cạnh của đồ thị G

Trong hàm này, chúng ta duyệt qua mỗi phần tử của ma trận kề A. Nếu phần tử A[i][j] có giá trị 1 (tức là có cạnh nối từ đỉnh i đến đỉnh j), chúng ta thêm cạnh (i,j) vào danh sách các cạnh. Chúng ta chỉ cần duyệt qua nửa phần tam giác trên của ma trận kề để tránh lặp lại việc đếm các cạnh hai lần. Cuối cùng, chúng ta trả về danh sách các cạnh đã tạo.

Hot: 500+ Đề thi thử tốt nghiệp THPT các môn, ĐGNL các trường ĐH... file word có đáp án (2025). Tải ngay

Sách thầy cô Vietjack biên soạn:

Xem thêm »

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1

Một đơn đồ thị, vô hướng có n đỉnh, có thể có số cạnh lớn nhất là bao nhiêu?

Xem đáp án

Lời giải

Trong một đơn đồ thị vô hướng có n đỉnh, số cạnh lớn nhất có thể có được là khi mỗi cặp đỉnh đều được nối với nhau bằng một cạnh. Điều này xảy ra khi đồ thị là đồ thị đầy đủ.

Một đồ thị đầy đủ có nnn đỉnh sẽ có tất cả các cặp đỉnh đều được nối với nhau bằng một cạnh.

Số cạnh của một đồ thị đầy đủ với n đỉnh được tính bằng công thức sau:

Một đơn đồ thị, vô hướng có n đỉnh, có thể có số cạnh lớn nhất là bao nhiêu? (ảnh 1)

Do mỗi cặp đỉnh được nối với nhau bằng một cạnh, và số lượng cặp đỉnh là

(lấy một đỉnh, sau đó chọn một đỉnh từ n−1 đỉnh còn lại).

Vì vậy, số cạnh lớn nhất của một đơn đồ thị vô hướng với n đỉnh là

Câu 2

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?

Xem đáp án

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ề.

Câu 3