This is a good article. Click here for more information.

할린 그래프

Halin graph
A Halin graph with 21 vertices
할린 그래프

그래프 이론에서, 할린 그래프는 나무의 잎을 주기에 연결함으로써 만들어진 평면 그래프의 한 종류이다.트리는 적어도 4개의 정점을 가지고 있어야 하며, 이들 중 어느 것도 정확히 2개의 인접점을 가지고 있지 않습니다.또한 평면에 그 가장자리가 교차하지 않도록 그려져야 합니다(이것을 평면 매립이라고 부릅니다).이 매립에서는 사이클이 잎을 시계 방향으로 연결합니다.따라서 사이클은 [1]트리가 내부에 있는 할린 그래프의 바깥쪽 면을 형성합니다.

할린 그래프는 [2]1971년에 그것들을 연구한 독일 수학자 루돌프 할린의 이름을 따서 붙여졌다.각 정점이 정확히 세 개의 모서리에 닿는 입방체 할린 그래프는 커크먼에 의해 [3]한 세기 전에 이미 연구되었다.할린 그래프는 모든 할린 그래프가 볼록한 다면체의 정점과 모서리를 형성하는 데 사용될 수 있다는 것을 의미하는 다면체이며, 그것들로부터 형성된 다면체는 지붕 없는 다면체 또는 돔이라고 불려왔다.

모든 할린 그래프는 모든 정점을 통과하는 해밀턴 사이클과 정점 수까지 거의 모든 길이의 사이클을 가집니다.할린 그래프는 선형 시간으로 인식할 수 있습니다.할린 그래프는 트리 폭이 낮기 때문에 해밀턴 사이클을 찾는 것과 같은 다른 종류의 평면 그래프에서 어려운 많은 계산 문제들도 할린 그래프에서 빠르게 해결할 수 있다.

The graph of a triangular prism
6개의 버텍스 트리에서 할린 그래프로 구성된 삼각 프리즘

예

Wheel graphs with four to nine vertices
휠 그래프

별은 정확히 하나의 꼭지점을 가진 나무이다.할린 그래프 구조를 별에 적용하면 피라미드 [4]그래프인 휠 그래프가 생성됩니다.삼각 프리즘의 그래프도 할린 그래프입니다.사각형 면 중 하나가 외부 순환이 되도록 그릴 수 있으며, 나머지 가장자리는 4개의 잎, 2개의 내부 정점,[5] 5개의 가장자리로 이루어진 트리를 형성합니다.

프루히트 그래프(Frucht graph)[6]는 간단한 그래프 자기동형이 없는 5개의 가장 작은 입방 그래프 중 하나이며 할린 [7]그래프이기도 합니다.

특성.

모든 할린 그래프는 3-연결되어 있습니다. 즉, 이 그래프는 두 개의 정점을 삭제하고 나머지 정점의 연결을 끊을 수 없습니다.이 그래프는 에지-최소 3-연결로, 에지 중 하나가 제거되면 나머지 그래프는 더 이상 [1]3-연결되지 않습니다.슈타이니츠의 정리에 따르면, 3연결 평면 그래프로서 볼록 다면체의 정점과 모서리의 집합으로 표현될 수 있다. 즉, 다면체 그래프이다.그래프를 실현하는 다면체는 모든 나무 잎을 포함하는 면이 수평이 되도록 선택할 수 있으며 다른 모든 면이 그 위에 있고 [8]기울기가 동일하도록 선택할 수 있습니다.모든 다면체 그래프와 마찬가지로 할린 그래프는 고유한 평면 매립을 가지며, 그 면 중 어떤 면을 외부 [1]면으로 할지 선택할 수 있다.

모든 할린 그래프는 해밀턴 그래프이며 그래프의 모든 가장자리는 해밀턴 사이클에 속합니다.게다가,[9] 모든 할린 그래프는 정점이 삭제된 후에도 해밀턴식으로 남는다.2도의 정점이 없는 모든 나무에는 동일한 부모를 공유하는 두 잎이 포함되므로 모든 할린 그래프에는 삼각형이 포함됩니다.특히 할린 그래프는 삼각형이 없는 그래프나 초당 [10]그래프가 될 수 없다.

Halin graph with one 16-vertex face, two 10-vertex faces, and all other faces having 3 to 5 vertices
8 사이클이 없는 할린 그래프.유사한 구조를 사용하면 단일 짝수 사이클 길이를 [11]피할 수 있습니다.

