K트리

K-tree
평면 3-트리의 예인 Goldner-Harary 그래프.

그래프 이론에서, k-트리는 (k + 1)-vertex 완전 그래프에서 시작하여 추가된 각 정점 v가 정확히 k개의 인접 U를 가지도록 반복적으로 정점을 추가함으로써 형성되는 무방향 그래프이다.[1][2]

특성화

k-트리는 트리 너비가 k인 최대 그래프입니다("maximal"은 트리 [2]너비를 늘리지 않고는 더 이상 에지를 추가할 수 없다는 의미).또한 최대 클리크가 모두 같은 크기 k + 1이고 최소 클리크 구분자가 모두 같은 크기 [1]k인 화음 그래프이기도 하다.

관련 그래프 클래스

1-수직은 뿌리 없는 나무와 같다. 2-수직은 최대 급수-수직 [3]그래프이며 최대 외평면 그래프도 포함한다.평면 3-트리는 아폴로니아 [4]네트워크라고도 합니다.

최대 k개의 트리 폭을 갖는 그래프는 정확히 k-트리의 하위 그래프이며, 이러한 이유로 부분 [2]k-트리라고 불린다.

k차원 적층 폴리톱의 모서리와 정점으로 형성된 그래프는 단순함에서 시작하여 단순함을 폴리톱의 면에 반복적으로 접착함으로써 형성되는 k-tree이다.[5]이 접착 프로세스는 정점을 clique에 [6]추가하여 k-tree 구성을 모방합니다.k-트리는 3개의 (k + 1)-vertex 클리어가 공통으로 [7]k개의 정점을 가지지 않는 경우에만 적층 폴리토프의 그래프입니다.

레퍼런스

  1. ^ a b 를 클릭합니다Patil, H. P. (1986), "On the structure of k-trees", Journal of Combinatorics, Information and System Sciences, 11 (2–4): 57–64, MR 0966069.
  2. ^ a b c 를 클릭합니다Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2008), "Structural Properties of Sparse Graphs" (PDF), in Grötschel, Martin; Katona, Gyula O. H. (eds.), Building Bridges: between Mathematics and Computer Science, Bolyai Society Mathematical Studies, vol. 19, Springer-Verlag, p. 390, ISBN 978-3-540-85218-6.
  3. ^ 를 클릭합니다Hwang, Frank; Richards, Dana; Winter, Pawel (1992), The Steiner Tree Problem, Annals of Discrete Mathematics (North-Holland Mathematics Studies), vol. 53, Elsevier, p. 177, ISBN 978-0-444-89098-6.
  4. ^ 랜덤 아폴로니아 네트워크 구조의 거리 2011-07-21 Wayback Machine, Olivier Bodini, Alexis Darasse 및 Michéle Soria가 FPSAC 2008에서 강연한 슬라이드(2011-03-06에 액세스)
  5. ^ 특히 페이지 420을 참조하십시오Koch, Etan; Perles, Micha A. (1976), "Covering efficiency of trees and k-trees", Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976), Utilitas Math., Winnipeg, Man., pp. 391–420. Congressus Numerantium, No. XVII, MR 0457265.
  6. ^ 를 클릭합니다Below, Alexander; De Loera, Jesús A.; Richter-Gebert, Jürgen. "The Complexity of Finding Small Triangulations of Convex 3-Polytopes". arXiv:math/0012177..
  7. ^ Kleinschmidt, Peter (1 December 1976). "Eine graphentheoretische Kennzeichnung der Stapelpolytope". Archiv der Mathematik. 27 (1): 663–667. doi:10.1007/BF01224736.