트리(그래프 이론)

나무들
꼭지점 6개와 모서리 5개가 있는 레이블이 지정된 트리입니다.
꼭지점	v
가장자리	v − 1
색수	2 if v > 1
그래프 및 매개 변수 표

그래프 이론에서 트리는 두 꼭지점이 정확히 하나의 경로로 연결된 무방향 그래프 또는 동등하게 연결된 ^[1]비순환 무방향 그래프입니다.포레스트는 두 개의 정점이 최대 하나의 경로 또는 동등하게 비순환적인 무방향 그래프 또는 동등하게 분리된 ^[2]트리 결합으로 연결된 무방향 그래프입니다.

폴리^[3] 트리(또는 directed^[4] tree, directed^[5][6] tree, or or single connected^[7] network)는 기본 무방향 그래프가 트리인 Directed ascyclic graph(DAG; 유도 비순환 그래프)입니다.다포레스트(또는 방향성 포레스트 또는 방향성 포레스트)는 기본 무방향 그래프가 포레스트인 방향성 비순환 그래프입니다.

컴퓨터 과학에서 나무라고 불리는 다양한 종류의 데이터 구조는 그래프 이론에서 나무인 기본 그래프를 가지고 있지만, 이러한 데이터 구조는 일반적으로 루트 트리입니다.루트 트리는 방향성 루트 ^[8][9]트리라고 불리며, 그 모든 가장자리가 루트에서 멀어지도록 하거나(이 경우 수목^[4][10] 또는 아웃^[11][12] 트리),^[11][14] 또는 모든 가장자리가 루트를 가리키도록 하거나(이 경우 반수목^[13] 또는 인트리라고 불립니다).루트 트리 자체는 일부 저자에 의해 방향 ^[15][16][17]그래프로 정의되었습니다.뿌리 내린 숲은 뿌리 내린 나무들의 분리된 결합이다.루트 포레스트는 다이렉트 루트 포레스트라고 불리며, 각 루트 트리의 루트에서 모든 엣지가 포인트 되도록 하거나(이 경우 분기 또는 아웃 포레스트라고 불립니다), 또는 각 루트 트리의 루트를 가리키도록 모든 엣지가 포인트 되도록 합니다(이 경우 안티 분기 또는 인 포레스트라고 불립니다).

"나무"라는 용어는 1857년 영국의 수학자 아서 ^[18]케일리에 의해 만들어졌습니다.

정의들

트리

트리는 다음과 같은 동등한 조건 중 하나를 충족하는 무방향 그래프 G입니다.

• G는 연결되어 있고 비순환적입니다(사이클 없음).
• G는 비순환형이며, G에 엣지를 더하면 간단한 사이클이 형성된다.
• G가 연결되어 있지만 G에서 단일 에지가 제거되면 연결이 끊어집니다.
• G가 연결되어 있고, 3-vertex 완전 그래프₃ K는 G의 단수가 아니다.
• G의 두 정점은 고유한 단순 경로로 연결할 수 있습니다.

G가 정점(예를 들어 n개)이 완전히 많은 경우 위의 문장은 다음 조건 중 하나에 해당합니다.

• G가 연결되어 있고 n - 1개의 에지가 있습니다.
• G는 접속되어 있으며, G의 모든 서브그래프는 0 또는 1개의 입사 에지를 가진 적어도 1개의 정점을 포함한다.(즉, G는 접속되어 있고, 1-degrate입니다).
• G에는 단순한 사이클이 없으며 n - 1개의 에지가 있습니다.

그래프 이론의 다른 곳과 같이, 순서 0 그래프(정점이 없는 그래프)는 일반적으로 트리로 간주되지 않는다: 그래프로서 공백으로 연결되어 있는 동안(어떤 두 정점도 경로로 연결될 수 있음), 그것은 비어 있지 않은 트리와 달리 대수 위상에서 0으로 연결되어 있지 않으며(또는 심지어 -1) "가장자리보다 하나 더 많은 정점"을 위반한다.하지만 나무가 없는 숲으로 여겨질 수도 있다.

