2017년 7월 10일 (월) 10:13 판 편집 Osteologia (토론 \| 기여) 점검 면제자, 장기인증된 사용자 39,111 편집 잔글 Osteologia님이 나무 (그래프 이론) 문서를 나무 그래프 문서로 이동했습니다: 괄호가 없는 제목을 선호. en:tree graph, nl:Boomstructuur 등 참고 ← 이전 편집		2017년 7월 10일 (월) 10:30 판 편집 편집 취소 Osteologia (토론 \| 기여) 점검 면제자, 장기인증된 사용자 39,111 편집 편집 요약 없음 다음 편집 →
1번째 줄: [[그래프 이론]]에서, '''나무 그래프'''({{llang\|en\|tree graph\|트리 그래프}}) 또는 단순하 '''나무'''는 [[순환 (그래프 이론)\|순환]]을 갖지 않는 [[연결 그래프]]이다. ~~[[파일:Tree graph.svg\|thumb\|200px\|6개의 꼭짓점을 갖는 나무]]~~ ~~[[그래프 이론]]에서, '''나무'''({{llang\|en\|tree\|트리}}는 [[순환 (그래프 이론)\|순환]]을 갖지 않는 [[연결 그래프]]이다.~~ == 정의 == ~~(단순~~[[그래프]] ~~무향) 그래프에~~<math>T</math>에 대하여 다음 조건들이 서로 [[동치]]이며, 이 조건을 만족시키는 그래프 <math>T</math>를 '''숲 그래프'''({{llang\|en\|forest graph\|포리스트 그래프}})이라고 한다. * <math>T</math>는 ~~길이가~~(길이 3 이상의) [[순환 (그래프 이론)\|순환]]을 갖지 않는다. * 임의의 두 꼭짓점 <math>v_1,v_2\in\operatorname V(T)</math>에 대하여, <math>v_1</math>과 <math>v_2</math> 사이의 [[경로 (그래프 이론)\|경로]]의 수는 1 이하이다. * <math>T</math>는 [[완전 그래프]] <math>K_3</math>를 [[마이너 (그래프 이론)\|마이너]]로 갖지 않는다. * <math>T</math>는 [[단일 연결 공간]]이다. (즉, 임의의 밑점 <math>v\in\operatorname V(T)</math>에 대하여, 1차 [[세포 호몰로지]] <math>\operatorname H_1(T,v)</math>가 [[자명군]]이다. 그러나 [[연결 공간]]이 아닐 수 있다.) ~~(단순~~[[그래프]] ~~무향) 그래프에~~<math>T</math>에 대하여 다음 조건들이 서로 [[동치]]이며, 이 조건을 만족시키는 그래프 <math>T</math>를 '''나무 그래프'''라고 한다. * <math>T</math>는 숲 그래프이며, [[연결 ~~숲이다~~그래프]]이다 (즉, 정확히 1개의 [[연결 성분]]을 갖는다). * 임의의 두 꼭짓점 <math>v_1,v_2\in V(T)</math>에 대하여, <math>v_1</math>과 <math>v_2</math> 사이의 [[경로 (그래프 이론)\|경로]]가 정확히 하나 존재한다. * <math>T</math>는 (1차원 [[세포 복합체]]로서) [[연결 공간\|연결]] [[단일 연결 공간]]이다. (특히, [[공집합]]이 아니다.) * 하나 이상의 꼭짓점을 가지며, 임의의 변 <math>e\in\operatorname E(T)</math>을 지운 그래프 <math>T-e</math>는 [[연결 ~~그래프가~~그래프]]가 아니다. 숲나무 그래프 <math>T</math>의 '''잎 꼭짓점'''({{llang\|en\|leaf vertex\|리프 버텍스}})은 차수가 ~~1 이하인~~1인 꼭짓점이며, '''내부 꼭짓점'''({{llang\|en\|internal vertex}})은 차수가 2 이상인 꼭짓점이다. 연결성분은 2개의 잎과 1개의 가지로 구성된다. 즉 2개의 점과 1개의 선으로 되어있는 연결그래프 트리의 최소단위이다. ~~<math>\therefore \; \left\|V(T)\right\|-\left\|E(T)\right\|=1</math>~~ == 성질 == 숲 그래프 <math>T</math>에 대하여 다음이 성립한다. <math>n</math>개의 꼭짓점 및 <math>c</math>개의 연결 성분을 갖는 숲은 <math>n-c</math>개의 변을 갖는다. 특히, 공집합이 아닌 나무의 경우 <math>c=1</math>이므로 변의 수는 <math>n-1</math>이다. <math>\|\operatorname V(T)\| = \|\operatorname E(T)\| + \|\operatorname{Conn}(T)\|</math> 여기서 * <math>\|\operatorname V(T)\|</math>는 <math>T</math>의 꼭짓점의 수이다. * <math>\|\operatorname E(T)\|</math>는 <math>T</math>의 변의 수이다. * <math>\|\operatorname E(T)\|</math>는 <math>T</math>의 연결 성분의 수이다. 특히, (공집합이 아닌) 나무의 경우 <math>c=1</math>이므로 변의 수는 <math>n-1</math>이다. ~~모든 숲은 [[이분 그래프]]이자 [[평면 그래프]]이다. [[경로 그래프]]는 나무이다.~~ 모든 숲 그래프는 [[이분 그래프]]이자 [[평면 그래프]]이다. [[#케일리의 정리\|케일리의 정리]]에 따르면, <math>n</math>개의 (이름 붙인) 꼭짓점 집합 위의 나무 구조의 수는 <math>n^{n-2}</math>이다. <math>n</math>개의 꼭짓점을 갖는 나무의 [[동형\|동형류]]의 수는 다음과 같다 (<math>n=0,1,2,\dots</math>). === 나무 그래프의 수 === <math>n</math>개의 꼭짓점을 갖는 나무 그래프의 [[동형\|동형류]]의 수는 다음과 같다 (<math>n=0,1,2,\dots</math>). :1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, … {{OEIS\|A000055}} ~~<math>n</math>개의 꼭짓점을 갖는 숲의 [[동형\|동형류]]의 수는 다음과 같다 (<math>n=0,1,2,\dots</math>).~~ <math>n</math>개의 꼭짓점을 갖는 숲 그래프의 [[동형\|동형류]]의 수는 다음과 같다 (<math>n=0,1,2,\dots</math>). :1, 1, 2, 3, 6, 10, 20, 37, 76, 153, 329, 710, 1601, 3658, … {{OEIS\|A005195}} === 프뤼퍼 열 === ~~==케일리의 정리==~~ 유한 나무 그래프 <math>T</math>의 꼭짓점 집합 ~~케일리의 정리 <math> T_n = n^{n-2}</math>~~ :<math>\operatorname nV(T)</math>~~은 점 갯수이다.~~ 에 임의의 [[정렬 순서]]를 주고, 그 [[순서형]]을 <math>n\in\operatorname{Ord}</math>이라고 하자. ~~:<math> T_n </math>은 <math> n</math>개의 점으로 연결될 수 있는 그래프(트리)의 갯수이다.~~ [[아서 케일리]]의 아이디어는 임의의 자연수 <math> n^{n-2}</math>개인 집합 <math>\left\{ x_1,x_2,x_3,.....x_{n-2} \right\}</math> 과 <math> n</math>개로 구성된 트리 집합은 서로 1:1 대응임을 보여주는것은 <math> T_n = n^{n-2}</math>와 동치임을 증명하게 된다는것이다. <math>T</math>에 대하여, 꼭짓점 [[열 (수학)\|열]] ~~[[File:Graph-theory-tree001.svg\|left\|100px\|Graph theory tree]]~~ :<math>x_0,x_1,\dotsc</math> ~~[[w:Heinz Prüfer\|하인츠 프뤼퍼(Heinz Prüfer)]]의 '''케일리의 정리'''~~ 을 다음과 같이 재귀적으로 정의하자. :<math>x_i = \min\{v\in \operatorname V(T)\setminus\{x_j\}_{j<i} \colon \deg_{T\setminus\{x_j\}_{j<i}} v = 1\}</math> 즉, 다음과 같다. * 임의의 순서수 <math>i < \|\operatorname V(T)\|</math>에 대하여, <math>x_i\in\operatorname V(T)</math>은 <math>T\setminus\{x_j\}_{j<i}</math>의 잎 꼭짓점 가운데, [[정렬 순서]]에 대하여 [[최소 원소]]이다. 유한 나무 그래프의 경우, 이 열은 <math>T</math>의 모든 꼭짓점을 한 번씩 포함한다. 즉, <math>T</math>의 꼭짓점 집합 <math>\operatorname V(T)</math> 위의 또다른 [[정렬 순서]]를 정의한다. (반면, 무한 나무 그래프의 경우 이는 그렇지 못할 수 있다.) 또한, 다음과 같은 꼭짓점 열 :<math>y_0,y_1,\dotsc</math> 을 <math>(x_i)_{i<\|\operatorname V(T)\|}</math>로부터 정의할 수 있다. :<math>(x_i,y_i) \in \operatorname E(T \setminus \{x_j\}_{j<i})</math> 즉, * <math>y_i</math>는 <math>T\setminus\{v_j\}_{j<i}</math>에서 <math>x_i</math>와 인접한 유일한 내부 꼭짓점이다. (만약 이러한 꼭짓점이 존재하지 않는다면, 이 열은 끝나게 된다.) 유한 나무 그래프의 경우, 꼭짓점 열 <math>y_i</math>의 길이는 <math>n-1</math>인데, 이는 맨 “마지막”의 경우 꼭짓점이 하나 밖에 남지 않기 때문이다. <math>(y_i)</math>를 <math>T</math>의 '''프뤼퍼 열'''(Prüfer列, {{llang\|en\|Prüfer sequence}})이라고 한다. 또한, 프뤼퍼 열에 대하여 다음이 성립한다. {\| class=wikitable ! 유한 나무 그래프 !! 프뤼퍼 열 \|- \| 꼭짓점의 수 \|\| 프뤼퍼 열의 길이 + 2 \|- \| 변의 수 \|\| 프뤼퍼 열의 길이 + 1 \|- \| 잎 꼭짓점 \|\| 프뤼퍼 열에 등장하지 않는 꼭짓점 \|- \| 내부 꼭짓점 \|\| 프뤼퍼 열에 등장하는 꼭짓점 \|- \| 꼭짓점의 차수 \|\| 프뤼퍼 열에 등장하는 수 + 1 \|} 모든 유한 나무 그래프는 그 프뤼퍼 열로부터 재구성될 수 있다. 이 알고리즘은 대략 다음과 같다. # 우선, 각 꼭짓점 <math>v</math>에 대하여 양의 정수 값의 변수 <math>\mathtt{d}_v</math>를, <math>v_i</math>가 프뤼퍼 열에 등장하는 수 + 1로 놓는다. # 프뤼퍼 열의 첫째 꼭짓점 <math>y_0</math>에 대하여, <math>\mathsf d_v=1</math>인 최소의 꼭짓점을 <math>v</math>라고 하면, ## 변 <math>(v,a_v)</math>를 [[그래프]]에 추가하며, ## <math>\mathtt d_{y_0}</math>과 <math>\mathtt d_v</math>를 각각 1만큼 감소시킨다. # 위 단계를 프뤼퍼 열의 둘째, 셋째 등등 꼭짓점에 대하여 반복한다. # 이 과정이 끝나면, <math>\mathtt d_v=1</math>인 꼭짓점이 두 개 남는다. 이들 사이에 변을 추가한다. # 알고리즘 종료. (반면, 무한 나무 그래프의 경우 이는 일반적으로 불가능하다. 예를 들어, 양쪽 무한 [[경로 그래프]]는 나무 그래프이지만, 잎 꼭짓점을 갖지 않아, 프뤼퍼 열이 자명하다.) === 케일리 공식 === ~~규칙1 - 숫자도 가장 낮으면서, 차수도 가장 낮은 점(즉, 잎)을 선택해 점과 선을 제거해나간다. 반복한다.~~ 임의의 크기 <math>n</math>의 [[유한 집합]] <math>V</math>가 주어졌다고 하자. 그렇다면, <math>V</math>를 꼭짓점으로 하는 나무 그래프의 수를 <math>T_n</math>이라고 하자. (이 경우, 꼭짓점들이 서로 구별되므로, 이는 나무 그래프의 동형류의 수와 다르다.) '''케일리 공식'''({{llang\|en\|Cayley’s formula}})에 따르면, 이는 다음과 같다. :<math>T_n=n^{n-2}</math> <div class="mw-collapsible mw-collapsed toccolours"> '''증명''': <div class="mw-collapsible-content"> 꼭짓점 집합 <math>V</math>에 임의의 [[정렬 순서]]를 주자. 그렇다면, <math>V</math> 위의 임의의 나무 그래프는 프뤼퍼 열에 유일하게 대응하며, 반대로 모든 프뤼퍼 열은 나무 그래프에 유일하게 대응된다. 프뤼퍼 열의 수는 :<math>n^{n-2}</math> 이다. </div></div> 크기 <math>n</math>의 [[유한 집합]] 위의 숲 그래프의 수는 다음과 같다. (<math>n=0,1,2,\dotsc</math>) :1, 1, 2, 7, 38, 291, 2932, 36961, 561948, 10026505, 205608536, 4767440679, 123373203208, 3525630110107, 110284283006640, 3748357699560961, 137557910094840848, 5421179050350334929, 228359487335194570528, 10239206473040881277575, 486909744862576654283616, … {{OEIS\|A1858}} 이 자연수열을 :<math>c_i</math> 라고 표기하면, 그 [[생성 함수 (수학)\|생성 함수]]는 :<math>\sum_{i=0}^\infty \frac1{i!}c_ix^i = \exp\left(\sum_{n=1}^\infty n^{n-2} \frac1{n!}x^n\right)=1+x+\frac12(2x^2) + \frac16(7x^3)+\dotsb</math> 이다. <div class="mw-collapsible mw-collapsed toccolours"> '''증명''': <div class="mw-collapsible-content"> 크기 <math>N</math>의 집합의 [[집합의 분할\|분할]]에서, 크기 <math>n</math>의 성분의 수가 <math>k_n</math>이라고 하자. 즉, :<math>\sum_{n=1}^\infty nk_n=N</math> 이다. 이 경우, 주어진 분할을 [[연결 성분]] 분할로 갖는 숲 그래프의 수는 ~~규칙2 - 순서대로 제거되는 점을 <math>x_i</math>의 집합으로하고, 제거되는 점의 인접한 점을 <math>y_i</math>의 집합으로 한다.~~ :<math>\prod_{n=1}^\infty (T_n)^{k_n} </math> 이다. 크기 <math>N</math>의 집합의 경우, 이러한 [[집합의 분할\|분할]]의 수는 ~~규칙3 - <math>2</math> 개의 인접한 점만이 남게 되면 제거 작업을 멈춘다.~~ :<math>\binom{N!}{\prod_{n=1}^\infty (n!)^{k_n} k_n!}</math> 이다. 따라서, [[생성 함수 (수학)\|생성 함수]] <math>f(x)</math>는 다음과 같은 유한 [[중복집합]]에 대한 합으로 나타내어진다. ~~위 <math>Pr\ddot{u}fer</math>의 규칙을 <math>\left\{ 1,2,3,4,5 \right\}</math>의 트리 그래프에 적용하면,~~ :<math> ~~:<math>\left\{ 1,2,4 \right\} = x</math><math>\; , \;\left\{ 2,3 ,3 \right\}=y</math>~~ \begin{aligned} ~~와 같이 수열의 집합이 나오게 됨을 확인할 수 있다.~~ f(x)&=\sum_{k\in M} \frac{x^{\|k\|}{\|k\|!} \frac{\left(\sum_{n=1}^\infty nk_n\right)!}{\prod_{n=1}^\infty (n!)^{k_n} k_n!} \prod_{n=1}^\infty (T_n)^{k_n}\\ &= \sum_{k\in M} \prod_{n=1}^\infty\left(\frac{T_nx_n}{n!}\right)^{k_n} \frac1{k_n!} \\ & =\prod_{n=1}^\infty\sum_{k_n=0}^\infty\left(\frac{T_nx_n}{n!}\right)^{k_n} \frac1{k_n!} \\ & =\prod_{n=1}^\infty\exp(T_nx^n/n!) \\ & =\exp\left(\sum_{n=1}^\infty T_nx^n/n!\right) \end{aligned} </math> 여기서 <math>M</math>는 유한 [[중복집합]]들, 즉 함수 :<math>k\colon\mathbb Z^+\to\mathbb N</math> :<math>k\colon n\mapsto k_n</math> 가운데 :<math>\sum_{n=1}^\infty nk_n<\infty</math> 인 것들의 족이며, :<math>\|k\| = \sum_{n=1}^\infty nk_n</math> 이다. </div></div> == 예 == ~~그럼, 그 역도 성립함을 확인해보면,~~ 정의에 따라, 모든 [[무변 그래프]]는 숲 그래프이며, 특히 한원소 그래프 <math>K_1</math>은 나무 그래프이다. ~~:<math>x \cup y =\left\{ 1,2,3,4 \right\} </math>를 예약하고,~~ ~~:<math>y</math> 집합을 통해서 <math>x </math>집합을 도출해보면,~~ ~~:<math>\left\{ 2,3,3 \right\} = y</math>에 없는 <math>x \cup y</math>의 가장 작은값은~~ ~~:<math> 1 </math>~~ ~~:<math>\left\{ 3,3 \right\} = y</math>에 없는 가장 작은값은~~ ~~:<math>2</math>~~ ~~:<math>\left\{ 3 \right\} = y</math>에 없는 가장 작은값은~~ ~~:<math>4</math>~~ ~~:<math>\therefore \left\{ 1,2,4 \right\} = x </math>의 순서대로 집합을 얻을 수 있겠다.~~ 임의의 양의 정수 <math>n</math>에 대하여, [[경로 그래프]] <math>P_n</math>은 나무 그래프이다. 또한, 양쪽 무한 [[경로 그래프]] ~~==케일리의 정리에 대한 <math>Pr\ddot{u}fer</math>의 증명==~~ :<math>P_\infty</math> ~~임의의 트리(나무) 그래프의 점과 선은 다음과 같다.~~ 및 한쪽 무한 [[경로 그래프]] :<math>P_\infty^+</math> 역시 둘 다 나무 그래프이다. === 프뤼퍼 열의 예 === ~~점은 <math>T = point(n)= \left\{ 1,2,3,.....n \right\}</math>~~ 다음과 같은 유한 나무 그래프 <math>T</math>를 생각하자. ~~:<math>x_i = \left\{ x_1,x_2,x_3....,x_{n-2} \right\} </math>이고,~~ :[[File:Tree graph.svg]] ~~:<math>y_i = \left\{ y_1,y_2,y_3....,y_{n-2} \right\} </math>일때,~~ 이 경우, ~~:<math>x_i</math>의 집합은 가장 낮은 값이면서 가장 낮은 차수의 점부터 제거 됨으로써 시작되는 순서있는 집합 수열이고,~~ # 잎 꼭짓점들은 <math>\{1,2,3,6\}</math>이며, 이 가운데 최솟값은 1이다. 이는 꼭짓점 4에 연결되어 있다. 즉, <math>x_0=1</math>이며 <math>y_0=4</math>이다. 이제, 꼭짓점 1을 제거하자. ~~:<math>y_i</math>는<math>x_i</math>의 인접한 점에 순서된 집합 수열이다.~~ # <math>T\setminus\{1\}</math>에서, 잎 꼭짓점들은 <math>\{2,3,6\}</math>이며, 이 가운데 최솟값은 2이다. 이는 꼭짓점 4에 연결되어 있다. 즉, <math>x_1=2</math>이며 <math>y_1=4</math>이다. 이제, 꼭짓점 2를 제거하자. 선은 # <math>T\setminus\{1,2\}</math>에서, 잎 꼭짓점들은 <math>\{3,6\}</math>이며, 이 가운데 최솟값은 3이다. 이는 꼭짓점 4에 연결되어 있다. 즉, <math>x_2=3</math>이며 <math>y_2=4</math>이다. 이제, 꼭짓점 3을 제거하자. ~~:<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>T\setminus\{1,2,3\}</math>에서, 잎 꼭짓점들은 <math>\{4,6\}</math>이며, 이 가운데 최솟값은 4이다. 이는 꼭짓점 5에 연결되어 있다. 즉, <math>x_3=4</math>이며 <math>y_2=5</math>이다. 이제, 꼭짓점 4를 제거하자. ~~:멈추어진 선<math>\left\{ x_{n-1},y_{n-1}\right\}</math>을 마지막 성분으로 가짐으로서,~~ # <math>T\setminus\{1,2,3,4\}</math>에서, 잎 꼭짓점들은 <math>\{5,6\}</math>이며, 이 가운데 최솟값은 5이다. 즉, <math>x_4=5</math>이다. 이는 꼭짓점 6에 연결되어 있으나, 이 역시 잎 꼭짓점이므로, 프뤼퍼 열은 끝난다. ~~:<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\},\left\{ x_{n-1},y_{n-1}\right\}\right\} </math>가 된다.~~ 즉, :<math>(y_0,\dotsc,y_4) = (4,4,4,5)</math> 이다. == 역사 == ~~그 역은~~ 케일리 공식은 [[아서 케일리]]가 증명하였다. 에른스트 파울 하인츠 프뤼퍼({{llang\|de\|Ernst Paul Heinz Prüfer}}, 1896~1934)는 1918년에 프뤼퍼 열을 도입하였으며, 이를 사용하여 이에 대한 다른 증명을 제시하였다. ~~:<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_3,y_3 \right\},......\left\{ x_{n-2},y_{n-2}\right\}\right\} </math>으로~~ ~~:멈추어진 선<math>\left\{ x_{n-1},y_{n-1}\right\}</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\},\left\{ x_{n-1},y_{n-1}\right\}\right\} </math>가 되어,~~ ~~그 역도 성립함을 확인할 수 있다.~~ ~~따라서 <math> T_n = n^{n-2}</math>이다.~~ == 참고 자료문헌 == * {{저널 인용\|제목=케일리 공식의 네가지 증명(\|저널=한국수학사학회지~~, 제21권제3호2008년8월,p127~142,~~\|권=21\|호=3\|날짜=2008-08\|쪽=127–142\|저자1=서승현,\|저자2=권석일,\|저자3=홍진곤)\|url=http://society.kisti.re.kr/sv/SV_svpsbs03V.do?method=download&cn1=JAKO200800557082835 \| 언어=ko}} 케일리 공식에 관한 연구(석사학위논문, 군산대학교 교육대학원,최정미,2003년8월) == 바깥 고리 == 줄 96 ⟶ 174: {{매스월드\|id=Tree\|title=Tree}} * {{매스월드\|id=Forest\|title=Forest}} * {{매스월드\|id=PrueferCode\|title=Prüfer code}} [[분류:그래프 이론]]

나무 그래프: 두 판 사이의 차이