Універса льний граф це нескінченний граф що містить будь який скінченний або не більше ніж зліченний граф як породжений

Універса́льний граф — це нескінченний граф, що містить будь-який скінченний (або не більше ніж зліченний) граф як породжений підграф. Універсальний граф цього типу першим побудував Р. Радо і цей граф тепер називають графом Радо або випадковим графом. Свіжіші роботи фокусуються на універсальних графах для сімейства графів $F$ . Тобто нескінченний граф, що належить $F$ , який містить усі скінченні графи сімейства $F$ . Наприклад, графи Генсона є універсальними в цьому сенсі для графів без $i$ -клік.

Універсальний граф для сімейства графів $F$ можна також розуміти як член послідовності скінченних графів, які містять усі графи з $F$ . Наприклад, будь-яке скінченне дерево є підграфом достатньо великого графа гіперкуба, так що можна сказати, що гіперкуб є універсальним графом для дерев. Однак це не найменший такий граф — відомо, що існує універсальний граф для дерев з $n$ вершинами, що містить всього $n$ вершин і $O(n log n)$ ребер, і цей граф оптимальний. Побудову, засновану на теоремі про планарне розбиття, можна використати, щоб показати, що планарні графи з $n$ вершинами мають універсальні графи з $O(n 3/2)$ ребрами, і що планарні графи обмеженого степеня мають універсальні графи з $O(n log n)$ ребрами. Гіпотеза Самнера стверджує, що турнір є універсальними для ^[en] у тому сенсі, що будь-який турнір з $2 n - 2$ вершинами містить будь-яке полідерево з $n$ вершинами як піддерево.

Сімейство графів $F$ має універсальний граф поліноміального розміру, що містить будь-який граф з $n$ вершинами як породжений підграф, тоді й лише тоді, коли він має ^[en], в якій вершини можна позначити $O (log n)$ -бітовими рядками так, що алгоритм може визначити, чи суміжні вершини, за мітками цих вершин. Якщо граф цього типу існує, вершини будь-якого графа в $F$ можна позначити мітками відповідних вершин універсального графа, і навпаки, якщо схема розмітки існує, можна побудувати універсальний граф, що містить усі можливі мітки.

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

Примітки

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

Література

^[en], R. L. Graham. On universal graphs for spanning trees // Journal of the London Mathematical Society. — 1983. — Т. 27, вип. 2 (28 червня). — DOI:10.1112/jlms/s2-27.2.203.
R. Rado. Universal graphs and universal functions // Acta Arithmetica. — 1964. — Т. 9 (28 червня).
R. Rado. Universal graphs // A Seminar in Graph Theory. — Holt, Rinehart, and Winston, 1967.
Martin Goldstern, Menachem Kojman. Universal arrow-free graphs // Acta Mathematica Hungarica. — 1996. — Т. 1973, вип. 4 (28 червня). — arXiv:math.LO/9409206. — DOI:10.1007/BF00052907.
Greg Cherlin, Saharon Shelah, Niandong Shi. Universal graphs with forbidden subgraphs and algebraic closure // Advances in Applied Mathematics. — 1999. — Т. 22, вип. 4 (28 червня). — arXiv:math.LO/9809202. — DOI:10.1006/aama.1998.0641.
A. Y. Wu. Embedding of tree networks into hypercubes // Journal of Parallel and Distributed Computing. — 1985. — Т. 2, вип. 3 (28 червня). — DOI:10.1016/0743-7315(85)90026-7.
L. Babai, ^[en], P. Erdős, R. L. Graham, J. H. Spencer. On graphs which contain all sparse graphs // Theory and practice of combinatorics: a collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday / Alexander Rosa, Gert Sabidussi, Jean Turgeon. — 1982. — Т. 12. — (Annals of Discrete Mathematics)
Sandeep N. Bhatt, ^[en], F. T. Leighton, Arnold L. Rosenberg. Universal graphs for bounded-degree trees and planar graphs // SIAM Journal on Discrete Mathematics. — 1989. — Т. 2, вип. 2 (28 червня). — DOI:10.1137/0402014.
^[en]. Separator theorems and their applications // Paths, Flows, and VLSI-Layout / Bernhard Korte, László Lovász, Hans Jürgen Prömel, Alexander Schrijver. — Springer-Verlag, 1990. — Т. 9. — (Algorithms and Combinatorics) — .
Sampath Kannan, Moni Naor, Steven Rudich. Implicit representation of graphs // SIAM Journal on Discrete Mathematics. — 1992. — Т. 5, вип. 4 (28 червня). — DOI:10.1137/0405049.

Посилання

The panarborial formula, «Theorem of the Day» concerning universal graphs for trees

[FOOTNOTERado1964331–340-1] Rado, 1964, с. 331–340.

[FOOTNOTERado196783–85-2] Rado, 1967, с. 83–85.

[FOOTNOTEGoldstern,_Kojman1996319–326-3] Goldstern, Kojman, 1996, с. 319–326.

[FOOTNOTECherlin,_Shelah,_Shi1999454–491-4] Cherlin, Shelah, Shi, 1999, с. 454–491.

[FOOTNOTEWu1985238–249-5] Wu, 1985, с. 238–249.

[FOOTNOTEChung,_Graham1983203–211-6] Chung, Graham, 1983, с. 203–211.

[FOOTNOTEBabai,_Chung,_Erdős,_Graham,_Spencer198221–26-7] Babai, Chung, Erdős, Graham, Spencer, 1982, с. 21–26.

[FOOTNOTEBhatt,_Chung,_Leighton,_Rosenberg1989145-8] Bhatt, Chung, Leighton, Rosenberg, 1989, с. 145.

[FOOTNOTEChung199017–34-9] Chung, 1990, с. 17–34.

[10] Sumner's Universal Tournament Conjecture, Douglas B. West, retrieved 2010-09-17.

[FOOTNOTEKannan,_Naor,_Rudich1992596–603-11] Kannan, Naor, Rudich, 1992, с. 596–603.