알앤이 때문에 찾아보고 있는데 내가 이해한 게 맞는지 모르겠음


independent set(독립집합) : 서로 인접(=edge로 연결) 하지 않는 vertex의 집합

dominating set(지배집합, 우세집합) : 모든 vertex와 인접하게 할 수 있는 v의 집합

cover((집합의)덮개) = dominating set  ??

maximum independent set : G에 대해서 꼭짓점 수가 최대인 독립 집합


그래프의 maximal indep. set(극대 독립 집합)은 dominating set이다.

((maximal indep.set = dominating set))


어떤 집합이 독립집합이다 <=> 여집합이 vertex cover이다.

(bipartite graph : maximum indep.set 크기 = 최소 vertex cover크기)   (위키피디아)


1. 집합의 cover와 그래프의 dominant set은 무슨 관계?

2. 왜 bipartite graph에서는 최대독립집합의 크기가 cover의 크기랑 같음? 윗부분에는 독립집합의 여집합이 cover라고 했는데..


그래프이론 잘 아는 사람들 좀 도와줘..