Kiểm tra xem các mức độ nhất định của các đỉnh có đại diện cho Đồ thị hoặc Cây trong Python hay không

Giả sử chúng ta có một danh sách các bậc của một số đỉnh. Chúng tôi phải kiểm tra xem nó đang hình thành biểu đồ hay cây.

Vì vậy, nếu đầu vào là deg =[2,2,3,1,1,1], thì đầu ra sẽ là Cây

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• vert:=số đỉnh
• deg_sum:=tổng của tất cả các giá trị bậc của tất cả các đỉnh
• nếu 2 * (vert-1) giống với deg_sum, thì
  • trả về 'Cây'
• trả về 'Biểu đồ'

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Mã mẫu

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