Універсальний граф
Універса́льний граф — це нескінченний граф, що містить будь-який скінченний (або не більше ніж зліченний) граф як породжений підграф. Універсальний граф цього типу першим побудував Р. Радо[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].
У старій математичній термінології фразу «універсальний граф» іноді використовували для повного графа.
- ↑ 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.
- F. R. K. Chung[en], R. L. Graham. On universal graphs for spanning trees // Journal of the London Mathematical Society. — 1983. — Т. 27, вип. 2 (8 листопада). — DOI:.
- R. Rado. Universal graphs and universal functions // Acta Arithmetica. — 1964. — Т. 9 (8 листопада).
- 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 (8 листопада). — arXiv:math.LO/9409206. — DOI:.
- Greg Cherlin, Saharon Shelah, Niandong Shi. Universal graphs with forbidden subgraphs and algebraic closure // Advances in Applied Mathematics. — 1999. — Т. 22, вип. 4 (8 листопада). — arXiv:math.LO/9809202. — DOI:.
- A. Y. Wu. Embedding of tree networks into hypercubes // Journal of Parallel and Distributed Computing. — 1985. — Т. 2, вип. 3 (8 листопада). — DOI:.
- L. Babai, F. R. K. Chung[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, Fan R. K. Chung[en], F. T. Leighton, Arnold L. Rosenberg. Universal graphs for bounded-degree trees and planar graphs // SIAM Journal on Discrete Mathematics. — 1989. — Т. 2, вип. 2 (8 листопада). — DOI:.
- Fan R. K. Chung[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) — ISBN 978-0-387-52685-0.
- Sampath Kannan, Moni Naor, Steven Rudich. Implicit representation of graphs // SIAM Journal on Discrete Mathematics. — 1992. — Т. 5, вип. 4 (8 листопада). — DOI:.
- The panarborial formula, «Theorem of the Day» concerning universal graphs for trees