내부 정점(또는 내부 정점 또는 분기 정점)은 최소 2도의 정점이다.마찬가지로 외부 꼭지점(또는 외부 꼭지점, 종단 꼭지점 또는 잎)은 도수 1의 꼭지점입니다.

환원 불가능한 나무(또는 직렬 환원 나무)는 도수 2(^[19]OEIS의 시퀀스 A000014로 열거됨)의 정점이 없는 나무이다.

숲

포레스트는 두 개의 정점이 최대 1개의 경로로 연결된 무방향 그래프입니다.마찬가지로, 포레스트는 연결된 모든 구성요소가 나무인 무방향 비순환 그래프이다. 즉, 그래프는 나무의 분리된 결합으로 구성된다.특별한 경우로 순서 제로 그래프(제로 트리로 구성된 숲), 단일 트리, 모서리가 없는 그래프 등이 포레스트의 예입니다.모든 나무 V - E = 1에 대해 총 정점과 총 모서리 사이의 차이를 빼면 포레스트 내에 있는 나무 수를 쉽게 셀 수 있습니다.TV - TE = 숲의 나무 수.

폴리 트리

폴리^[3] 트리(또는 directed^[4] tree, directed^[5][6] tree, or or single connected^[7] network)는 기본 무방향 그래프가 트리인 Directed ascyclic graph(DAG; 유도 비순환 그래프)입니다.즉, 방향성이 없는 가장자리를 방향성이 없는 가장자리로 대체하면 연결성과 비순환성이 모두 있는 무방향 그래프를 얻을 수 있습니다.

일부^[who?] 저자는 모든 가장자리가 특정 정점으로 향하거나 모두 특정 정점으로 향하는 경우로 "방향 나무" 문구를 제한합니다(수목 원근 참조).

폴리포레스트

다포레스트(또는 방향성 포레스트 또는 방향성 포레스트)는 기본 무방향 그래프가 포레스트인 방향성 비순환 그래프입니다.즉, 방향성이 없는 모서리를 방향성이 없는 모서리로 대체하면 비순환적인 방향성이 없는 그래프를 얻을 수 있습니다.

일부^[who?] 저자는 연결된 각 구성요소의 가장자리가 모두 특정 정점으로 향하거나 모두 특정 정점에서 멀어지는 경우로 "방향 포레스트"라는 문구를 제한한다(분기 참조).

루트 트리

루트 트리는 하나의 정점이 ^[20]루트로 지정된 트리입니다.루트 트리의 가장자리는 루트로부터 멀리 떨어져 있거나 루트를 향해 자연스러운 방향을 할당할 수 있습니다.이 경우 이 구조물은 방향 루트 트리가 됩니다.방향성 루트 트리가 뿌리에서 떨어진 방향을 가지고 있는 경우, 수목^[4] 또는 아웃 ^[11]트리라고 하며, 루트를 향한 방향을 가지고 있는 경우, 반수목 또는 인 ^[11]트리라고 합니다.tree-order는 루트에서v로의 고유 경로가 u를 통과하는 경우에만 u < v인 트리 정점에서의 부분 순서입니다.이 트리 순서에서 G 내의 각 T 패스의 끝이 동등한 경우, 어떤 그래프 G의 서브 그래프인 루트 트리 T가 정규 트리이다(Diestel 2005, 페이지 15).루트 트리는 종종 각 정점의 인접 네트워크의 순서와 같은 추가 구조를 가지고 있으며 컴퓨터 과학의 핵심 데이터 구조입니다. 트리 데이터 구조를 참조하십시오.

일반적으로 트리에 루트가 있는 상황에서 지정된 루트가 없는 트리를 프리 트리라고 합니다.

