Универсальный граф — это бесконечный граф, содержащий любой конечный (или не более чем счётный) граф в качестве порождённого подграфа. Универсальный граф этого типа первым построил Р. Радо[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].
В старой математической терминологии фраза "универсальный граф" иногда использовался для полного графа.
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.
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.
Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.
