범용 그래프
Universal graph수학에서 범용 그래프는 유도 하위 그래프로서 모든 유한(또는 최대 카운트) 그래프를 포함하는 무한 그래프다.이런 유형의 보편적 그래프는 처음에 리차드 라도에[1][2] 의해 만들어졌고 현재는 라도 그래프 또는 랜덤 그래프라고 불린다.보다 최근의 연구는[3] 그래프 계열 F: 즉 F에 모든 유한한 그래프를 포함하는 F에 속하는 무한 그래프에 대한 범용 그래프에 초점을 맞추고 있다.예를 들어, 헨슨 그래프는 아이 클라이크 없는 그래프에 대해 이런 의미에서 보편적이다.
그래프의 F 계열에 대한 범용 그래프는 F의 모든 그래프를 포함하는 일련의 유한한 그래프의 구성원을 가리킬 수도 있다. 예를 들어, 모든 유한 트리는 충분히 큰 하이퍼큐브[5] 그래프의 하위 그래프여서 하이퍼큐브는 나무의 범용 그래프라고 할 수 있다.그러나 가장 작은 그래프는 아니다. 정점과 O(n log n) 가장자리만 있는 n-vertex 트리에 대한 범용 그래프가 있으며 이것이 최적의 그래프라고 알려져 있다.[6]평면 분리막 정리에 기초한 구성은 n-vertex 평면 그래프가 O(n3/2) 가장자리를 가진 범용 그래프를 가지고 있고, 경계도 평면 그래프는 O(n log n) 가장자리를 가진 범용 그래프를 가지고 있다는 것을 보여주는 데 사용될 수 있다.[7][8][9]정점이 없는1+o(1) 평면 그래프의 범용 그래프를 구성하는 것도 가능하다.[10]섬너의 추측은 2n - 2 정점을 가진 모든 토너먼트에는 정점을 가진 모든 폴리 트리가 서브그래프로 포함되어 있다는 점에서 폴리트리의 경우 토너먼트가 보편적이라고 말한다.[11]
그래프의 패밀리 F는 유도 하위그래프로써 모든 n-vertex 그래프를 포함하는 다항식 크기의 범용 그래프를 가지고 있는데, 이는 알고리즘이 두 정점이 그들의 라벨을 검사하여 인접하는지를 판단할 수 있는 O(log n) 비트 스트링으로 정점을 표시할 수 있는 인접 라벨링 체계를 가지고 있는 경우에만 해당된다.예를 들어, 이러한 유형의 범용 그래프가 존재하는 경우, F의 그래프의 정점은 범용 그래프의 해당 정점의 정점으로 표시될 수 있으며, 반대로 라벨링 방식이 존재하는 경우 가능한 모든 라벨에 대한 정점을 갖는 범용 그래프를 구성할 수 있다.[12]
이전의 수학 용어에서는, 완전한 그래프를 나타내기 위해 "범용 그래프"라는 문구가 사용되기도 했다.
보편적 그래프의 개념은 평균적인 보상 게임을 해결하기 위해 적용되고 이용되어 왔다.[13]
참조
- ^ Rado, R. (1964). "Universal graphs and universal functions". Acta Arithmetica. 9 (4): 331–340. doi:10.4064/aa-9-4-331-340. MR 0172268.
- ^ Rado, R. (1967). "Universal graphs". A Seminar in Graph Theory. Holt, Rinehart, and Winston. pp. 83–85. MR 0214507.
- ^ Goldstern, Martin; Kojman, Menachem (1996). "Universal arrow-free graphs". Acta Mathematica Hungarica. 1973 (4): 319–326. arXiv:math.LO/9409206. doi:10.1007/BF00052907. MR 1428038.
- ^ Cherlin, Greg; Shelah, Saharon; Shi, Niandong (1999). "Universal graphs with forbidden subgraphs and algebraic closure". Advances in Applied Mathematics. 22 (4): 454–491. arXiv:math.LO/9809202. doi:10.1006/aama.1998.0641. MR 1683298. S2CID 17529604.
- ^ Wu, A. Y. (1985). "Embedding of tree networks into hypercubes". Journal of Parallel and Distributed Computing. 2 (3): 238–249. doi:10.1016/0743-7315(85)90026-7.
- ^ Chung, F. R. K.; Graham, R. L. (1983). "On universal graphs for spanning trees" (PDF). Journal of the London Mathematical Society. 27 (2): 203–211. CiteSeerX 10.1.1.108.3415. doi:10.1112/jlms/s2-27.2.203. MR 0692525..
- ^ Babai, L.; Chung, F. R. K.; Erdős, P.; Graham, R. L.; Spencer, J. H. (1982). "On graphs which contain all sparse graphs". In Rosa, Alexander; Sabidussi, Gert; Turgeon, Jean (eds.). Theory and practice of combinatorics: a collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday (PDF). Annals of Discrete Mathematics. Vol. 12. pp. 21–26. MR 0806964.
- ^ Bhatt, Sandeep N.; Chung, Fan R. K.; Leighton, F. T.; Rosenberg, Arnold L. (1989). "Universal graphs for bounded-degree trees and planar graphs". SIAM Journal on Discrete Mathematics. 2 (2): 145–155. doi:10.1137/0402014. MR 0990447.
- ^ Chung, Fan R. K. (1990). "Separator theorems and their applications". In Korte, Bernhard; Lovász, László; Prömel, Hans Jürgen; et al. (eds.). Paths, Flows, and VLSI-Layout. Algorithms and Combinatorics. Vol. 9. Springer-Verlag. pp. 17–34. ISBN 978-0-387-52685-0. MR 1083375.
- ^ Dujmović, Vida; Esperet, Louis; Joret, Gwenaël; Gavoille, Cyril; Micek, Piotr; Morin, Pat (2021), "Adjacency Labelling for Planar Graphs (And Beyond)", Journal of the ACM, 68 (6): 1–33, arXiv:2003.04280, doi:10.1145/3477542
- ^ 섬너의 유니버설 토너먼트 추측, 더글라스 B.웨스트, 2010-09-17을 회수했다.
- ^ Kannan, Sampath; Naor, Moni; Rudich, Steven (1992), "Implicit representation of graphs", SIAM Journal on Discrete Mathematics, 5 (4): 596–603, doi:10.1137/0405049, MR 1186827.
- ^ Czerwiński, Wojciech; Daviaud, Laure; Fijalkow, Nathanaël; Jurdziński, Marcin; Lazić, Ranko; Parys, Paweł (2018-07-27). "Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games". Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 2333–2349. arXiv:1807.10546. doi:10.1137/1.9781611975482.142. ISBN 978-1-61197-548-2. S2CID 51865783.