레이블이 지정된 트리는 각 정점에 고유한 레이블이 지정된 트리입니다.n개의 정점에 라벨이 붙은 트리의 꼭지점에는 일반적으로 라벨 1, 2, …, n이 붙습니다.재귀 트리는 정점 라벨이 트리 순서를 존중하는 라벨이 붙은 루트 트리입니다(즉, 2개의 꼭지점 u와 v에 대해 u < v의 경우, u의 라벨은 v의 라벨보다 작습니다).

루트 트리에서 정점 v의 부모란 루트에 대한 경로 상의 v에 연결된 정점입니다.^[20] 부모가 없는 루트를 제외한 모든 정점은 고유한 부모를 가집니다.정점 v의 자식은 v가 ^[20]부모인 정점입니다.정점 v의 상승은 v의 부모이거나 (재귀적으로) v의 부모인 정점입니다.정점 v의 후예는 v의 자녀이거나 (재귀적으로) v의 자녀인 정점입니다.정점 v의 형제자매는 부모 v를 가진 나무상의 다른 정점입니다.잎은 아이가 ^[20]없는 꼭지점입니다.^[20]내부 정점은 ^[20]잎이 아닌 꼭지점입니다.

루트 트리의 정점 높이는 해당 정점에서 잎으로 가는 가장 긴 하향 경로의 길이입니다.나무의 높이는 뿌리의 높이입니다.정점의 깊이는 루트(루트 경로)에 대한 경로 길이입니다.이것은 다양한 셀프밸런싱 트리, 특히 AVL 트리의 조작에 일반적으로 필요합니다.뿌리에는 깊이 0, 잎에는 높이 0, 단일 정점(따라서 뿌리와 잎 모두)을 가진 트리에는 깊이와 높이가 0입니다.일반적으로 빈 나무(허용되는 경우 정점이 없는 나무)는 깊이와 높이가 -1이다.

k-아리 트리는 각 정점에 최대 k개의 ^[21]자녀가 있는 뿌리 나무입니다. 2-아리 트리는 종종 이진수라고 불리며 3-아리 트리는 때때로 삼원수라고도 불립니다.

순서 트리

순서 트리(또는 평면 트리)는 각 ^[20][22]정점의 자녀에 대해 순서가 지정된 루트 트리입니다.하위의 순서는 위쪽의 루트가 있고 각 정점의 하위가 해당 정점보다 낮은 평면에 트리를 포함하는 것과 같기 때문에 이를 "평면 트리"라고 합니다.평면에 뿌리나무를 심었을 때 왼쪽에서 오른쪽으로 등 아이의 방향을 고치면 심기는 아이의 순서를 부여한다.반대로, 순서 있는 트리가 주어지고, 통상적으로 꼭대기에 루트가 그려지면 순서 있는 트리의 자 정점은 왼쪽에서 오른쪽으로 그려질 수 있어 본질적으로 독특한 평면 매립을 얻을 수 있다.

특성.

