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

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

Література

Посилання