สมมติว่าเราได้รับกราฟ และต้องการหาขนาดขั้นต่ำของเคล็ก (clique) ขนาดใหญ่ที่สุดในกราฟ เคล็กของกราฟคือเซตย่อยของกราฟที่ทุกคู่ของจุดยอดติดกัน คือมีเส้นขอบระหว่างทุกคู่ของจุดยอด การหาเคล็กขนาดใหญ่ที่สุดในกราฟทั่วไปไม่สามารถทำได้ใน polynomial time ดังนั้นเมื่อได้รับจำนวนโหนดและเส้นขอบของกราฟขนาดเล็ก เราต้องหาเคล็กขนาดใหญ่ที่สุดในมัน
เช่น ถ้าอินพุตคือ nodes = 4, edges = 4 ผลลัพธ์จะเป็น 2
ในกราฟด้านบน ขนาดสูงสุดของเคล็กคือ 2
วิธีแก้ปัญหา
- กำหนดฟังก์ชัน helper() รับ x, y:
- ga := x mod y
- gb := y - ga
- sa := ผลหารของ (x / y) + 1
- sb := ผลหารของ (x / y)
- return ga * gb * sa * sb + ga *(ga - 1) * sa * sa / 2 + gb * (gb - 1) * sb * sb / 2
- i := 1, j := nodes + 1
- while i + 1 < j:
- p := i + floor((j - i) / 2)
- k := helper(nodes, p)
- ถ้า k < edges: i := p
- มิฉะนั้น: j := p
- return j
ตัวอย่าง
import math
def helper(x, y):
ga = x % y
gb = y - ga
sa = x // y + 1
sb = x // y
return ga * gb * sa * sb + ga * (ga - 1) * sa * sa // 2 + gb * (gb - 1) * sb * sb // 2
def solve(nodes, edges):
i = 1
j = nodes + 1
while i + 1 < j:
p = i + (j - i) // 2
k = helper(nodes, p)
if k < edges:
i = p
else:
j = p
return j
print(solve(4, 4))
อินพุต
4,4
เอาต์พุต
2
