Independent Set (1) 썸네일형 리스트형 121. Independent Set & Clique 그래프에 포함된 정점 $0$개 이상을 포함한 집합이 다음 조건을 만족할 경우 그 집합을 그래프의 독립 집합(Independent Set)이라고 한다. 그래프에 존재하는 임의의 간선이 정점 $u$와 정점 $v$를 연결할 때, $u$와 $v$ 중 최소한 한 정점은 집합에 속하지 않는다. 간단히 말하면 독립 집합에 속한 정점들 사이를 직접 연결하는 간선이 없다는 것이다. 이것은 트리에도 똑같이 적용할 수 있고, 트리에 존재하는 독립 집합을 트리의 독립 집합이라고 한다. 또한 독립 집합들 중 가장 많은 정점을 포함하는 집합을 최대 독립 집합(Maximal Independent Set)이라고 한다. 하나의 그래프/트리에 두 개 이상의 최대 독립 집합이 존재할 수도 있다. 독립 집합을 정의할 때의 특이사항은 그래프.. 이전 1 다음
