Мінор обмеженої глибини

Неглибокий мінор або мінор обмеженої глибини — це обмежений вид мінора графа, в якому стягнуті підграфи мають малий діаметр. Неглибокі мінори ввели Плоткін, Рао та СмітШаблон:Sfn, але вони приписують визначення терміна Чарльзу Лейзерсону та Сівану ТоледоШаблон:Sfn.

Визначення

Граф, що містить повний граф $K_4$ як 1-неглибокий мінор. Кожна з чотирьох підмножин усередині затінених прямокутників породжує підграф радіуса одиниця і існує ребро між будь-якими парами підмножин.

Один зі способів визначення мінора неорієнтованого графа $G$ полягає у вказанні підграфа $H$ графа $G$ і набору множин $S_i$ вершин графа $G$, що не перетинаються, кожна з яких утворює зв'язний породжений підграф $H_i$ графа $H$. Мінор має вершину $v_i$ для кожної підмножини $S_i$ і ребро $v_i{v}_j$_j, якщо існує ребро із $S_i$ до $S_j$, що належить $H$.

У цьому формулюванні $d$-неглибокий мінор (інша назва — мінор глибини $d$) — це мінор, який можна визначити вказаним вище чином з умовою, що кожен з підграфів $H_i$ має радіус, що не перевищує $d$, що означає, що підграф містить вершину $c_i$, відстань від якої до решти вершин підграфа $H_i$ не перевищує $d$. Зауважимо, що відстань тут вимірюється в числі дуг у графі $H_i$, а тому ця відстань може бути більшою за відстань у графі $G$Шаблон:Sfn.

Часткові випадки

Мінори глибини нуль — це те саме, що підграфи даного графа. За досить великого $d$ (зокрема, не менші від числа вершин графа), мінори глибини $d$ збігаються з усіма мінорами графаШаблон:Sfn.

Класифікація сімейств графів

Нешріл та Оссона де МендезШаблон:Sfn використовували неглибокі мінори для поділу сімейств кінцевих графів на два типи. Вони кажуть, що сімейство графів $F$ подекуди щільне, якщо існує скінченне значення $d$, для якого множина мінорів глибини $d$ графів $F$ містить будь-який скінченний граф. В іншому випадку кажуть, що сімейство графів ніде не щільнеШаблон:Sfn. Цю термінологію виправдовує те, що якщо $F$ ніде не щільний клас графів, то (для будь-якого $\epsilon >0$) графи з $n$ вершинами з $F$ мають $O(n^{1+\epsilon })$ вершин. Таким чином, ніде не щільні графи є розрідженими графамиШаблон:Sfn.

Більш обмежений тип сімейств графів, описуваних подібним чином — сімейства графів з обмеженим розширенням. Це сімейства графів, для яких існує функція $f$, така, що відношення числа ребер до числа вершин у будь-якому мінорі глибини $d$ не перевищує $f(d)$Шаблон:Sfn. Якщо така функція існує і обмежена многочленом, то кажуть, що сімейство має поліноміальне розширення.

Теорема про відділення

Як показали Плоткін, Рао і СмітШаблон:Sfn, графи з виключеними неглибокими мінорами можна розбити аналогічно до розбиття в теоремі про сепаратор для планарних графів. Зокрема, якщо повний граф $K_h$ не є мінором глибини $d$ графа $G$ з $n$ вершинами, існує підмножина $S$ вершин графа $G$ розміру $O(d{h}^2\log n+n/d)$, така, що будь-яка зв'язна компонента графа $G\mathrm{\setminus }S$ має максимум $2n/3$ вершин. Результат є конструктивним — існують алгоритми з поліноміальним часом виконання, які знаходять такий сепаратор, або мінор $K_h$ глибини $d$. Як наслідок, Плоткін та інші показали, що з будь-якого сімейства графів, замкненого відносно мінорів, теорема про сепаратор виконується майже так само строго, як і для планарних графів.

Плоткін та інші також застосували ці результати для поділу сіток у методі скінченних елементів у великих розмірностях. Для цього неглибокі мінори необхідні, оскільки (за відсутності обмежень) сімейство сіток у розмірностях три і вище мають мінорами всі графи. ТенгШаблон:Sfn поширив ці результати на ширший клас графів високої розмірності.

Дворак і Норін показали, що для класів, замкнутих відносно операції створення підграфів, із строгої сублінійності сепараторів випливає поліноміальність розширенняШаблон:Sfn.

Література

• Шаблон:Стаття
• Шаблон:Книга.
• Шаблон:Стаття.
• Шаблон:Книга
• Шаблон:Книга