中庸 中庸

그래프 G(V,E) 의 Independent Set 을 구하는 문제는 Cliques 를 구하는 문제로 reduction 할 수 있습니다. 먼저 Indepedent Set 과 Clique 의 정의에 대해 알아보도록 하겠습니다. Definition of Indepedent Set Graph G(V, E) 에 대해 Vertex set V’ ⊂ V 에 속한 모든 vertex 들이 서로 adjacent 하지 않으면 V’ 은 G 의 independent set 입니다. ( ∀ i, j ∈ V', (i, j) ∉ E 이면 V' 은 그래프 G의 Indepedent Set ) Definition of Clique Graph G(V, E)에 대해 Vertex set V’ ⊂ V 에 속한 모든 vertex 들이 서로 adj..