maximum, maximal independent set in graphs

independent set 은 graph에서 서로 인접하지 않은 vertex의 집합을 말한다. 

그중에서도 다른 independent set의 subset이 아닌 independent set을 maximal independent set이라고 한다. 

 

출처 :위키피디아 https://en.wikipedia.org/wiki/Maximal_independent_set

위와같은 정육면체그래프가 있으면 빨간색 vertex끼리는 서로 인접하지 않는다. 이런 큐브형태의 정육면체는 maximal independent set이 6가지가 있다. 그중 가운데 2개는 vertex의 개수가 maximal independent set중에서 가장 많다. 이것을 maximum independent set 라고 부른다. 

즉, maximal independent set은 다른 independent set의 하위집합이 아닌 independent set이고, 그중 가장 vertex가 많은 것이 maximum independent set이다.