퀴즈가 2문제가 나왔는데
증명까지 써서 제출해야 하는데 문제당 4분을 줬다;
족보가 없으면 불가능하다고 개인적으로 생각 ㅜㅜ. 둘 다 못 풀었다.
1.
그래프가 주어졌을 때, k개 이하의 clique들로 그래프를 분할 할 수 있는지 판단하는 것은 np complete임을 증명하라.
더보기
complement graph를 생각한다.
즉 간선들의 연결관계를 뒤집는다.
그렇다면 originial graph에서의 clique는 complement graph에서 independent 하다.
즉 complement graph에서 k-coloring 문제와 정확히 동치임을 알 수 있다.
k-coloring은 k>=3에서 np-complete임을 아므로 끝.
2번 문제는 3-sat 어쩌구 였는데... 기억이 안나서 모르겠다
'알고리즘 공부 > The nature of computation' 카테고리의 다른 글
| 재미있는 과제 복습 (2) | 2022.12.04 |
|---|---|
| 공부 (1) | 2022.11.29 |