보다 강하게는 모든 할린 그래프는 단일 짝수 길이를 제외하고 3에서 n까지의 모든 길이의 주기를 갖는다는 점에서 거의 범순환형이다.또한 모든 할린 그래프는 단일 가장자리가 수축된 경우 거의 범순환 상태로 유지되며, 내부 정점이 3도인 모든 할린 그래프는 [12]범순환형이다.

최대도 δ(G)가 4보다 큰 할린 그래프 G의 입사 색수는 δ(G) + [13]1이다. 이는 모든 쌍(v,e)을 색칠하는 데 필요한 색수이며, 여기서 v는 그래프의 정점이고 e는 색칠에 대한 특정 제약을 따르는 가장자리이다.정점을 공유하거나 모서리를 공유하는 쌍은 동일한 색상을 가질 수 없습니다.또한 쌍(v,e)은 e의 다른 끝점을 사용하는 다른 쌍과 동일한 색상을 가질 수 없습니다.δ(G) = 3 또는 4인 할린 그래프의 경우, 입사 색수는 각각 [14]5 또는 6만큼 클 수 있다.

계산의 복잡성

주어진 n-vertex 그래프가 할린 그래프인지 여부는 그래프의 평면 매립(있는 경우)을 찾은 후 적어도 n/2 + 1개의 정점이 있는 면이 있는지 여부를 테스트하여 선형 시간에 테스트할 수 있다.이 경우, 이러한 면은 최대 4개까지 존재할 수 있으며, 나머지 그래프가 이 면의 정점을 잎으로 하여 트리를 형성하는지 여부를 선형 시간으로 확인할 수 있다.한편, 그러한 면이 존재하지 않는 경우는, 그래프는 [15]할린이 아닙니다.또는 n개의 정점과 m개의 모서리를 가진 그래프는 평면적이고 3개의 연결로 되어 있으며 그래프의 회로 순위 m - n + 1과 동일한 면의 경우만 Halin이 되며, 이 모든 것을 [16]선형 시간으로 확인할 수 있다.선형 시간에 할린 그래프를 인식하는 다른 방법으로는 Courcelle의 정리 또는 그래프 재작성에 기초한 방법을 들 수 있다. 두 방법 [17]모두 그래프의 평면 매립을 아는 데 의존하지 않는다.

모든 할린 그래프의 트리 폭은 = 3입니다.[18]따라서, 최대 독립 집합을 찾는 것과 같은 임의의 평면 그래프에 대해 NP-완전인 많은 그래프 최적화 문제는 동적[19] 프로그래밍이나 쿠셀의 정리를 사용하여 할린 그래프에서 선형 시간 내에, 또는 경우에 따라 직접 [17]알고리즘에 의해 해결될 수 있다.그러나 주어진 그래프의 가장 큰 할린 서브그래프를 찾거나, 주어진 그래프의 모든 정점을 포함하는 할린 서브그래프가 존재하는지, 또는 주어진 그래프가 더 큰 할린 [20]그래프의 서브그래프인지 테스트하는 것은 NP-완전이다.

역사

1971년 Halin은 Halin 그래프를 최소 3개의 버텍스 연결 그래프의 클래스로 도입했다. 그래프의 모든 에지에 대해 해당 에지를 제거하면 [2]그래프의 연결성이 감소한다.이러한 그래프는 임의 평면 그래프에 대해 계산적으로 불가능한 많은 알고리즘 문제를 [9][16]효율적으로 해결할 수 있다는 발견과 함께 중요성을 얻었다.이 사실은 나중에 낮은 나무 너비와 낮은 나무 [18][19]너비의 그래프에서 이러한 문제에 대한 효율적인 해결책을 제공하는 쿠셀의 정리 같은 알고리즘 메타 이론의 결과로 설명되었습니다.

이러한 그래프에 대한 Halin의 연구 이전에, 입방형(또는 3-정규형) Halin 그래프에 관한 그래프 열거 문제는 1856년에 Thomas[3] Kirkman에 의해 그리고 1965년에 Hans Rademacher에 의해 연구되었다.Rademacher는 이 그래프를 다면체라고 부릅니다.그는 그것들을 f개의 면이 있는 입방체 다면체 그래프로 정의한다. f개의 면 중 하나는 f - 1개의 [21]면을 가진다.이 정의에 맞는 그래프가 바로 입방 할린 [22]그래프입니다.

