Interested Article - Универсальный граф

cathleen
  • 2020-04-27
  • 2

Универсальный граф — это бесконечный граф , содержащий любой конечный (или не более чем счётный ) граф в качестве порождённого подграфа . Универсальный граф этого типа первым построил Р. Радо и этот граф теперь называется графом Радо или случайным графом. Более свежие работы фокусируются на универсальных графах для семейства графов F . То есть бесконечный граф, принадлежащий F , содержащий все конечные графы семейства F . Например, графы Хэнсона являются универсальными в этом смысле для графов без i -клик.

Универсальный граф для семейства графов F может также пониматься как член последовательности конечных графов, которые содержат все графы из F . Например, любое конечное дерево является подграфом достаточно большого графа гиперкуба , так что можно сказать, что гиперкуб является универсальным графом для деревьев. Однако это не самый маленький такой граф — известно, что существует универсальный граф для деревьев с n вершинами, содержащий всего n вершин и O( n log n ) рёбер, и этот граф оптимален . Построение, основанное на теореме о планарном разбиении , может быть использовано, чтобы показать, что планарные графы с n вершинами имеет универсальные графы с O( n 3/2 ) рёбрами, и что планарные графы ограниченной степени имеют универсальные графы с O( n log n ) рёбрами . Гипотеза Самнера утверждает, что турниры являются универсальными для в том смысле, что любой турнир с 2 n − 2 вершинами содержат любое полидерево с n вершинами в качестве поддерева .

Семейство графов F имеет универсальный граф полиномиальная размера, содержащий любой граф с n вершинами в качестве порождённого подграфа, тогда и только тогда, когда он имеет , в которой вершины могут быть помечены O (log n ) -битными строками таким образом, что алгоритм может определить, смежны ли вершины, по меткам этих вершин. Если граф этого типа существует, вершины любого графа в F можно пометить метками соответствующих вершин универсального графа, и наоборот, если схема разметки существует, может быть построен универсальный граф, содержащий все возможные метки .

В старой математической терминологии фраза "универсальный граф" иногда использовался для полного графа .

Примечания

  1. , с. 331–340.
  2. , с. 83–85.
  3. , с. 319–326.
  4. , с. 454–491.
  5. , с. 238–249.
  6. , с. 203–211.
  7. , с. 21–26.
  8. , с. 145.
  9. , с. 17–34.
  10. от 27 февраля 2014 на Wayback Machine , Douglas B. West, retrieved 2010-09-17.
  11. , с. 596–603.

Литература

  • F. R. K. Chung, R. L. Graham. // Journal of the London Mathematical Society. — 1983. — Т. 27 , вып. 2 . — doi : .
  • 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 : . — arXiv : .
  • Greg Cherlin, Saharon Shelah, Niandong Shi. Universal graphs with forbidden subgraphs and algebraic closure // Advances in Applied Mathematics. — 1999. — Т. 22 , вып. 4 . — doi : . — arXiv : .
  • A. Y. Wu. Embedding of tree networks into hypercubes // Journal of Parallel and Distributed Computing. — 1985. — Т. 2 , вып. 3 . — doi : .
  • L. Babai , F. R. K. Chung , P. Erdős , R. L. Graham , J. H. Spencer. On graphs which contain all sparse graphs // / 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 // . — 1989. — Т. 2 , вып. 2 . — doi : .
  • 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 // . — 1992. — Т. 5 , вып. 4 . — doi : .

Ссылки

  • , "Theorem of the Day" concerning universal graphs for trees
Источник —

cathleen
  • 2020-04-27
  • 2
  • Tags:

Same as Универсальный граф

The title for the last searches