나무 그래프: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
56번째 줄:
:<math>4</math>
:<math>\therefore \left\{ 1,2,4 \right\} = x </math>의 순서대로 집합을 얻을 수 있겠다.
==케일리의 정리에 대한 <math>Pr\ddot{u}fer</math>의 증명==
임의의 트리(나무) 그래프의 점과 선은 다음과 같다.
점은 <math>T = point(n)= \left\{ 1,2,3,.....n \right\}</math>
:<math>x_i = \left\{ x_1,x_2,x_3....,x_{n-2} \right\} </math>이고,
:<math>y_i = \left\{ y_1,y_2,y_3....,y_{n-2} \right\} </math>일때,
:<math>x_i</math>의 집합은 가장 낮은 값이면서 가장 낮은 차수의 점부터 제거 됨으로써 시작되는 순서있는 집합 수열이고,
:<math>y_i</math>는<math>x_i</math>의 인접한 점에 순서된 집합 수열이다.
선은 <math>T_i = \left\{ \left\{ x_1,y_1 \right\},\left\{ x_2,y_2 \right\},\left\{ x_3,y_3 \right\},......\left\{ x_{n-2},y_{n-2}\right\}\right\} </math> 이다.
그 역은
:<math>x_i \cup y_i =\left\{ x_1,y_1,x_2,y_2,.....x_{n-2},y_{n-2} \right\} </math>를 예약하고,
:<math>y_i</math> 집합을 통해서 <math>x_i </math>집합을 역으로 도출해보면,
<math>y_i</math> 에 대응되는 점을 순서대로 연산해보면,<math>{y_1,y_2,....y_{n_2}}</math>에
순서대로 <math>x_i \cup y_i</math>에 없는 가장작은 수의 출현은<math>{x_1,x_2,....x_{n-2}}</math>가 되므로,
이것은 다시,
:<math>x_i = \left\{ x_1,x_2,x_3....,x_{n-2} \right\} </math>과
:<math>y_i = \left\{ y_1,y_2,y_3....,y_{n-2} \right\} </math>이 되어진것이므로,
:<math>\left\{\left\{ x_i,y_i \right\}: i=1,2,....,n-2 \right\}</math>
따라서 <math>\left\{\left\{ x_1,y_1 \right\},\left\{ x_2,y_2 \right\},......\left\{ x_{n-2},y_{n-2}\right\}\right\}</math>이 되어,
그 역도 성립함을 확인할수있다.
따라서 <math> T_n = n^{n-2}</math>이다.
== 바깥 고리 ==
| |||