Универсальный граф
Универсальный граф — это бесконечный граф, содержащий любой конечный (или не более чем счётный) граф в качестве порождённого подграфа. Универсальный граф этого типа первым построил Р. Радо[1][2] и этот граф теперь называется графом Радо или случайным графом. Более свежие работы[3][4] фокусируются на универсальных графах для семейства графов F. То есть бесконечный граф, принадлежащий F, содержащий все конечные графы семейства F. Например, графы Хэнсона являются универсальными в этом смысле для графов без i-клик.
Универсальный граф для семейства графов F может также пониматься как член последовательности конечных графов, которые содержат все графы из F. Например, любое конечное дерево является подграфом достаточно большого графа гиперкуба[5], так что можно сказать, что гиперкуб является универсальным графом для деревьев. Однако это не самый маленький такой граф — известно, что существует универсальный граф для деревьев с n вершинами, содержащий всего n вершин и O(n log n) рёбер, и этот граф оптимален[6]. Построение, основанное на теореме о планарном разбиении, может быть использовано, чтобы показать, что планарные графы с n вершинами имеет универсальные графы с O(n3/2) рёбрами, и что планарные графы ограниченной степени имеют универсальные графы с O(n log n) рёбрами[7][8][9]. Гипотеза Самнера утверждает, что турниры являются универсальными для полидеревьев[англ.] в том смысле, что любой турнир с 2n − 2 вершинами содержат любое полидерево с n вершинами в качестве поддерева[10].
Семейство графов F имеет универсальный граф полиномиальная размера, содержащий любой граф с n вершинами в качестве порождённого подграфа, тогда и только тогда, когда он имеет схему смежной разметки[англ.], в которой вершины могут быть помечены O(log n)-битными строками таким образом, что алгоритм может определить, смежны ли вершины, по меткам этих вершин. Если граф этого типа существует, вершины любого графа в F можно пометить метками соответствующих вершин универсального графа, и наоборот, если схема разметки существует, может быть построен универсальный граф, содержащий все возможные метки[11].
В старой математической терминологии фраза "универсальный граф" иногда использовался для полного графа.
Примечания[править | править код]
- ↑ Rado, 1964, с. 331–340.
- ↑ Rado, 1967, с. 83–85.
- ↑ Goldstern, Kojman, 1996, с. 319–326.
- ↑ Cherlin, Shelah, Shi, 1999, с. 454–491.
- ↑ Wu, 1985, с. 238–249.
- ↑ Chung, Graham, 1983, с. 203–211.
- ↑ Babai, Chung, Erdős, Graham, Spencer, 1982, с. 21–26.
- ↑ Bhatt, Chung, Leighton, Rosenberg, 1989, с. 145.
- ↑ Chung, 1990, с. 17–34.
- ↑ Sumner's Universal Tournament Conjecture Архивная копия от 27 февраля 2014 на Wayback Machine, Douglas B. West, retrieved 2010-09-17.
- ↑ Kannan, Naor, Rudich, 1992, с. 596–603.
Литература[править | править код]
- F. R. K. Chung, R. L. Graham. On universal graphs for spanning trees // Journal of the London Mathematical Society. — 1983. — Т. 27, вып. 2. — doi:10.1112/jlms/s2-27.2.203.
- R. Rado. Universal graphs and universal functions // Acta Arithmetica. — 1964. — Т. 9.
- R. Rado. Universal graphs // A Seminar in Graph Theory. — Holt, Rinehart, and Winston, 1967.
- Martin Goldstern, Menachem Kojman. Universal arrow-free graphs // Acta Mathematica Hungarica. — 1996. — Т. 1973, вып. 4. — doi:10.1007/BF00052907. — arXiv:math.LO/9409206.
- Greg Cherlin, Saharon Shelah, Niandong Shi. Universal graphs with forbidden subgraphs and algebraic closure // Advances in Applied Mathematics. — 1999. — Т. 22, вып. 4. — doi:10.1006/aama.1998.0641. — arXiv:math.LO/9809202.
- A. Y. Wu. Embedding of tree networks into hypercubes // Journal of Parallel and Distributed Computing. — 1985. — Т. 2, вып. 3. — doi:10.1016/0743-7315(85)90026-7.
- L. Babai, F. R. K. Chung, P. Erdős, R. L. Graham, J. H. Spencer. On graphs which contain all sparse graphs // Theory and practice of combinatorics: a collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday / Alexander Rosa, Gert Sabidussi, Jean Turgeon. — 1982. — Т. 12. — (Annals of Discrete Mathematics).
- Sandeep N. Bhatt, Fan R. K. Chung, F. T. Leighton, Arnold L. Rosenberg. Universal graphs for bounded-degree trees and planar graphs // SIAM Journal on Discrete Mathematics. — 1989. — Т. 2, вып. 2. — doi:10.1137/0402014.
- Fan R. K. Chung. Separator theorems and their applications // Paths, Flows, and VLSI-Layout / Bernhard Korte, László Lovász, Hans Jürgen Prömel, Alexander Schrijver. — Springer-Verlag, 1990. — Т. 9. — (Algorithms and Combinatorics). — ISBN 978-0-387-52685-0.
- Sampath Kannan, Moni Naor, Steven Rudich. Implicit representation of graphs // SIAM Journal on Discrete Mathematics. — 1992. — Т. 5, вып. 4. — doi:10.1137/0405049.
Ссылки[править | править код]
- The panarborial formula, "Theorem of the Day" concerning universal graphs for trees
 | Для улучшения этой статьи желательно:
|