2006학년도 대학수학능력시험 수리 영역 가형 이산수학 29번

그림과 같이 $a$부터 $p$까지 $16$개의 꼭지점을 가지고 있는 평면 그래프가 있다. 이 그래프의 꼭지점 전체의 집합 $\{a,b,c,d,\cdots,p\}$를 분할할 때, 분할에 있는 모든 부분집합의 각 꼭지점들이 그래프에서 회로를 이루도록 분할하는 방법의 수는? (단, 전체 집합은 분할의 방법에서 제외한다.) [4점]