Универсальный граф — это бесконечный граф, содержащий любой конечный (или не более чем счётный) граф в качестве порождённого подграфа. Универсальный граф этого типа первым построил Р. Радо и этот граф теперь называется графом Радо или случайным графом. Более свежие работы фокусируются на универсальных графах для семейства графов . То есть бесконечный граф, принадлежащий F, содержащий все конечные графы семейства . Например, графы Хэнсона являются универсальными в этом смысле для графов без -клик.
Универсальный граф для семейства графов может также пониматься как член последовательности конечных графов, которые содержат все графы из . Например, любое конечное дерево является подграфом достаточно большого графа гиперкуба, так что можно сказать, что гиперкуб является универсальным графом для деревьев. Однако это не самый маленький такой граф — известно, что существует универсальный граф для деревьев с вершинами, содержащий всего вершин и рёбер, и этот граф оптимален. Построение, основанное на теореме о планарном разбиении, может быть использовано, чтобы показать, что планарные графы с вершинами имеет универсальные графы с рёбрами, и что планарные графы ограниченной степени имеют универсальные графы с рёбрами. Гипотеза Самнера утверждает, что турниры являются универсальными для в том смысле, что любой турнир с вершинами содержат любое полидерево с вершинами в качестве поддереваSumner's Universal Tournament Conjecture , Douglas B. West, retrieved 2010-09-17..
Семейство графов имеет универсальный граф полиномиальная размера, содержащий любой граф с вершинами в качестве порождённого подграфа, тогда и только тогда, когда он имеет , в которой вершины могут быть помечены -битными строками таким образом, что алгоритм может определить, смежны ли вершины, по меткам этих вершин. Если граф этого типа существует, вершины любого графа в можно пометить метками соответствующих вершин универсального графа, и наоборот, если схема разметки существует, может быть построен универсальный граф, содержащий все возможные метки.
В старой математической терминологии фраза "универсальный граф" иногда использовался для полного графа.
Примечания
Литература
Ссылки The panarborial formula, "Theorem of the Day" concerning universal graphs for trees
Категория:Семейства графов Категория:Бесконечные графы