Универсальный граф

Универсальный граф — это бесконечный граф, содержащий любой конечный (или не более чем счётный) граф в качестве порождённого подграфа. Универсальный граф этого типа первым построил Р. Радо[1][2] и этот граф теперь называется графом Радо или случайным графом. Более свежие работы[3][4] фокусируются на универсальных графах для семейства графов F. То есть бесконечный граф, принадлежащий F, содержащий все конечные графы семейства F. Например, графы Хэнсона являются универсальными в этом смысле для графов без i-клик.

Универсальный граф для семейства графов F может также пониматься как член последовательности конечных графов, которые содержат все графы из F. Например, любое конечное дерево является подграфом достаточно большого графа гиперкуба[5], так что можно сказать, что гиперкуб является универсальным графом для деревьев. Однако это не самый маленький такой граф — известно, что существует универсальный граф для деревьев с n вершинами, содержащий всего n вершин и O(n log n) рёбер, и этот граф оптимален[6]. Построение, основанное на теореме о планарном разбиении, может быть использовано, чтобы показать, что планарные графы с n вершинами имеет универсальные графы с O(n^3/2) рёбрами, и что планарные графы ограниченной степени имеют универсальные графы с O(n log n) рёбрами[7][8][9]. Гипотеза Самнера утверждает, что турниры являются универсальными для полидеревьев в том смысле, что любой турнир с 2n − 2 вершинами содержат любое полидерево с n вершинами в качестве поддерева[10].

Семейство графов F имеет универсальный граф полиномиальная размера, содержащий любой граф с n вершинами в качестве порождённого подграфа, тогда и только тогда, когда он имеет схему смежной разметки, в которой вершины могут быть помечены O(log n)-битными строками таким образом, что алгоритм может определить, смежны ли вершины, по меткам этих вершин. Если граф этого типа существует, вершины любого графа в F можно пометить метками соответствующих вершин универсального графа, и наоборот, если схема разметки существует, может быть построен универсальный граф, содержащий все возможные метки[11].

В старой математической терминологии фраза "универсальный граф" иногда использовался для полного графа.