Универсальный граф (Runfyjvgl,udw ijgs)

Перейти к навигации Перейти к поиску

Универсальный граф — это бесконечный граф, содержащий любой конечный (или не более чем счётный) граф в качестве порождённого подграфа. Универсальный граф этого типа первым построил Р. Радо[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]. Гипотеза Самнера утверждает, что турниры являются универсальными для полидеревьев[англ.] в том смысле, что любой турнир с 2n − 2 вершинами содержат любое полидерево с n вершинами в качестве поддерева[10].

Семейство графов F имеет универсальный граф полиномиальная размера, содержащий любой граф с n вершинами в качестве порождённого подграфа, тогда и только тогда, когда он имеет схему смежной разметки[англ.], в которой вершины могут быть помечены 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 Архивная копия от 27 февраля 2014 на Wayback Machine, Douglas B. West, retrieved 2010-09-17.
  11. ↑ Kannan, Naor, Rudich, 1992, с. 596–603.

Литература

[править | править код]
  • F. R. K. Chung, R. L. Graham. On universal graphs for spanning trees // Journal of the London Mathematical Society. — 1983. — Т. 27, вып. 2. — doi:10.1112/jlms/s2-27.2.203.
  • R. Rado. Universal graphs and universal functions // Acta Arithmetica. — 1964. — Т. 9.
  • 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. — doi:10.1007/BF00052907. — arXiv:math.LO/9409206.
  • Greg Cherlin, Saharon Shelah, Niandong Shi. Universal graphs with forbidden subgraphs and algebraic closure // Advances in Applied Mathematics. — 1999. — Т. 22, вып. 4. — doi:10.1006/aama.1998.0641. — arXiv:math.LO/9809202.
  • A. Y. Wu. Embedding of tree networks into hypercubes // Journal of Parallel and Distributed Computing. — 1985. — Т. 2, вып. 3. — doi:10.1016/0743-7315(85)90026-7.
  • L. Babai, F. R. K. Chung, 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, F. T. Leighton, Arnold L. Rosenberg. Universal graphs for bounded-degree trees and planar graphs // SIAM Journal on Discrete Mathematics. — 1989. — Т. 2, вып. 2. — doi:10.1137/0402014.
  • Fan R. K. Chung. 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. — doi:10.1137/0405049.

Ссылки

[править | править код]
Источник — https://ru.wikipedia.org/w/index.php?title=Универсальный_граф&oldid=124937393