폴리 트리

수학, 특히 그래프 이론에서 폴리트리(polytree^[1], directed ^[2]tree, directed^[3] tree, or onely connected^[4] network)는 기본 무방향 그래프가 트리인 방향 비순환 그래프이다.즉, 방향성이 없는 가장자리를 방향성이 없는 가장자리로 대체하면 연결성과 비순환성이 모두 있는 무방향 그래프를 얻을 수 있습니다.

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

폴리 트리는 방향 그래프의 한 예입니다.

폴리트리라는 용어는 1987년 Rebane과 ^[5]Pearl에 의해 만들어졌다.

관련 구조

• 수목은 유도 루트 트리, 즉 유도 비순환 그래프로, 단일 소스 노드가 존재하며 다른 모든 노드에 대한 고유 경로를 가진다.모든 수목은 폴리 트리이지만 모든 수목은 수목은 아닙니다.
• 멀티트리는 임의의 노드에서 도달 가능한 서브그래프가 트리를 형성하는 방향 비순환 그래프입니다.모든 폴리 트리는 멀티 트리입니다.
• 폴리 트리의 노드 간의 도달 가능성 관계는 최대 3개의 순서 차원을 가진 부분 순서를 형성합니다.순서 치수가 3인 경우$,$ 각 $(디스플레이$ 스타일 i=$0,$ 1, 2$(디스플레이$$$$스타일$ i$=0,$ ${\displaystyle 1}$,$2,$2)에 대해 x ${\displaystyle \le }$ ${\displaystyle {}_{}{}_{}}$≥ y ≥ y 、 { i $\}$ 、 ${\displaystyle y_{}}$ 、 $、$ y （ ${\displaystyle i_{}}$ }$$） 、 y$$$（$ displaystyle$$z _ {$$$i$ $\}$$$） ${\displaystyle \mathrm{elements}}$ elements elements elements elements $elements{\displaystyle }$ of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of $of$$\geq z_{i}$ $또는$ x ${\displaystyle \ge }$ ${\displaystyle y_{}{}_{}}$ ${\displaystyle z_{}}$ i$${ $displaystyle$x \ $geq y _$ { i } \$leq z _$ { i$$} 。이러한 6개의 부등식은 이들 7개의 ^[6]요소에서 폴리트리 구조를 정의합니다.
• 펜스 또는 지그재그 포셋은 폴리 트리의 특별한 경우로, 기초 트리가 경로이고 가장자리에 경로를 따라 번갈아 가면서 방향이 지정됩니다.폴리 트리에서의 도달 가능성 순서는 일반 ^[7]펜스라고도 불립니다.

열거

라벨이 부착되지 않은n$$$${ $displaystyle$ n$$}개의 노드(n ${\displaystyle =1}$,${\displaystyle 2}$, 3${\displaystyle }$, $...$ { $displaystyle$ n $= 1, 2, 3$ , \ displaystyle$\}$ )의 $고유{\displaystyle }$ 폴리 트리 수는 다음과 같습니다.

섬너의 추측

David Sumner의 이름을 딴 Sumner의 추측에 따르면 토너먼트는 폴리트리의 유니버설 그래프입니다. 즉${\displaystyle ,}$ ${\displaystyle \mathrm{2n}}$- ${\displaystyle \mathrm{2개}}$의$정점$이 $있는{\displaystyle \mathrm{}}$ 모든 토너먼트는 n개의$정점$을 하위 그래프로 $포함$하는 모든 폴리트리를 포함합니다.아직 해결되지 않은 상태로 남아 있지만, 충분히 큰 $값$인 n${displaystyle$ n$\}$^[8]에 대해 증명되었습니다.

적용들

폴리트리는 확률론적 ^[1]추론을 위한 그래픽 모델로 사용되었다.만약 베이지안 네트워크가 폴리 트리의 구조를 가지고 있다면, 믿음 전파는 그것에 ^[4][5]대해 효율적으로 추론을 수행하기 위해 사용될 수 있다.

벡터 공간에서 실수값 함수의 등고선 트리는 함수의 수준 집합을 설명하는 폴리 트리입니다.등고선 트리의 노드는 함수의 임계점을 통과하는 레벨 세트이며, 가장자리는 임계점 없이 연속된 레벨 세트 세트를 나타냅니다.가장자리의 방향은 해당하는 두 레벨 ^[9]세트의 함수 값 간 비교에 의해 결정됩니다.

「 」를 참조해 주세요.

• 그래프 이론 용어집

메모들

레퍼런스

• Carr, Hamish; Snoeyink, Jack; Axen, Ulrike (2000), "Computing contour trees in all dimensions", in Proc. 11th ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), pp. 918–926
• 를 클릭합니다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; 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.
• 를 클릭합니다Kühn, Daniela; Mycroft, Richard; Osthus, Deryk (2011), "A proof of Sumner's universal tournament conjecture for large tournaments", Proceedings of the London Mathematical Society, Third Series, 102 (4): 731–766, arXiv:1010.4430, doi:10.1112/plms/pdq035, MR 2793448.
• 를 클릭합니다Rebane, George; Pearl, Judea (1987), "The recovery of causal poly-trees from statistical data", in Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987 (PDF), pp. 222–228.
• 를 클릭합니다Ruskey, Frank (1989), "Transposition generation of alternating permutations", Order, 6 (3): 227–233, doi:10.1007/BF00563523, MR 1048093.
• 를 클릭합니다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.
• 를 클릭합니다Trotter, William T., Jr.; Moore, John I., Jr. (1977), "The dimension of planar posets", Journal of Combinatorial Theory, Series B, 22 (1): 54–67, doi:10.1016/0095-8956(77)90048-X.