산업안전기사 기출문제·모의고사·오답노트·자동채점

2003년08월31일 39번

[인간공학 및 시스템안전공학]
다음 그림의 결함수에서 최소 컷셋을 올바르게 구한 것은?시 정답과 해설을 확인하시기 바랍니다.)(오류 신고가 접수된 문제입니다. 반드시 정답과 해설을 확인하시기 바랍니다.)

  • ① (X1, X2)
  • ② (X1, X2, X3)
  • ③ (X1, X3)
  • ④ (X2, X3)
(정답률: 33%)

문제 해설

최소 컷셋은 소스 노드와 싱크 노드를 분리하는 최소한의 노드 집합을 의미합니다. 이 그래프에서는 소스 노드가 X1이고 싱크 노드가 X3입니다. 따라서 X1과 X3을 분리하는 최소한의 노드 집합을 찾아야 합니다.

(X1, X2)는 X1과 X3을 분리하는 최소한의 노드 집합입니다. 이유는 (X1, X2)를 제외한 모든 컷셋은 X1과 X3을 분리하지 못하기 때문입니다. 예를 들어, (X1, X2, X3)은 X1과 X3을 분리하지만, 불필요하게 X2도 포함되어 있습니다. (X1, X3)은 X2를 포함하지 않아 X1과 X3을 분리하지 못합니다. (X2, X3)은 X1과 X3을 분리하지 못합니다. 따라서 정답은 "(X1, X2)"입니다.

연도별