| [ Teach ] in KIDS 글 쓴 이(By): guest (guest) <hydra.kaist.ac.> 날 짜 (Date): 1999년 4월 23일 금요일 오후 02시 54분 26초 제 목(Title): 그래프의 분할 문제 누구든지 다음의 문제에 대해서 아무런 힌트라도 주시면 감사하겠습니다. 그래프는 두 종류의 노드로 구성이 되어 있습니다. 편의상 M과 V라고 합시다. 아크는 M에서 V로만 존재합니다. 즉 bipartite입니다. 문제는 그래프를 disconnected하게 만들기 위해 제거되어야 하는 최소한의 M 노드를 구하는 것입니다. 이미 그래프가 disconnected되어 있으면 0 이 되겠지요. straight-forward한 방법은 처음에는 M 타입의 각 노드 하나를 제거해 가면서 제거되었을 때 ( 노드가 제거되면서 연결된 아크도 함께 제거합니다.) 그래프가 disconnected되는 지 조사합니다. 즉 n개의 M 타입 노드가 있는 그래프의 경우 n번을 시도해봐야 하겠지요. 한개의 M 타입 노드를 제거해서 분해가 되지 않으면, 이번에는 2개씩 묶어서 제거해 봅니다. 그러면, nC2개의 경우가 있겠지요. 이것도 싶해하면 3개씩 묶어서 제거를 해 봅니다. 결국 worst case는 2^n 경우가 존재하게 됩니다. 제가 원하는 것은 이 것보다 효율적인 알고리즘이 있는가 하는 것입니다. 그리고 있다면 그 복잡도는 얼마이고 구체적인 알고리즘을 알고 싶습니다. -- hschae@salmosa.kaist.ac.kr 채흥석 |