그래프가 주어졌을 때, 이 그래프에서 가장 큰 클리크(clique)의 최소 크기를 구하는 문제를 생각해 볼 수 있습니다. 클리크란 그래프 정점들의 부분 집합 중, 집합 안의 모든 정점 쌍이 서로 인접한 경우, 즉 임의의 두 정점 사이에 항상 간선이 존재하는 부분 그래프를 말합니다.
그래프에서 최대 클리크를 찾는 문제는 다항 시간 안에 해결할 수 없는 것으로 알려져 있습니다(NP-난해). 따라서 노드 수와 간선 수가 주어진 작은 그래프에서는 이 정보만을 바탕으로 최대 클리크의 크기를 계산해야 합니다.
예를 들어 입력이 nodes = 4, edges = 4라면 출력은 2가 됩니다.
위 그래프에서 클리크의 최대 크기는 2입니다.
문제 해결 접근 방법
이 문제는 다음과 같은 단계로 해결할 수 있습니다 −
- helper() 함수를 정의합니다. 이 함수는 x, y 두 값을 매개변수로 받습니다.
- ga := x mod y (x를 y로 나눈 나머지)
- gb := y − ga
- sa := (x ÷ y)의 몫 + 1
- sb := (x ÷ y)의 몫
- ga × gb × sa × sb + ga × (ga − 1) × sa × sa ÷ 2 + gb × (gb − 1) × sb × sb ÷ 2를 반환합니다.
- i := 1로 초기화합니다.
- j := nodes + 1로 초기화합니다.
- i + 1 < j를 만족하는 동안 다음을 반복합니다.
- p := i + (j − i) ÷ 2의 내림값
- k := helper(nodes, p)
- 만약 k < edges라면 i := p
- 그렇지 않으면 j := p
- j를 반환합니다.
동작 원리
helper(nodes, p) 함수는 전체 노드를 p개의 그룹에 최대한 균등하게 나눌 때, 서로 다른 그룹에 속한 정점 쌍의 개수, 즉 만들 수 있는 간선의 최대 개수를 계산합니다. 이는 조합론의 투란 그래프(Turán graph)의 간선 수와 같으며, 투란의 정리에 따르면 이 값은 크기가 p+1인 클리크를 포함하지 않는 그래프가 가질 수 있는 최대 간선 수입니다.
따라서 이분 탐색(binary search)을 활용하면 주어진 간선 수를 수용할 수 있는 최소의 p 값을 O(log 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))
입력
4,4
출력
2