나무 (그래프 이론)

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

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

정의[편집]

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

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

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

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

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

성질[편집]

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

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

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

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)

바깥 고리[편집]