|
Універсальний графУніверса́льний граф — це нескінченний граф, що містить будь-який скінченний (або не більше ніж зліченний) граф як породжений підграф. Універсальний граф цього типу першим побудував Р. Радо[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]. Гіпотеза Самнера стверджує, що турнір є універсальними для полідерев[en] у тому сенсі, що будь-який турнір з 2n − 2 вершинами містить будь-яке полідерево з n вершинами як піддерево[10]. Сімейство графів F має універсальний граф поліноміального розміру, що містить будь-який граф з n вершинами як породжений підграф, тоді й лише тоді, коли він має схему суміжної розмітки[en], в якій вершини можна позначити O(log n)-бітовими рядками так, що алгоритм може визначити, чи суміжні вершини, за мітками цих вершин. Якщо граф цього типу існує, вершини будь-якого графа в F можна позначити мітками відповідних вершин універсального графа, і навпаки, якщо схема розмітки існує, можна побудувати універсальний граф, що містить усі можливі мітки[11]. У старій математичній термінології фразу «універсальний граф» іноді використовували для повного графа. Примітки
Література
Посилання
|