• 모든 트리는 초당 그래프입니다.그래프는 홀수 길이의 사이클이 없는 경우에만 양분됩니다.트리는 사이클이 전혀 없기 때문에 초당적입니다.
• 정점이 셀 수 없을 정도로 많은 모든 트리는 평면 그래프입니다.
• 모든 연결된 그래프 G는 G의 모든 정점을 포함하고 가장자리가 G의 가장자리인 스패닝 트리를 허용합니다.모든 연결된 유한 그래프에 존재하는 보다 구체적인 유형의 스패닝 트리는 깊이 우선 탐색 트리와 폭 우선 탐색 트리를 포함합니다.깊이 우선 탐색 트리의 존재를 일반화하면, 셀 수 없을 정도로 많은 정점만 있는 연결된 모든 그래프에는 트리모 ^[23]트리가 있습니다.그러나 일부 셀 수 없는 그래프에는 이러한 ^[24]트리가 없습니다.
• n개의 정점이 있는 모든 유한 트리(n > 1)에는 적어도 2개의 정점(leave)이 있습니다.이 최소 잎 수는 경로 그래프의 특징이며, 최대 수 n - 1은 스타 그래프에 의해서만 달성된다.잎의 수는 최소한 최대 정점 도입니다.
• 트리의 3개의 정점에 대해 이들 사이의 3개의 경로는 정확히 하나의 정점을 공유합니다.일반적으로 그래프에서 3개의 정점 중 3개의 최단 경로에 속하는 정점을 이들 정점의 중앙값이라고 합니다.트리의 세 꼭지점마다 고유한 중위수가 있기 때문에 모든 트리는 중위수 그래프입니다.
• 모든 트리는 하나의 정점 또는 두 개의 인접한 정점으로 구성된 중심을 가집니다.중심은 모든 가장 긴 경로에서 중간 정점 또는 중간 두 정점입니다.마찬가지로 모든 n-vertex 트리는 하나의 정점 또는 두 개의 인접한 정점으로 구성된 중심을 가집니다.첫 번째 경우 정점을 제거하면 트리가 n/2개 미만의 정점으로 분할됩니다.두 번째 경우, 두 개의 중심 정점 사이의 가장자리를 제거하면 트리가 정확히 n/2개의 정점으로 이루어진 두 개의 하위 트리로 분할됩니다.

열거

라벨이 붙은 트리

케일리의 공식은 레이블이 지정된 n개의 정점에 n개의 나무가ⁿ⁻² 있음을 나타냅니다.고전적인 증명은 Prüfer 시퀀스를 사용하며, 이는 자연스럽게 더 강한 결과를 보여준다: 각각 d, d₂, …, d의_1n 정점이 1, 2, …, n인 나무의 수는 다항식 계수이다.

$\displaystyle {n-2\choose d_{1}-1,d_{2}-1,\ldots,d_{n}-1.}$

보다 일반적인 문제는 무방향 그래프에서 스패닝 트리를 카운트하는 것이며, 이는 매트릭스 트리 정리에 의해 해결됩니다.(케일리의 공식은 완전한 그래프에 스패닝 트리를 표시하는 특수한 경우입니다.)크기에 관계없이 모든 서브트리를 카운트하는 유사한 문제는 일반적인 경우 #P-complete이다(Jerrum(1994)).

라벨이 붙어 있지 않은 트리

라벨이 부착되지 않은 자유 나무의 수를 세는 것은 더 어려운 문제입니다.그래프 동형까지 n개의 정점이 있는 나무의 수 t(n)에 대한 닫힌 공식은 알려져 있지 않다.t(n)의 처음 몇 가지 값은

1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, …(OEIS의 시퀀스 A000055).

수달(1948년)은 점근 추정치를 증명했다.

${\displaystyle t(n)\sim C\alpha ^{n}n^{-5/2}\quad {text{as}}n\infty,}\infty,}$

C ≈ 0.534949606...α 2 2.95576528565...(OEIS의 시퀀스 A051491).여기서 ~ 기호는 다음을 의미합니다.

$\displaystyle \lim _{n\to \infty }{\frac {t(n)}{C\alpha ^{n}n^{-5/2}}=1.}$

이는 n개의 꼭지점을 가진 라벨이 부착되지 않은 뿌리 나무의 수 r(n)에 대한 그의 점근 추정의 결과이다.

${\displaystyle r(n)\sim D\alpha ^{n}n^{-3/2}\quad {text{as}}n\infty,}}\infty,}$

D 0 0.4392401257...상기와 같은 α(cf).Knuth(1997), chap. 2.3.4.4와 Flajolet & Sedgewick(2009), chap.(VII.5, 페이지 475)

r(n)의^[25] 처음 몇 가지 값은

1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, …(OEIS의 시퀀스 A000081)

나무의 종류

