Универсальный граф - Universal graph

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

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

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

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

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

Рекомендации

  1. ^ Радо, Р. (1964). «Универсальные графики и универсальные функции». Acta Arithmetica. 9 (4): 331–340. Дои:10.4064 / aa-9-4-331-340. МИСТЕР  0172268.
  2. ^ Радо, Р. (1967). «Универсальные графики». Семинар по теории графов. Холт, Райнхарт и Уинстон. С. 83–85. МИСТЕР  0214507.
  3. ^ Голдстерн, Мартин; Кожман, Менахем (1996). «Универсальные графики без стрелок». Acta Mathematica Hungarica. 1973 (4): 319–326. arXiv:math.LO / 9409206. Дои:10.1007 / BF00052907. МИСТЕР  1428038.
  4. ^ Черлин, Грег; Шела, Сахарон; Ши, Няньдун (1999). «Универсальные графы с запрещенными подграфами и алгебраическим замыканием». Успехи в прикладной математике. 22 (4): 454–491. arXiv:math.LO / 9809202. Дои:10.1006 / aama.1998.0641. МИСТЕР  1683298.
  5. ^ Ву, А.Ю. (1985). «Вложение древовидных сетей в гиперкубы». Журнал параллельных и распределенных вычислений. 2 (3): 238–249. Дои:10.1016/0743-7315(85)90026-7.
  6. ^ Чанг, Ф. Р. К.; Грэм, Р. Л. (1983). «Об универсальных графах для остовных деревьев» (PDF). Журнал Лондонского математического общества. 27 (2): 203–211. CiteSeerX  10.1.1.108.3415. Дои:10.1112 / jlms / s2-27.2.203. МИСТЕР  0692525..
  7. ^ Бабай, Л.; Чанг, Ф. Р. К.; Эрдеш, П.; Грэм, Р. Л.; Спенсер, Дж. Х. (1982). «О графах, содержащих все разреженные графы». В Розе, Александр; Сабидусси, Герт; Turgeon, Жан (ред.). Теория и практика комбинаторики: сборник статей, посвященных Антону Коцигу к его шестидесятилетию (PDF). Анналы дискретной математики. 12. С. 21–26. МИСТЕР  0806964.
  8. ^ Bhatt, Sandeep N .; Чунг, Фан Р. К.; Лейтон, Ф. Т.; Розенберг, Арнольд Л. (1989). «Универсальные графы для деревьев ограниченной степени и планарных графов». Журнал SIAM по дискретной математике. 2 (2): 145–155. Дои:10.1137/0402014. МИСТЕР  0990447.
  9. ^ Чунг, Фан Р. К. (1990). «Теоремы о разделителях и их приложения». В Корте, Бернхард; Ловас, Ласло; Prömel, Hans Jürgen; и другие. (ред.). Пути, потоки и макет СБИС. Алгоритмы и комбинаторика. 9. Springer-Verlag. стр.17–34. ISBN  978-0-387-52685-0. МИСТЕР  1083375.
  10. ^ Бонами, Марта; Гавой, Сирил; Пилипчук, Михал (2019), Более короткие схемы разметки для плоских графов, arXiv:1908.03341
  11. ^ Гипотеза Самнера об универсальном турнире, Дуглас Б. Вест, получено 17 сентября 2010 г.
  12. ^ Каннан, Сампатх; Наор, Мони; Рудич, Стивен (1992), «Неявное представление графов», Журнал SIAM по дискретной математике, 5 (4): 596–603, Дои:10.1137/0405049, МИСТЕР  1186827.
  13. ^ Червинский, Войцех; Daviaud, Laure; Фиялкоу, Натанаэль; Юрдзинский, Марцин; Лазич, Ранко; Парис, Павел (27.07.2018). «Универсальные деревья растут внутри разделяющих автоматов: квазиполиномиальные нижние оценки для игр на четность». arXiv:1807.10546 [cs.FL ].

внешняя ссылка