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

В математике универсальный граф — это бесконечный граф , содержащий каждый конечный (или не более чем счетный ) граф в качестве индуцированного подграфа . Универсальный граф такого типа был впервые построен Ричардом Радо [1] [2] и теперь называется графом Радо или случайным графом. Более поздняя работа [3] [4] была сосредоточена на универсальных графах для семейства графов F : то есть бесконечного графа, принадлежащего F , который содержит все конечные графы из F . Например, графы Хенсона универсальны в этом смысле для графов без i -клики.

Универсальный граф для семейства графов F может также относиться к члену последовательности конечных графов, которая содержит все графы из F ; например, каждое конечное дерево является подграфом достаточно большого графа гиперкуба [5] , поэтому гиперкуб можно назвать универсальным графом для деревьев. Однако это не наименьший такой граф: известно, что существует универсальный граф для деревьев с n вершинами, всего с n  вершинами и O( n  log  n ) ребрами, и что это оптимально. [6] Конструкция, основанная на теореме о плоском сепараторе, может быть использована для того, чтобы показать, что планарные графы с n вершинами имеют универсальные графы с O( n 3/2 ) ребрами, и что планарные графы ограниченной степени имеют универсальные графы с O( n  log  n ) ребрами. [7] [8] [9] Также возможно построить универсальные графы для планарных графов, которые имеют n 1+ o (1) вершин. [10] Гипотеза Самнера утверждает, что турниры универсальны для полидеревьев , в том смысле, что каждый турнир с 2 n  − 2 вершинами содержит каждое полидерево с n вершинами в качестве подграфа. [11]

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

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

Понятие универсального графа было адаптировано и использовано для решения игр со средним выигрышем. [13]

Ссылки

  1. ^ Радо, Р. (1964). «Универсальные графы и универсальные функции». Акта Арифметика . 9 (4): 331–340. дои : 10.4064/aa-9-4-331-340 . МР  0172268.
  2. ^ Радо, Р. (1967). «Универсальные графы». Семинар по теории графов . Холт, Райнхарт и Уинстон. стр. 83–85. MR  0214507.
  3. ^ Голдстерн, Мартин; Койман, Менахем (1996). «Универсальные графы без стрелок». Acta Mathematica Hungarica . 1973 (4): 319–326. arXiv : math.LO/9409206 . doi : 10.1007/BF00052907 . MR  1428038.
  4. ^ Черлин, Грег; Шелах, Сахарон ; Ши, Ниандонг (1999). «Универсальные графы с запрещенными подграфами и алгебраическое замыкание». Успехи в прикладной математике . 22 (4): 454–491. arXiv : math.LO/9809202 . doi :10.1006/aama.1998.0641. MR  1683298. S2CID  17529604.
  5. ^ Wu, AY (1985). «Встраивание древовидных сетей в гиперкубы». Журнал параллельных и распределенных вычислений . 2 (3): 238–249. doi :10.1016/0743-7315(85)90026-7.
  6. ^ Chung, FRK ; Graham, RL (1983). "Об универсальных графах для остовных деревьев" (PDF) . Журнал Лондонского математического общества . 27 (2): 203–211. CiteSeerX 10.1.1.108.3415 . doi :10.1112/jlms/s2-27.2.203. MR  0692525. .
  7. ^ Бабай, Л .; Чунг, Ф. Р. К .; Эрдёш, П.; Грэхем , Р. Л .; Спенсер, Дж. Х. (1982). «О графах, содержащих все разреженные графы». В Rosa, Alexander; Sabidussi, Gert; Turgeon, Jean (ред.). Теория и практика комбинаторики: сборник статей, посвященных Антону Коцигу по случаю его шестидесятилетия (PDF) . Annals of Discrete Mathematics. Том 12. С. 21–26. MR  0806964.
  8. ^ Бхатт, Сандип Н.; Чунг, Фань Р.К.; Лейтон , Ф.Т.; Розенберг , Арнольд Л. (1989). «Универсальные графы для деревьев ограниченной степени и планарных графов». SIAM Journal on Discrete Mathematics . 2 (2): 145–155. doi :10.1137/0402014. MR  0990447.
  9. ^ Chung, Fan RK (1990). «Теоремы о разделителях и их приложения». В Korte, Bernhard ; Lovász, László ; Prömel, Hans Jürgen; et al. (ред.). Paths, Flows, and VLSI-Layout. Algorithms and Combinatorics. Vol. 9. Springer-Verlag. pp. 17–34. ISBN 978-0-387-52685-0. МР  1083375.
  10. ^ Дуймович, Вида; Эспере, Луи; Жоре, Гвенаэль; Гавуа, Сирил; Мичек, Петр; Морин, Пэт (2021), «Разметка смежности для планарных графов (и не только)», Журнал ACM , 68 (6): 1–33, arXiv : 2003.04280 , doi : 10.1145/3477542
  11. ↑ Универсальная турнирная гипотеза Самнера, Дуглас Б. Уэст, получено 17 сентября 2010 г.
  12. ^ Каннан, Сампат; Наор, Мони ; Рудич, Стивен (1992), «Неявное представление графов», SIAM Journal on Discrete Mathematics , 5 (4): 596–603, doi :10.1137/0405049, MR  1186827.
  13. ^ Czerwiński, Wojciech; Daviaud, Laure; Fijalkow, Nathanaël; Jurdziński, Marcin; Lazić, Ranko; Parys, Paweł (2018-07-27). «Универсальные деревья растут внутри разделяющих автоматов: квазиполиномиальные нижние границы для игр на четность». Труды тридцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . стр. 2333–2349. arXiv : 1807.10546 . doi :10.1137/1.9781611975482.142. ISBN 978-1-61197-548-2. S2CID  51865783.
  • Пандревесная формула, «Теорема дня» об универсальных графах для деревьев
Получено с "https://en.wikipedia.org/w/index.php?title=Universal_graph&oldid=1112303554"