Giả sử cho một đồ thị, cần tìm kích thước tối thiểu của clique lớn nhất trong đồ thị. Clique là tập con đỉnh mà mọi cặp đỉnh đều kề nhau. Việc tìm clique lớn nhất là bài toán NP-hard, nhưng với số đỉnh và cạnh nhỏ, ta có thể tìm được.
Ví dụ, nodes = 4, edges = 4, đầu ra sẽ là 2.
Trong đồ thị trên, kích thước clique lớn nhất là 2.
Giải pháp
Để giải quyết bài toán này, ta sử dụng định lý Turán và tìm kiếm nhị phân:
- Định nghĩa hàm helper(x, y):
- ga := x % y
- gb := y - ga
- sa := x // y + 1
- sb := x // y
- Trả về ga * gb * sa * sb + ga * (ga - 1) * sa * sa // 2 + gb * (gb - 1) * sb * sb // 2
- i := 1, j := nodes + 1
- Khi i + 1 < j:
- p := i + (j - i) // 2
- k := helper(nodes, p)
- Nếu k < edges: i := p
- Ngược lại: j := p
- Trả về j
Ví dụ minh họa
Xem triển khai sau để hiểu rõ hơn:
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))
Đầu vào
4,4
Đầu ra
2