• 경로 그래프(또는 선형 그래프)는 i와 i + 1이 i = 1, …, n – 1에 대해 모서리로 연결되도록 한 선에 배열된 n개의 정점으로 구성됩니다.
• 별 모양의 나무는 루트라고 불리는 중심 꼭지점과 거기에 부착된 여러 개의 경로 그래프로 구성됩니다.좀 더 형식적으로 말하면, 나무는 정확히 2보다 큰 한 개의 정점을 가지고 있다면 별과 같다.
• 스타 트리는 단일 내부 정점(및 n – 1 잎)으로 구성된 나무입니다.즉, n계열의 스타 트리는 가능한 한 많은 잎을 가진 n계열의 트리이다.
• 캐터필러 트리는 모든 정점이 중앙 경로 하위 그래프의 거리 1 내에 있는 트리입니다.
• 바닷가재 나무는 모든 정점이 중앙 경로 하위 그래프의 거리 2 내에 있는 트리입니다.
• d도의 정규 트리는 각 정점에 d개의 가장자리가 있는 무한 트리입니다.이것들은 자유 그룹의 케일리 그래프와 Tits 빌딩 이론으로 나타난다.

「 」를 참조해 주세요.

• Decision Tree(결정 트리)
• 하이퍼 트리
• 멀티트리
• 의사 포레스트
• 트리 구조(일반)
• 트리(데이터 구조)
• 루트가 없는 이진 트리

메모들

레퍼런스

• Bender, Edward A.; Williamson, S. Gill (2010), Lists, Decisions and Graphs. With an Introduction to Probability
• 를 클릭합니다Dasgupta, Sanjoy (1999), "Learning polytrees", in Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Stockholm, Sweden, July–August 1999 (PDF), pp. 134–141.
• Deo, Narsingh (1974), Graph Theory with Applications to Engineering and Computer Science (PDF), Englewood, New Jersey: Prentice-Hall, ISBN 0-13-363473-6
• Harary, Frank; Prins, Geert (1959), "The number of homeomorphically irreducible trees, and other species", Acta Mathematica, 101 (1–2): 141–162, doi:10.1007/BF02559543, ISSN 0001-5962
• 를 클릭합니다Harary, Frank; Sumner, David (1980), "The dichromatic number of an oriented tree", Journal of Combinatorics, Information & System Sciences, 5 (3): 184–187, MR 0603363.
• 를 클릭합니다Kim, Jin H.; Pearl, Judea (1983), "A computational model for causal and diagnostic reasoning in inference engines", in Proc. 8th International Joint Conference on Artificial Intelligence (IJCAI 1983), Karlsruhe, Germany, August 1983 (PDF), pp. 190–193.
• 를 클릭합니다Li, Gang (1996), "Generation of Rooted Trees and Free Trees", M.S. Thesis, Dept. of Computer Science, University of Victoria, BC, Canada (PDF), p. 9.
• 를 클릭합니다Simion, Rodica (1991), "Trees with 1-factors and oriented trees", Discrete Mathematics, 88 (1): 93–104, doi:10.1016/0012-365X(91)90061-6, MR 1099270.

추가 정보

• 를 클릭합니다Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4.
• Flajolet, Philippe; Sedgewick, Robert (2009), Analytic Combinatorics, Cambridge University Press, ISBN 978-0-521-89806-5
• "Tree", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Knuth, Donald E. (November 14, 1997), The Art of Computer Programming Volume 1: Fundamental Algorithms (3rd ed.), Addison-Wesley Professional
• 를 클릭합니다Jerrum, Mark (1994), "Counting trees in a graph is #P-complete", Information Processing Letters, 51 (3): 111–116, doi:10.1016/0020-0190(94)00085-9, ISSN 0020-0190.
• 를 클릭합니다Otter, Richard (1948), "The Number of Trees", Annals of Mathematics, Second Series, 49 (3): 583–599, doi:10.2307/1969046, JSTOR 1969046.