대 19 ‘방향그래프의 꼭짓점 나누기’ 풀이

[eqn: G]에서 [eqn: n]길이 경로는 4가지 경우가 있다. [eqn: I]를 지나는 경로, [eqn: I]에서 시작하는 경로, [eqn: I]를 지나지 않는 경로, [eqn: I]에서 끝나는 경로. 각각의 경로의 개수를 [eqn: g _{(1)n}], [eqn: g _{(2)n}], [eqn: g _{(3)n}], [eqn: g _{(4)n}]이라고 하자. 그리고, [eqn: H]에서 같은 종류의 경로를 [eqn: h _{(1)n}], [eqn: h _{(2)n}], [eqn: h _{(3)n}], [eqn: h _{(4)n}]이라고 하자.

Lemma (1)) [eqn: g _{(1)n} =h _{(1)n}], [eqn: g _{(2)n} =h _{(2)n} ,`g _{(3)n} =h _{(3)n} ,`2g _{(4)n} =h _{(4)n}]이다.

pf(1)) (1)[eqn: g _{(1)n} =h _{(1)n}]: [eqn: I]에서 끝나는 변의 개수를 [eqn: k], 그리고 [eqn: LEFT | A RIGHT | =x,` LEFT | B RIGHT | =y]라고 하자. 그러면 [eqn: g _{(1)n}][eqn: =k(x+y) TIMES c _{1}]이다. 그리고, [eqn: h _{(1)n}]=([eqn: I _{A}]를 지나는 경로의 개수)+([eqn: I _{B}]를 지나는 경로의 개수)=[eqn: (kx+ky) TIMES c _{1}]이다. 그러므로, [eqn: g _{(1)n} =h _{(1)n}]이다.

(2)[eqn: g _{(2)n} =h _{(2)n}]: [eqn: I]에서 시작하는 경로는 [eqn: (x+y)]이고, [eqn: h _{(2)n`}]=([eqn: I _{A}]에서 시작하는 경로의 수)+([eqn: I _{B}]에서 시작하는 경로의 수) =[eqn: x+y]이다. 즉, [eqn: g _{(2)n} =h _{(2)n}]이다.

(3)[eqn: g _{(3)n} =h _{(3)n}]: 어떤 경로가 [eqn: I]를 지나지 않는다면 [eqn: I _{A}], [eqn: I _{B}]도 거치지 않으므로, [eqn: g _{(3)n} =h _{(3)n}]임은 자명하다.  ><

(4)[eqn: 2g _{(4)n} =h _{(4)n}]: 그 이유는 [eqn: g _{(4)n}]=[eqn: k][eqn: TIMES c _{3}]이지만. [eqn: h _{(4)n} =]([eqn: I _{A}]에서 끝나는 경로의 수)+([eqn: I _{B}]에서 끝나는 경로의 수)=([eqn: k+k])[eqn: TIMES c _{3}]=[eqn: 2k][eqn: TIMES c _{3}]이다. 그러므로, [eqn: 2g _{(4)n} =h _{(4)n}]이다.

<본 증명> [eqn: g _{n} =g _{(1)n} +g _{(2)n} +g _{(3)n} +g _{(4)n} ,`h _{n} =h _{(1)n} +h _{(2)n} +h _{(3)n} +h _{(4)n}]이다. 그러면

[eqn: {g _{n}} over {h _{n}} = {g _{(1)n} +g _{(2)n} +g _{(3)n} +g _{(4)n}} over {h _{(1)n} +h _{(2)n} +h _{(3)n} +h _{(4)n}}]이다. 그리고, [eqn: lim _{n-> INF } {{1} over {a _{n}}}]=[eqn: {lim _{n-> INF } {1}} over {lim _{n-> INF } {a _{n}}} = {1} over {lim _{n-> INF } {a _{n}}}]이다.

즉, [eqn: lim _{n-> INF } {{g _{n}} over {h _{n}} = {1} over {lim _{n-> INF } {{h _{n}} over {g _{n}}}} =1}]이다. 그러므로, [eqn: lim _{n-> INF } {{h _{n}} over {g _{n}} =1}]이다.

[eqn: {h _{n}} over {g _{n}} = {h _{(1)n} +h _{(2)n} +h _{(3)n} +h _{(4)n}} over {g _{(1)n} +g _{(2)n} +g _{(3)n} +g _{(4)n}} = {g _{(1)n} +g _{(2)n} +g _{(3)n} +2g _{(4)n}} over {g _{(1)n} +g _{(2)n} +g _{(3)n} +g _{(4)n}} =1+ {g _{(4)n}} over {g _{(1)n} +g _{(2)n} +g _{(3)n} +g _{(4)n}} =1.]

즉, [eqn: lim _{n-> INF } {{h _{n}} over {g _{n}} = lim _{n-> INF } {(1+ {g _{(4)n}} over {g _{(1)n} +g _{(2)n} +g _{(3)n} +g _{(4)n}} )=1+ lim _{n-> INF } {{g _{(4)n}} over {g _{(1)n} +g _{(2)n} +g _{(3)n} +g _{(4)n}} =1.}}}]이다.

그러므로, [eqn: lim _{n-> INF } {{g _{(4)n}} over {g _{(1)n} +g _{(2)n} +g _{(3)n} +g _{(4)n}} =0}]이다. 즉, [eqn: lim _{n -> INF } {{1} over {{g _{(1)n} +g _{(2)n} +g _{(3)n}} over {g _{(4)n}} +1}} =0]이다.

그러므로, [eqn: lim _{n-> INF } {{g _{(1)n} +g _{(2)n} +g _{(3)n}} over {g _{(4)n}}} = INF]이다. 즉, [eqn: lim _{n-> INF } {{g _{(1)n} +g _{(2)n} +g _{(3)n}} over {g _{(4)n}}} > lim _{n-> INF } {{g _{(1)n}} over {g _{(4)n}} = lim _{n-> INF } {(x+y) TIMES {c _{1}} over {c _{3}}}}]이다.

그래프의 점의 개수가 무한개이여야 n이 무한이 될 수가 있다. 그런데, 여기에서 [eqn: c _{1}]은 [eqn: I]에서 끝나는 경로의 개수와 [eqn: I]에서 시작하는 경로의 개수의 곱이며, [eqn: c _{3}]은 [eqn: I]에서 끝나는 경로의 개수이므로, [eqn: {c _{1}} over {c _{3}}]은 [eqn: I]에서 시작하는 경로의 개수이다.

그러므로, [eqn: lim _{n-> INF } {(x+y)= INF ,` {c _{1}} over {c _{3}} = INF }]이다. 즉, [eqn: lim _{n-> INF } {{g _{n}} over {g _{(4)n}} = INF }]이다.

[eqn: Q.E.D]