Kiểm tra bậc đỉnh biểu diễn đồ thị hay cây trong Python

Cho danh sách bậc của các đỉnh. Xác định xem chúng có tạo thành một cây hay một đồ thị tổng quát.

Điều kiện cần và đủ để một đồ thị vô hướng liên thông là cây: tổng bậc = 2*(số đỉnh - 1).

Ví dụ: deg = [2,2,3,1,1,1] → tổng = 10, số đỉnh = 6 → 2*(6-1)=10 → là Tree.

Giải thuật

• vert = len(deg).
• deg_sum = sum(deg).
• Nếu 2*(vert-1) == deg_sum trả về 'Tree', ngược lại 'Graph'.

Mã ví dụ

def solve(deg):
    vert = len(deg)
    deg_sum = sum(deg)
    if 2*(vert-1) == deg_sum:
        return 'Tree'
    return 'Graph'

deg = [2,2,3,1,1,1]
print(solve(deg))

Đầu vào

[2,2,3,1,1,1]

Đầu ra

Tree