아르보렌스(그래프 이론)

Arborescence (graph theory)

그래프 이론에서, 수목은 정점 u(루트라고 함)와 다른 정점 v에 [1]대해 정확히 하나의 유향 경로가 있는 유향 그래프이다. 따라서 수목은 여기서 무향 [2][3]그래프로 이해되는 루트 트리의 유향 그래프 형태이다.

마찬가지로, 수목은 모든 에지가 루트에서 멀리 떨어져 있는 방향성 루트 트리입니다. 그 밖에도 여러 가지 동등한 특성화가 존재합니다.[4][5]모든 수목은 DAG(Directed Acyclic Graph)이지만 모든 수목은 수목은 아닙니다.

등가적으로 아르보렌스는 루트로부터 다른 정점까지의 경로가 고유한 [2]루트 디그래프로 정의될 수 있다.

정의.

수목이라는 용어는 [6]프랑스어에서 유래했다.몇몇 작가들은 [7]철자가 번거롭다는 이유로 그것에 반대한다.그래프 이론에는 유도 루트[3][7] 트리 아웃 아보렌스,[8] 아웃 트리,[9] 그리고 심지어 [9]같은 개념을 나타내기 위해 사용되는 분기를 포함하여 수목의 동의어가 많이 있다.루트 트리 자체는 일부 저자에 의해 방향 [10][11][12]그래프로 정의되어 있습니다.

추가 정의

또, 일부의 저자는, 수목 형성을, 소정의 [12][13]디그래프의 스패닝 방향 트리로 정의한다.동의어, 특히 [13]분기에 대해서도 같은 말을 할 수 있습니다.다른 저자들은 나뭇가지를 사용하여 수목현상의 포레스트를 나타내는데, 후자의 개념은 이 [14][15]기사의 첫머리에 더 넓은 의미로 정의되어 있지만, 스패닝 플레이버의 두 가지 개념을 모두 가진 변화도 [12]볼 수 있다.

또한 나무 원호의 모든 호를 반전시켜 유용한 개념을 정의할 수도 있습니다. 즉, 모든 호가 나무 원호에서 멀어지는 것이 아니라 루트를 가리키게 합니다.이러한 디그래프는 또한 인트리[16](in-tree) 또는 안티아르보렌스(anti-arboresence[17]) 등과 같은 다양한 용어로 지정된다.W. T. Tutte는 [일부 루트]에서 분기하는 수목과 [일부 루트][18]로 수렴하는 수목이라는 문구를 사용하여 두 경우를 구분합니다.

노드가 n개인 루트 트리(또는 수목)의 수는 다음 순서로 제공됩니다.

0, 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 476, 12486, ...(OEIS의 시퀀스 A000081).

「 」를 참조해 주세요.

레퍼런스

  1. ^ "Tree". NetworkX 2.6.2 documentation. Retrieved 2021-12-10. arborescence - A directed tree with each node having, at most, one parent. So the maximum in-degree is equal to 1.
  2. ^ a b Gordon, Gary (1989). "A greedoid polynomial which distinguishes rooted arborescences". Proceedings of the American Mathematical Society. 107 (2): 287. doi:10.1090/S0002-9939-1989-0967486-0.
  3. ^ a b Stanley Gill Williamson (1985). Combinatorics for Computer Science. Courier Dover Publications. p. 288. ISBN 978-0-486-42076-9.
  4. ^ Jean-Claude Fournier (2013). Graphs Theory and Applications: With Exercises and Problems. John Wiley & Sons. pp. 94–95. ISBN 978-1-84821-070-7.
  5. ^ Jean Gallier (2011). Discrete Mathematics. Springer Science & Business Media. pp. 193–194. ISBN 978-1-4419-8046-5.
  6. ^ Per Hage and Frank Harary (1996). Island Networks: Communication, Kinship, and Classification Structures in Oceania. Cambridge University Press. p. 43. ISBN 978-0-521-55232-5.
  7. ^ a b Mehran Mesbahi; Magnus Egerstedt (2010). Graph Theoretic Methods in Multiagent Networks. Princeton University Press. p. 38. ISBN 1-4008-3535-6.
  8. ^ Ding-Zhu Du; Ker-I Ko; Xiaodong Hu (2011). Design and Analysis of Approximation Algorithms. Springer Science & Business Media. p. 108. ISBN 978-1-4614-1701-9.
  9. ^ a b Jonathan L. Gross; Jay Yellen; Ping Zhang (2013). Handbook of Graph Theory, Second Edition. CRC Press. p. 116. ISBN 978-1-4398-8018-0.
  10. ^ David Makinson (2012). Sets, Logic and Maths for Computing. Springer Science & Business Media. pp. 167–168. ISBN 978-1-4471-2499-3.
  11. ^ Kenneth Rosen (2011). Discrete Mathematics and Its Applications, 7th edition. McGraw-Hill Science. p. 747. ISBN 978-0-07-338309-5.
  12. ^ a b c Alexander Schrijver (2003). Combinatorial Optimization: Polyhedra and Efficiency. Springer. p. 34. ISBN 3-540-44389-4.
  13. ^ a b Jørgen Bang-Jensen; Gregory Z. Gutin (2008). Digraphs: Theory, Algorithms and Applications. Springer. p. 339. ISBN 978-1-84800-998-1.
  14. ^ James Evans (1992). Optimization Algorithms for Networks and Graphs, Second Edition. CRC Press. p. 59. ISBN 978-0-8247-8602-1.
  15. ^ Bernhard Korte; Jens Vygen (2012). Combinatorial Optimization: Theory and Algorithms (5th ed.). Springer Science & Business Media. p. 18. ISBN 978-3-642-24488-9.
  16. ^ Kurt Mehlhorn; Peter Sanders (2008). Algorithms and Data Structures: The Basic Toolbox (PDF). Springer Science & Business Media. p. 52. ISBN 978-3-540-77978-0.
  17. ^ Bernhard Korte; Jens Vygen (2012). Combinatorial Optimization: Theory and Algorithms (5th ed.). Springer Science & Business Media. p. 28. ISBN 978-3-642-24488-9.
  18. ^ Tutte, W.T. (2001), Graph Theory, Cambridge University Press, pp. 126–127, ISBN 978-0-521-79489-3

외부 링크


Stub icon

이 콤비네이터 관련 기사는 스텁입니다.위키피디아를 확장함으로써 위키피디아를 도울 수 있습니다.