Універса́льний граф — це нескінченний граф, що містить будь-який скінченний (або не більше ніж зліченний) граф як породжений підграф. Універсальний граф цього типу першим побудував Р. Радо і цей граф тепер називають графом Радо або випадковим графом. Свіжіші роботи фокусуються на універсальних графах для сімейства графів . Тобто нескінченний граф, що належить , який містить усі скінченні графи сімейства . Наприклад, графи Генсона є універсальними в цьому сенсі для графів без -клік.
Універсальний граф для сімейства графів можна також розуміти як член послідовності скінченних графів, які містять усі графи з . Наприклад, будь-яке скінченне дерево є підграфом достатньо великого графа гіперкуба, так що можна сказати, що гіперкуб є універсальним графом для дерев. Однак це не найменший такий граф — відомо, що існує універсальний граф для дерев з вершинами, що містить всього вершин і ребер, і цей граф оптимальний. Побудову, засновану на теоремі про планарне розбиття, можна використати, щоб показати, що планарні графи з вершинами мають універсальні графи з ребрами, і що планарні графи обмеженого степеня мають універсальні графи з ребрами. Гіпотеза Самнера стверджує, що турнір є універсальними для у тому сенсі, що будь-який турнір з вершинами містить будь-яке полідерево з вершинами як піддеревоSumner's Universal Tournament Conjecture, Douglas B. West, retrieved 2010-09-17..
Сімейство графів має універсальний граф поліноміального розміру, що містить будь-який граф з вершинами як породжений підграф, тоді й лише тоді, коли він має , в якій вершини можна позначити -бітовими рядками так, що алгоритм може визначити, чи суміжні вершини, за мітками цих вершин. Якщо граф цього типу існує, вершини будь-якого графа в можна позначити мітками відповідних вершин універсального графа, і навпаки, якщо схема розмітки існує, можна побудувати універсальний граф, що містить усі можливі мітки.
У старій математичній термінології фразу «універсальний граф» іноді використовували для повного графа.
Примітки
Література
Посилання The panarborial formula, «Theorem of the Day» concerning universal graphs for trees