폴리매스

서울지하철은 경의중앙선, 분당선, 공항철도 등등을 다 합치면 더 많지만 기본적으로는 1호선부터 9호선까지 있다. 환승역 개수는 다 안 세어 봐서 모르겠지만 대충 100개라고 가정하자. 이 때 아래 조건을 만족하는 서울지하철노선도의 경우의 수는?

<조건>

1. 모든 노선은 환승역에서 종착한다. 즉 환승역이 아닌 역에서 노선이 끝나면 안 된다.

2. 모든 노선은 일직선이다. 즉 실제 서울지하철 1,5호선처럼 갈라지지도, 2호선처럼 순환하지도, 6호선처럼 한쪽 끝에 고리를 만들지도 않는다.

3. 모든 노선의 색깔은 달리 하기 때문에 노선끼리의 구분은 간다.

4. 환승역에는 최소 2개의 노선이 만나야 하지만 환승역에 모이는 노선의 수는 아무리 많아도 상관없다.

5. 지하철노선도를 그릴 때는 환승역이 아닌 역은 표기하지 않는다.

6. 지하철노선도를 그릴 때 연결 상태가 같고(즉 위상이 같고) 모양만 다르게 그린 노선도는 같은 노선도로 본다.

7. 모든 노선은 환승역이 아닌 곳에서 교차하지 않는다.

(참고: 저도 막 떠오른 거라 저도 답 모릅니다. 그리고 제가 조건을 빠트렸을 수도 있으니 조건을 추가해야 한다고 생각하시면 알려주세요!)