Halin 그래프와 4-vertex 연결 평면 그래프 모두에 해밀턴 주기가 포함되어 있다는 사실에서 영감을 얻어, Lovasz & Plummer(1974)는 모든 4-vertex 연결 평면 그래프에 스패닝 할린 하위 그래프가 포함되어 있다고 추측했다. 여기서 "스패닝"은 하위 그래프가 더 큰 그래프의 모든 정점을 포함한다는 것을 의미한다.로바시즈-플루머 추측은 2015년까지 공개되었으며, 그 때 무한히 많은 반례 표본에 대한 구성이 [23]발표되었다.

할린 그래프는 때때로 주름진 나무[11] 또는 지붕이 없는 [9]다면체라고도 불립니다.그러나 이 이름들은 애매하다.일부 저자는 잎을 주기에 연결함으로써 나무로 형성된 평면 그래프를 참조하기 위해 "스커티드 트리"라는 이름을 사용하지만 트리의 내부 정점이 [24]3도 이상을 가질 필요는 없다.그리고 "기반 다면체"와 마찬가지로 "지붕 없는 다면체" 이름도 입방체 할린 [22]그래프를 나타낼 수 있습니다.그래프가 할린 그래프인 볼록 다면체는 [25]돔이라고도 불린다.

레퍼런스

  1. ^ a b c 수학 백과사전, 제1권 부록, 1988, ISBN0-7923-4709-9, 페이지 281, 기사 "할린 그래프" 및 참조.
  2. ^ a b 를 클릭합니다Halin, R. (1971), "Studies on minimally n-connected graphs", Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), London: Academic Press, pp. 129–136, MR 0278980.
  3. ^ a b 를 클릭합니다Kirkman, Th. P. (1856), "On the enumeration of x-edra having triedral summits and an (x − 1)-gonal base", Philosophical Transactions of the Royal Society of London, 146: 399–411, doi:10.1098/rstl.1856.0018, JSTOR 108592.
  4. ^ Cornujols, Naddef & Pulleyblank(1983) : "T가 별이라면, 즉 단일 노드 v가 n개의 다른 노드에 결합되어 있다면, H는 바퀴라고 불리며 할린 그래프의 가장 단순한 유형이다."
  5. ^ Syswo & Proskurowski(1983), Prop. 4.3, 페이지 254를 참조해 주십시오.이것은 삼각 프리즘을 할린 그래프로서 실현의 외부 사이클이 될 수 있는 정확히 3개의 사이클을 가지는 고유 그래프로서 식별합니다.
  6. ^ Bussemaker, F. C.; Cobeljic, S.; Cvetkovic, D. M.; Seidel, J. J. (1976), Computer investigation of cubic graphs, EUT report, vol. 76-WSK-01, Dept. of Mathematics and Computing Science, Eindhoven University of Technology
  7. ^ Weisstein, Eric W., "Halin Graph", MathWorld
  8. ^ Aichholzer, Oswin; Cheng, Howard; Devadoss, Satyan L.; Hackl, Thomas; Huber, Stefan; Li, Brian; Risteski, Andrej (2012), "What makes a tree a straight skeleton?" (PDF), Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG'12)
  9. ^ a b c 를 클릭합니다Cornuéjols, G.; Naddef, D.; Pulleyblank, W. R. (1983), "Halin graphs and the travelling salesman problem", Mathematical Programming, 26 (3): 287–294, doi:10.1007/BF02591867, S2CID 26278382.
  10. ^ 왕, Weifan, 부, 위에화;Montassier, Mickaël, Raspaud, 앙드레(2012년)에서,"등뼈에 그래프 채색"면 필기장이 Combinatorial최적화의, 23(1):79–93, doi:10.1007/s10878-010-9342-6, MR2875236, S2CID 26975523: 말하였다.`G는3-cycle 내적인 꼭지점은 두 외부 vertices로 구성되어 G가 아니다 bipartit 정리 10의 증거를 참조하십시오.egraph."
  11. ^ a b Malkevitch, Joseph (1978), "Cycle lengths in polytopal graphs", Theory and Applications of Graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976), Lecture Notes in Mathematics, Berlin: Springer, 642: 364–370, doi:10.1007/BFb0070393, ISBN 978-3-540-08666-6, MR 0491287
  12. ^ 를 클릭합니다Skowrońska, Mirosława (1985), "The pancyclicity of Halin graphs and their exterior contractions", in Alspach, Brian R.; Godsil, Christopher D. (eds.), Cycles in Graphs, Annals of Discrete Mathematics, vol. 27, Elsevier Science Publishers B.V., pp. 179–194.
  13. ^ 를 클릭합니다Wang, Shu-Dong; Chen, Dong-Ling; Pang, Shan-Chen (2002), "The incidence coloring number of Halin graphs and outerplanar graphs", Discrete Mathematics, 256 (1–2): 397–405, doi:10.1016/S0012-365X(01)00302-8, MR 1927561.
  14. ^ 를 클릭합니다Shiu, W. C.; Sun, P. K. (2008), "Invalid proofs on incidence coloring", Discrete Mathematics, 308 (24): 6575–6580, doi:10.1016/j.disc.2007.11.030, MR 2466963.
  15. ^ 를 클릭합니다Fomin, Fedor V.; Thilikos, Dimitrios M. (2006), "A 3-approximation for the pathwidth of Halin graphs", Journal of Discrete Algorithms, 4 (4): 499–510, doi:10.1016/j.jda.2005.06.004, MR 2577677.
  16. ^ a b 를 클릭합니다Sysło, Maciej M.; Proskurowski, Andrzej (1983), "On Halin graphs", Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981, Lecture Notes in Mathematics, vol. 1018, Springer-Verlag, pp. 248–256, doi:10.1007/BFb0071635.
  17. ^ a b 를 클릭합니다Eppstein, David (2016), "Simple recognition of Halin graphs and their generalizations", Journal of Graph Algorithms and Applications, 20 (2): 323–346, arXiv:1502.05334, doi:10.7155/jgaa.00395, S2CID 9525753.
  18. ^ a b 를 클릭합니다Bodlaender, Hans (1988), Planar graphs with bounded treewidth (PDF), Technical Report RUU-CS-88-14, Department of Computer Science, Utrecht University, archived from the original (PDF) on 2004-07-28.
  19. ^ a b 를 클릭합니다Bodlaender, Hans (1988), "Dynamic programming on graphs with bounded treewidth", Proceedings of the 15th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 317, Springer-Verlag, pp. 105–118, doi:10.1007/3-540-19488-6_110, ISBN 978-3540194880.
  20. ^ 를 클릭합니다Horton, S. B.; Parker, R. Gary (1995), "On Halin subgraphs and supergraphs", Discrete Applied Mathematics, 56 (1): 19–35, doi:10.1016/0166-218X(93)E0131-H, MR 1311302.
  21. ^ 를 클릭합니다Rademacher, Hans (1965), "On the number of certain types of polyhedra", Illinois Journal of Mathematics, 9 (3): 361–380, doi:10.1215/ijm/1256068140, MR 0179682.
  22. ^ a b 를 클릭합니다Lovász, L.; Plummer, M. D. (1974), "On a family of planar bicritical graphs", Combinatorics (Proc. British Combinatorial Conf., Univ. Coll. Wales, Aberystwyth, 1973), London: Cambridge Univ. Press, pp. 103–107. London Math. Soc. Lecture Note Ser., No. 13, MR 0351915.
  23. ^ 를 클릭합니다Chen, Guantao; Enomoto, Hikoe; Ozeki, Kenta; Tsuchiya, Shoichi (2015), "Plane triangulations without a spanning Halin subgraph: counterexamples to the Lovász-Plummer conjecture on Halin graphs", SIAM Journal on Discrete Mathematics, 29 (3): 1423–1426, doi:10.1137/140971610, MR 3376776.
  24. ^ Skowrońska, M.; Sysło, M. M. (1987), "Hamiltonian cycles in skirted trees", Proceedings of the International Conference on Combinatorial Analysis and its Applications (Pokrzywna, 1985), Zastos. Mat., 19 (3–4): 599–610 (1988), MR 0951375
  25. ^ 를 클릭합니다Demaine, Erik D.; Demaine, Martin L.; Uehara, Ryuhei (2013), "Zipper unfolding of domes and prismoids", Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013), Waterloo, Ontario, Canada, August 8–10, 2013, pp. 43–48.

외부 링크