ปัญหา
ให้รายการเลขช่วงของจุดยอด ตรวจสอบว่าเป็นต้นไม้ (Tree) หรือกราฟทั่วไป (Graph)
ทฤษฎี
สำหรับกราฟที่มี V จุดยอด และ E เส้นขอบ:
- ต้นไม้:
E = V - 1และสัมพันธ์กัน - ผลรวมเลขช่วง =
2E(Handshaking Lemma) - ดังนั้น ต้นไม้ต้องมี
sum(degrees) = 2*(V-1)
ตัวอย่าง
deg = [2,2,3,1,1,1] → V=6, sum=10, 2*(6-1)=10 → "Tree"
โค้ดตัวอย่าง
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)) # Tree
อินพุต / เอาต์พุต
Input: [2,2,3,1,1,1] Output: Tree
