Jump to content

Ограниченное расширение

В теории графов , что семейство графов говорят имеет ограниченное расширение , если все его мелкие миноры являются разреженными графами . Многие естественные семейства разреженных графов имеют ограниченное расширение. Тесно связанное, но более сильное свойство, полиномиальное разложение , эквивалентно существованию теорем о разделителе для этих семейств. Семейства с этими свойствами имеют эффективные алгоритмы для решения проблем, включая проблему изоморфизма подграфов и проверку моделей для теории графов первого порядка.

Определение и эквивалентные характеристики

[ редактировать ]

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

Эквивалентные определения классов ограниченных расширений заключаются в том, что все мелкие миноры имеют хроматическое число, ограниченное функцией t , [1] или что данное семейство имеет ограниченное значение топологического параметра . Такой параметр представляет собой инвариант графа , монотонный относительно подграфов, такой, что значение параметра может изменяться только контролируемым образом при подразделении графа, и такой, что ограниченное значение параметра подразумевает, что граф имеет ограниченное вырождение . [2]

Теоремы о полиномиальном разложении и сепараторах

[ редактировать ]

Более сильное понятие – полиномиальное разложение , означающее, что функция f, используемая для ограничения плотности ребер мелких миноров, является полиномом . Если семейство наследственных графов подчиняется теореме о разделителе , утверждающей, что любой n- вершинный граф в семействе можно разбить на части, содержащие не более n /2 вершин, удалением O ( n с ) вершин для некоторой константы c < 1, то это семейство обязательно имеет полиномиальное расширение. И наоборот, графы с полиномиальным разложением имеют теоремы о сублинейном разделителе. [3]

Классы графов с ограниченным расширением

[ редактировать ]

Из-за связи между разделителями и расширением каждое минорно-замкнутое семейство графов , включая семейство планарных графов , имеет полиномиальное расширение. То же самое верно для 1-планарных графов и, в более общем плане, для графов, которые можно встроить в поверхности ограниченного рода с ограниченным числом пересечений на ребро, а также для без биклик струнных графов , поскольку все они подчиняются аналогичным теоремам о сепараторах. к планарным графам. [4] [5] [6] [7] В евклидовых пространствах более высокой размерности пересечений графы систем шаров со свойством, что любая точка пространства покрывается ограниченным числом шаров, также подчиняются теоремам о сепараторах. [8] что подразумевает полиномиальное разложение.

Хотя графы ограниченной толщины книги не имеют сублинейных разделителей, [9] они также имеют ограниченное расширение. [10] Другие графы ограниченного расширения включают графы ограниченной степени, [11] случайные графы ограниченной средней степени в модели Эрдеша–Реньи , [12] и графики числа ограниченной очереди . [2] [13]

Алгоритмические приложения

[ редактировать ]

Экземпляры проблемы изоморфизма подграфов , цель которой состоит в том, чтобы найти целевой граф ограниченного размера как подграф большего графа, размер которого не ограничен, могут быть решены за линейное время, когда больший граф принадлежит семейству графов ограниченное расширение. То же самое верно для поиска клик фиксированного размера, поиска доминирующих наборов фиксированного размера или, в более общем плане, проверки свойств, которые могут быть выражены формулой ограниченного размера в логике графов первого порядка . [14] [15]

