나무 (그래프 이론)

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
6개의 꼭짓점을 갖는 나무

그래프 이론에서, 나무(영어: tree 트리[*]순환을 갖지 않는 연결 그래프이다.

정의[편집]

(단순 무향) 그래프에 대하여 다음 조건들이 서로 동치이며, 이 조건을 만족시키는 그래프 (영어: forest 포리스트[*])이라고 한다.

  • 는 길이가 3 이상의 순환을 갖지 않는다.
  • 임의의 두 꼭짓점 에 대하여, 사이의 경로의 수는 1 이하이다.
  • 완전 그래프 마이너로 갖지 않는다.
  • 단일 연결 공간이다. (즉, 자명군이다. 그러나 연결 공간이 아닐 수 있다.)

(단순 무향) 그래프에 대하여 다음 조건들이 서로 동치이며, 이 조건을 만족시키는 그래프 나무라고 한다.

  • 는 연결 숲이다.
  • 임의의 두 꼭짓점 에 대하여, 사이의 경로가 정확히 하나 존재한다.
  • 연결 단일 연결 공간이다.
  • 임의의 변 을 지운 그래프 는 연결 그래프가 아니다.

(영어: leaf 리프[*])은 차수가 1 이하인 꼭짓점이며, 내부 꼭짓점(영어: internal vertex)은 차수가 2 이상인 꼭짓점이다.

  • 연결성분은 2개의 잎과 1개의 가지로 구성된다. 즉 2개의 점과 1개의 선으로 되어있는 연결그래프 트리의 최소단위이다.

성질[편집]

개의 꼭짓점 및 개의 연결 성분을 갖는 숲은 개의 변을 갖는다. 특히, 공집합이 아닌 나무의 경우 이므로 변의 수는 이다.

모든 숲은 이분 그래프이자 평면 그래프이다. 경로 그래프는 나무이다.

케일리의 정리에 따르면, 개의 (이름 붙인) 꼭짓점 집합 위의 나무 구조의 수는 이다. 개의 꼭짓점을 갖는 나무의 동형류의 수는 다음과 같다 ().

1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, … (OEIS의 수열 A000055)

개의 꼭짓점을 갖는 숲의 동형류의 수는 다음과 같다 ().

1, 1, 2, 3, 6, 10, 20, 37, 76, 153, 329, 710, 1601, 3658, … (OEIS의 수열 A005195)

케일리의 정리[편집]

케일리의 정리

은 점 갯수이다.
개의 점으로 연결될 수 있는 그래프(트리)의 갯수이다.

아서 케일리의 아이디어는 임의의 자연수 개인 집합 개로 구성된 트리 집합은 서로 1:1 대응임을 보여주는것은 와 동치임을 증명하게 된다는것이다.

Graph theory tree

하인츠 프뤼퍼(Heinz Prüfer)케일리의 정리

규칙1 - 숫자도 가장 낮으면서, 차수도 가장 낮은 점(즉, 잎)을 선택해 점과 선을 제거해나간다. 반복한다.

규칙2 - 순서대로 제거되는 점을 의 집합으로하고, 제거되는 점의 인접한 점을 의 집합으로 한다.

규칙3 - 개의 인접한 점만이 남게 되면 제거 작업을 멈춘다.

의 규칙을 의 트리 그래프에 적용하면,

와 같이 수열의 집합이 나오게 됨을 확인할 수 있다.

그럼, 그 역도 성립함을 확인해보면,

를 예약하고,
집합을 통해서 집합을 도출해보면,
에 없는 의 가장 작은값은
에 없는 가장 작은값은
에 없는 가장 작은값은
의 순서대로 집합을 얻을 수 있겠다.

케일리의 정리에 대한 의 증명[편집]

임의의 트리(나무) 그래프의 점과 선은 다음과 같다.

점은

이고,
일때,
의 집합은 가장 낮은 값이면서 가장 낮은 차수의 점부터 제거 됨으로써 시작되는 순서있는 집합 수열이고,
의 인접한 점에 순서된 집합 수열이다.

선은

으로
멈추어진 선을 마지막 성분으로 가짐으로서,
가 된다.


그 역은

를 예약하고,
집합을 통해서 집합을 역으로 도출해보면,

에 대응되는 점을 순서대로 연산해보면,에 순서대로 에 없는 가장작은 수의 출현은가 되므로, 이것은 다시,

이 된 것이므로,

따라서 으로

멈추어진 선을 마지막 성분으로 가짐으로서,
가 되어,

그 역도 성립함을 확인할 수 있다. 따라서 이다.

참고 자료[편집]

  • 케일리 공식의 네가지 증명(한국수학사학회지, 제21권제3호2008년8월,p127~142,서승현,권석일,홍진곤)
  • 케일리 공식에 관한 연구(석사학위논문, 군산대학교 교육대학원,최정미,2003년8월)

바깥 고리[편집]