그래프 경로의 수

[출제의도] 그래프의 경로를 이해하여 경우의 수를 구할 수 있는가를 묻는 문제이다. (ⅰ) 변의 개수가 $1$인 경로 : $\mathrm{AF}$ ∴ $1$ (개) (ⅱ) 변의 개수가 $2$인 경로 : $\mathrm{AGF}$ ∴ $1$ (개) (ⅲ) 변의 개수가 $5$인 경로 : $\mathrm{AG}$$\mathrm{B} C$$\mathrm{G}$$\mathrm{F}$, $\mathrm{AG}$$\mathrm{C} B$$\mathrm{G}$$\mathrm{F}$, $\mathrm{AG}$$\mathrm{D} E$$\mathrm{G}$$\mathrm{F}$, $\mathrm{AG}$$\mathrm{E} D$$\mathrm{G}$$\mathrm{F}$ ∴ $4$ (개) (ⅳ) 변의 개수가 $8$인 경로 : $\mathrm{AG}$$\mathrm{B} C$$\mathrm{G}$$\mathrm{DE}$$\mathrm{G}$$\mathrm{F}$ $\mathrm{AG}$$\mathrm{C} B$$\mathrm{G}$$\mathrm{DE}$$\mathrm{G}$$\mathrm{F}$ $\mathrm{AG}$$\mathrm{B} C$$\mathrm{G}$$\mathrm{E} D$$\mathrm{G}$$\mathrm{F}$ $\mathrm{AG}$$\mathrm{C} B$$\mathrm{G}$$\mathrm{E} D$$\mathrm{G}$$\mathrm{F}$ $\mathrm{AG}$$\mathrm{DE}$$\mathrm{G}$$\mathrm{B} C$$\mathrm{G}$$\mathrm{F}$ $\mathrm{AG}$$\mathrm{DE}$$\mathrm{G}$$\mathrm{C} B$$\mathrm{G}$$\mathrm{F}$ $\mathrm{AG}$$\mathrm{E} D$$\mathrm{G}$$\mathrm{B} C$$\mathrm{G}$$\mathrm{F}$ $\mathrm{AG}$$\mathrm{E} D$$\mathrm{G}$$\mathrm{C} B$$\mathrm{G}$$\mathrm{F}$ ∴ $8$ (개) 따라서 꼭짓점 $\mathrm{A}$에서 꼭짓점 $\mathrm{F}$로 가는 모든 경로의 수는 $1 + 1 + 4 + 8 = 14$ (개) [참고] (1) 변의 개수가 $5$인 경로 : 경로 $\mathrm{AG}$$\mathrm{P} _{1} P _{2}$$\mathrm{G}$$\mathrm{F}$에서 두 꼭짓점 $\mathrm{P} _{1} , P _{2}$를 택하는 경우의 수는 $4 \times 1 = 4$ (개) (2) 변의 개수가 $8$인 경로 : 경로 $\mathrm{AG}$$\mathrm{P} _{1} P _{2}$$\mathrm{G}$$\mathrm{P} _{3} P _{4}$$\mathrm{G}$$\mathrm{F}$에서 네 꼭짓점 $\mathrm{P} _{1} , P _{2} , P _{3} , P _{4}$를 택하는 경우의 수는 $4 \times 1 \times 2 \times 1 = 8$ (개)