Для графов полиномиального расширения существуют схемы аппроксимации полиномиального времени для задачи покрытия множества , задачи максимального независимого множества , задачи доминирующего множества и нескольких других связанных задач оптимизации графа. [16]

  1. Перейти обратно: Перейти обратно: а б Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), «5.5 Классы с ограниченным расширением», Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, том. 28, Springer, стр. 104–107, номер документа : 10.1007/978-3-642-27875-4 , ISBN.  978-3-642-27874-7 , МР   2920058 .
  2. Перейти обратно: Перейти обратно: а б Нешетржил, Ярослав ; Оссона де Мендес, Патрис ; Вуд, Дэвид Р. (2012), «Характеристики и примеры классов графов с ограниченным расширением», Европейский журнал комбинаторики , 33 (3): 350–373, arXiv : 0902.3265 , doi : 10.1016/j.ejc.2011.09.008 , МР   2864421 , S2CID   2633083 .
  3. ^ Дворжак, Зденек; Норин, Сергей (2016), «Сильно сублинейные сепараторы и полиномиальное разложение», SIAM Journal on Discrete Mathematics , 30 (2): 1095–1101, arXiv : 1504.04821 , doi : 10.1137/15M1017569 , MR   3504982 , S2CID   27395 359
  4. ^ Нешетрил и Оссона де Мендес (2012) , 14.2 Номер пересечения, стр. 319–321.
  5. ^ Григорьев Александр; Бодлендер, Ханс Л. (2007), «Алгоритмы для встраиваемых графов с небольшим количеством пересечений на ребро» , Algorithmica , 49 (1): 1–11, doi : 10.1007/s00453-007-0010-x , MR   2344391 , S2CID   8174422 .
  6. ^ Дуймович, Вида ; Эппштейн, Дэвид ; Вуд, Дэвид Р. (2015), «Род, ширина дерева и число локальных скрещиваний», Proc. 23-й Международный. Симп. Рисование графика (GD 2015) , arXiv : 1506.04380 , Bibcode : 2015arXiv150604380D .
  7. ^ Фокс, Джейкоб ; Пах, Янош (2009), «Теорема о разделителе для строковых графов и ее приложения» (PDF) , Combinatorics, Probability and Computing , 19 (3): 371, doi : 10.1017/s0963548309990459 , S2CID   5705145 .
  8. ^ Миллер, Гэри Л .; Тэн, Шанхуа ; Терстон, Уильям ; Вавасис, Стивен А. (1997), «Сепараторы для сферических упаковок и графов ближайших соседей», Журнал ACM , 44 (1): 1–29, doi : 10.1145/256292.256294 , MR   1438463 .
  9. ^ Дуймович, Вида; Сидиропулос, Анастасиос; Вуд, Дэвид Р. (2015), 3-монотонные расширители , arXiv : 1501.05020 , Bibcode : 2015arXiv150105020D
  10. ^ Нешетрил и Оссона де Мендес (2012) , 14,5 Номер стека, стр. 327–328.
  11. ^ Нешетрил и Оссона де Мендес (2012) , стр. 307.
  12. ^ Нешетрил и Оссона де Мендес (2012) , 14.1 Случайные графики (модель Эрдеша – Реньи), стр. 314–319.
  13. ^ Нешетрил и Оссона де Мендес (2012) , стр. 321–327.
  14. ^ Нешетржил и Оссона де Мендес (2012) , 18.3 Проблема изоморфизма подграфов и логические запросы, стр. 400–401.
  15. ^ Дворжак, Зденек ; Краль, Даниэль ; Томас, Робин (2010), «Определение свойств первого порядка для разреженных графов», Proc. 51-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS 2010) , IEEE Computer Soc., Лос-Аламитос, Калифорния, стр. 133–142, MR   3024787 .
  16. ^ Хар-Пелед, Сариэль ; Куанруд, Кент (2015), «Алгоритмы аппроксимации для графов полиномиального разложения и низкой плотности» , Алгоритмы - ESA 2015 , Конспекты лекций по информатике, том. 9294, Springer-Verlag, стр. 717–728, arXiv : 1501.00721 , doi : 10.1007/978-3-662-48350-3_60 , ISBN  978-3-662-48349-7 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 9b6336883761ed7acc5e2fbc5d6354b6__1701835320
URL1:https://arc.ask3.ru/arc/aa/9b/b6/9b6336883761ed7acc5e2fbc5d6354b6.html
Заголовок, (Title) документа по адресу, URL1:
Bounded expansion - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)