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.

Để 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],

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