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

нескінченний граф, що містить будь-який скінченний (або не більше ніж зліченний) граф як породжений підграф

Універса́льний граф — це нескінченний граф, що містить будь-який скінченний (або не більше ніж зліченний) граф як породжений підграф. Універсальний граф цього типу першим побудував Р. Радо[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].

У старій математичній термінології фразу «універсальний граф» іноді використовували для повного графа.

ПриміткиРедагувати

  1. Rado, 1964, с. 331–340.
  2. Rado, 1967, с. 83–85.
  3. Goldstern, Kojman, 1996, с. 319–326.
  4. Cherlin, Shelah, Shi, 1999, с. 454–491.
  5. Wu, 1985, с. 238–249.
  6. Chung, Graham, 1983, с. 203–211.
  7. Babai, Chung, Erdős, Graham, Spencer, 1982, с. 21–26.
  8. Bhatt, Chung, Leighton, Rosenberg, 1989, с. 145.
  9. Chung, 1990, с. 17–34.
  10. Sumner's Universal Tournament Conjecture, Douglas B. West, retrieved 2010-09-17.
  11. Kannan, Naor, Rudich, 1992, с. 596–603.

ЛітератураРедагувати

ПосиланняРедагувати