Мелкий минор
В теории графов мелкий минор или минор ограниченной глубины — это ограниченная форма минора графа , в которой подграфы, сжимающиеся для формирования минора, имеют малый диаметр . Мелкие несовершеннолетние были представлены Плоткиным, Рао и Смитом (1994) , которые приписали свое изобретение Чарльзу Э. Лейзерсону и Сивану Толедо. [1]
Определение
[ редактировать ]
Один из способов определения минора неориентированного графа G состоит в указании подграфа H графа G набора непересекающихся подмножеств вершин Si графа G , каждое из которых образует связный индуцированный подграф H i графа H. и Минор имеет вершину v i каждого подмножества Si для и ребро v i v j всякий раз, когда существует ребро из S i в S j, принадлежащее H .
этой формулировке d -мелкий минор (альтернативно называемый мелким минором глубины d ) — это минор, который можно определить таким образом, что каждый из подграфов Hi В имеет радиус не более d , что означает, что он содержит центральную вершину. c i который находится на расстоянии d от всех остальных вершин Hi . , Обратите внимание, что это расстояние измеряется количеством переходов в Hi расстояние , и поэтому оно может быть больше, чем G. в [1]
Особые случаи
[ редактировать ]Мелкие миноры нулевой глубины — это то же самое, что и подграфы данного графа. При достаточно больших значениях d (включая все значения, по крайней мере равные числу вершин) d -мелкие миноры данного графа совпадают со всеми его минорами. [1]
Классификация семейств графов
[ редактировать ]Нешетржил и Оссона де Мендес (2012) используют мелкие миноры для разделения семейств конечных графов на два типа. Они говорят, что семейство графов F если где-то плотно, существует конечное значение d , для которого d -мелкие миноры графов в F состоят из каждого конечного графа. В противном случае говорят, что семейство графов нигде не плотно . [2] Эта терминология оправдана тем, что если F — нигде не плотный класс графов, то (для любого ε > 0) n -вершинные графы в F имеют O ( n 1 + е ) края; таким образом, нигде не плотные графы являются разреженными графами . [3]
Более ограничительный тип семейства графов, описываемый аналогично, — это семейства графов ограниченного расширения . Это семейства графов, для которых существует функция f такая, что отношение ребер к вершинам в каждом d -мелком миноре не превосходит f ( d ). [4] Если эта функция существует и ограничена полиномом , говорят, что семейство графов имеет полиномиальное расширение.
Теоремы о сепараторах
[ редактировать ]Как показали Плоткин, Рао и Смит (1994) , графы с исключенными мелкими минорами можно разбить аналогично теореме о плоском сепараторе для плоских графов . В частности, если полный граф K h не является d -мелким минором n- вершинного графа G , то существует подмножество S графа G размером O ( dh 2 log n + n / d ), такой, что каждая компонента связности G \ S имеет не более 2 n /3 вершин. Результат конструктивен: существует алгоритм с полиномиальным временем, который находит либо такой разделитель, либо d -мелкий K h минор. [5] Как следствие, они показали, что каждое семейство малозамкнутых графов подчиняется теореме о сепараторе, почти такой же строгой, как и для плоских графов.
Плоткин и др. также применил этот результат к разбиению сеток метода конечных элементов на более высокие размерности; для этого обобщения необходимы неглубокие миноры, поскольку (без ограничения глубины) семейство сеток в трех или более измерениях имеет все графы как миноры. Тенг (1998) распространяет эти результаты на более широкий класс многомерных графов.
В более общем смысле, семейство наследственных графов имеет теорему о разделителе, согласно которой размер разделителя является сублинейной степенью n тогда и только тогда, когда он имеет полиномиальное разложение. [6]
Примечания
[ редактировать ]- ↑ Перейти обратно: Перейти обратно: а б с Нешетржил и Оссона де Мендес (2012) , раздел 4.2 «Неглубокие несовершеннолетние», стр. 62–65.
- ^ Нешетржил и Оссона де Мендес (2012) , раздел 5.3 «Классификация классов по минорным кликам», стр. 100–102.
- ^ Нешетрил и Оссона де Мендес (2012) , Теорема 5.3, стр. 100.
- ^ Нешетржил и Оссона де Мендес (2012) , Раздел 5.5 «Классы с ограниченным расширением», стр. 104–107.
- ^ Алгоритм Плоткина и др. занимает время O ( mn / d ), где m — количество ребер во входных данных. Вульф-Нильсен (2011) улучшил это значение для неразреженных графов до O ( m + n 2 + е / д ).
- ^ Дворжак и Норин (2015) .
Ссылки
[ редактировать ]- Дворжак, Зденек ; Норин, Сергей (2015), Сильно сублинейные сепараторы и полиномиальное разложение , arXiv : 1504.04821 , Bibcode : 2015arXiv150404821D .
- Плоткин, Серж; Рао, Сатиш; Смит, Уоррен Д. (1994), «Неглубоко исключенные несовершеннолетние и улучшенное разложение графов», Proc. 5-й симпозиум ACM-SIAM. по дискретным алгоритмам (SODA) , стр. 462–470 .
- Тенг, Шан-Хуа (1998), «Комбинаторные аспекты геометрических графов», Comput. Геом. , 9 (4): 277–287, doi : 10.1016/S0925-7721(96)00008-9 , MR 1609578 .
- Вульф-Нильсен, Кристиан (2011), «Теоремы о разделителях для графов без миноров и неглубоких графов без миноров с приложениями», Proc. 52-й симпозиум IEEE. Основы компьютерных наук (FOCS) , стр. 37–46, arXiv : 1107.1292 , doi : 10.1109/FOCS.2011.15 .
- Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, том. 28, Спрингер, номер домена : 10.1007/978-3-642-27875-4 , ISBN. 978-3-642-27874-7 , МР 2920058 .