У теорії графів, теорема про планарне розбиття є формою ізопериметричної нерівності для планарних графів, що стверджує, що будь-який планарний граф можна розділити на дрібніші шматки, видаляючи невелику кількість вершин. Зокрема, видалення вершин з -вершинного графа (де О використано по аналогії з O великим ) може розділити граф на непересічні підграфи, кожен з яких має не більше вершин.
Більш слабка форма теореми розбиття з вершинами в розбитті, а не була спочатку доведена Унгаро (1951), а форма з близьким асимптотична оцінка від розміру розбиття вперше доведено по Lipton і Tarjan (1979). З їх роботі, теорема розбиття був reproven кількома різними способами, постійна в термін теореми була покращена, і це був продовжений до певних класів не планарних графів.
Повторне застосування теореми розбиття виробляє роздільник ієрархії, які можуть набувати форми або розкладання дерева або гілкове розкладання графу. Розбиття ієрархії можуть бути використані для розробки ефективного алгоритму розділяю і володарю для планарних графів, і динамічне програмування на цих ієрархій може бути використаний для розробки експоненціальне час і фіксованою параметрів згідливим алгоритми для вирішення NP-важкою задачі оптимізації на цих графіках. Розбиття ієрархії також можуть бути використані в вкладених перетинів, ефективного варіанту Гаусса для вирішення розріджених систем лінійних рівнянь, що випливають з методів кінцевих елементів.
Теорія Двовимірності Демейна, Фоміна, Hajiaghayi і Thilikos узагальнює і значно розширює застосовність теореми розбиття для величезної множини задач мінімізації планарних графів і в більш загальному графі за винятком фіксованих графів-мінорів.
Формулювання теореми Як зазвичай вказується, теорема стверджує, що розбиття, в будь-якому n-вершиного планарного графа , існує розбиття вершин в трьох сетах , , і , такі, що кожен з і має в більшості вершин, має вершини, і немає ребер з однієї кінцевої точки в і однієї кінцевої точки в . Це не потрібно, що або зв'язні підграфи з . називається розбиттям для цього розділу.
Еквівалентна формулювання є те, що краї будь-якого n-вершині планарного графа можуть бути поділені на дві крайові непересічних подграфов та таким чином, що обидва підграфи мати, принаймні вершин і таке, що перетин безлічі вершин двох подграфов є вершини в ньому. Таке розбиття відомий як поділ. Якщо поділ дано, то перетин множин вершин утворює роздільник, а вершини, які належать до однієї подграфа, але не іншу форму відокремлених підмножин не більш вершини. В іншому напрямку, якщо один дано розбиття на трьох наборів, , , та , які відповідають умовам теореми про планарне розбиття, то можна сформувати поділ, в якому краю з кінцевою точкою в належить , краю з кінцевою точкою в ставляться до , а решта ребра (з обох кінцевих точок в ) розділені довільно.
Постійна у формулюванні теореми розбиття є довільним і може бути замінений будь-яким іншим номером у відкритому проміжку , не змінюючи форму теореми: розділ в більш рівних підмножин можуть бути отримані від менш навіть розділу по кілька разів розділивши великі набори в нерівномірному розділу і перегрупування результаті зв'язкові компоненти..
Приклад
Розглянемо сітки графік з рядків і колон; число n вершин дорівнює . Наприклад, на малюнку, , , та . Якщо є непарним, є один центральний ряд, а в іншому випадку є два рядки однаково близько до центру; аналогічним чином, якщо нечетно, існує єдиний центральний стовпець, а в іншому випадку є дві колонки однаково близько до центру. Вибір бути кожний із цих центральних рядків або стовпців, а також усунення з графу, ділить графік на дві частини Підключення подграфов і , кожен з яких має не більше вершин. Якщо (як на малюнку), то, вибираючи центральну колонку дасть роздільник з вершин, і аналогічно, якщо , то вибираючи центральну ряд дасть розбиття на більшості вершин. Таким чином, кожен сітка граф має роздільник розміру не більше , усунення яких розділяє його на дві компоненти зв'язності, кожна розміром не більше .
Теорема про планарне розбіття стверджує, що подібна розділ може бути побудований в кожному пласкому графі. Випадок довільних планарнихграфів відрізняється від випадку сітки графіків в тому, що розбиття має розмір , але може бути більше, ніж , пов'язаних з розміром двох підмножин і (в найбільш поширених версій теореми) не , і дві підмножини A і необхідність самі по собі не утворюють з'єднані подграфов.
Будівельні
Ширина першого шару Lipton & Тар'я (1979) доповнити даний планарний граф додатковими гранями, при необхідності, таким чином, що він стає максимальним планарними (кожна грань в планарному вкладенні являє собою трикутник). Потім вони виконують пошуку в ширину, з коренем у довільній вершини , і розділити вершини в рівнях їх відстані від . Якщо є середній рівень (рівень, так що число вершин у вищих і нижчих рівнях як в найбільш ), тобто повинні бути рівні і , які кроків вище і нижче , відповідно, і які містять вершин, відповідно, в іншому випадку було б більше, ніж п вершин на рівнях поблизу . Вони показують, що там має бути роздільник формується шляхом об'єднання і , кінцеві точки з краю G, які не належать до пошук в ширину дерева і знаходиться між двома рівнями, а вершини на двох в ширину дерева пошуку шляхів від е назад до рівня . Розмір розбиття побудована таким чином, не більше , або приблизно . Вершини розбиття і два непересічних подграфов можна знайти в лінійному часу.
Це доказ теореми розбиття застосовується також для зважених планарних графів, в якому кожна вершина має невід'ємне вартість. Графік може бути розділена на три групи , , і такі, що і у кожного є в більшості від загальної вартості і має вершин, без будь-яких ребер до . Більш ретельного аналізу аналогічну конструкцію розбиття, Djidjev (1982) показує, що обмеження на розмір може бути зведена до , або приблизно .
Хольцер та ін. (2009) пропонують спрощену версію цього підходу: вони збільшують графік, щоб бути максимально планарною і побудувати широту в першу чергу дерево пошуку, як раніше. Тоді для кожного ребра е, який не є частиною дерева, вони утворюють цикл шляхом об'єднання е з шляху дерева, який з'єднує свої кінцеві точки. Потім вони використовують як роздільник вершини одного з цих циклів. Хоча цей підхід не може бути гарантована, щоб знайти невелике розбиття для планарних графів великого діаметра, їхні експерименти показують, що він перевершує за Lipton-Тар'я і Djidjev завширшки методи пошарового нанесення на багатьох видів планарного графа.
Прості розбиття циклу Для графа, який вже максимально планарний можна показати більш сильну конструкцію простого розбиття циклу, цикл малої довжини таким чином, що всередині і зовні циклу (в унікальному планарному вкладені графа) мають по крайней більшість вершини. Міллер (1986) доводить це (з розміром розбиття ), використовуючи техніку Ліптон-Тар'я для модифікованої версії широти першим пошуку, в якому рівні форма пошуку простих циклів.
Алон, Сеймур і Томас (1994) довели існування простих розбиттів циклу більш безпосередньо: вони дозволяють буде цикл на найбільш вершин, з не більш вершин поза , що форми, як навіть розділу внутрішнього і зовнішнього, наскільки це можливо, і вони показують, що ці припущення змусить розбитися .В іншому випадку, в межах відстані повинен бути рівний відстані в диску, оточеній (коротший шлях через внутрішню частину диска стане частиною кордону кращого циклу). Крім того, повинні бути довжиною рівно , в іншому випадку вона може бути поліпшена шляхом заміни одного з його країв двох інших сторін трикутника. Якщо вершини в нумеруються (за годинниковою стрілкою) від до і вершини поєднується з вершини , то ці підібрані пари можуть бути пов'язані вершинних непересічних шляхів в межах диск, за формою теореми Менгера для планарних графів. Тим не менш, загальна довжина цих шляхів обов'язково перевищувати , протиріччя. З деякою додаткової роботи, яку вони показують, аналогічним способом, що існує простий роздільник циклу розмір не більше , приблизно .
Djidjev & Венкатесан (1997) далі вдосконалювали постійний коефіцієнт в простій теореми розбиття цикл . Їх метод також можете знайти прості розбиття циклу для графів з невід'ємними вагами вершин, з розміром розбиття не більше , і може генерувати розбиття з меншим розміром за рахунок більш нерівномірним розбиттям графа. У 2-зв'язний планарні графи, що не максимальна, існують прості розбиття циклу з розміром, пропорційним евклідової нормоювектора довжини обличчя, які можуть бути знайдені найближчим часом лінійний.
Коло розбиття
Згідно з теоремою Кебе-Андреев-Терстона коло-упаковки, будь-який планарний граф може бути представлений в упаковці круглих дисків в площині з непересічних інтер'єрів, наприклад, що дві вершини в графі суміжні тоді і тільки тоді, коли відповідна пара дисків взаємно дотичній. Як Міллер та ін. (1997) шоу, для такої насадки, існує коло, яке має більше диски торкаючись або всередині неї, в найбільш диски торкаючись або за її межами, і який перетинає (дисків).
Щоб довести це, Міллер та ін. використовували стереографічну проєкцію на карті упаковки на поверхні одиничної сфери у трьох вимірах. Ретельно вибираючи проєкцію, центром сфери можуть бути зроблені в центральній точки дискових центрів на його поверхні, так що будь-яка площина, що проходить через центр сфери розділів його в двох напівпросторів, що кожен містять або перетинають понад з дисків. Якщо площина, що проходить через центр вибирається випадково рівномірно, диск буде перетинатися з імовірністю, пропорційною її радіусу. Таким чином, очікувана кількість дисків, які перетинаються пропорційна сумі радіусів кіл. Тим не менш, сума квадратів радіусів пропорційна сумарній площі дисків, який знаходиться на найбільш загальна площа поверхні одиничної сфери, постійне. Аргумент участю нерівність Дженсена показує, що, коли сума квадратів невід'ємних дійсних чисел обмежена константою, сума самих чисел . Таким чином, очікуване число дисків, що перетинаються випадкової площині і існує площину, яка перетинає саме, що багато диски. Цей літак перетинає сферу в великий круг, який виступає вниз до колу в площині із заданими властивостями. диски схрещені цього кола відповідають вершинам планарного розбиття графа, який відокремлює вершин, диски всередині кола з вершин, диски поза колом, з не більш вершин у кожній з цих двох підмножин.
Цей метод призводить до рандомізованого алгоритму, який знаходить такий розбиття в лінійному часу, і менш практичним детермінований алгоритм з тією ж лінійної час пов'язані. Аналізуючи цей алгоритм ретельно використовуючи відомі оцінки на щільність упаковки з кола упаковки, можна показати, щоб знайти розбиття розміру не більше
Хоча це поліпшений розмір розбиття пов'язаний приходить на рахунок більш-нерівній розбиття графа, Шпільман і Ден (1996) стверджують, що воно забезпечує поліпшений постійний коефіцієнт в час за годинником для вкладених перетинів в порівнянні з розбиття Алон, Сеймур і Томас (1990). Розмір розбиття вона виробляє можуть бути додатково поліпшені, на практиці, за допомогою неоднорідний розподіл для випадкового ріжучих площин.
Стереографічна проєкція в Міллер та ін. Аргумент можна уникнути, враховуючи маленький коло, що містить постійну частку центрами дисків, а потім розширювати його на константу підбирають рівномірно в діапазоні . Легко стверджувати, як в Miller та ін., Що диски, перетинають розширений коло утворюють правильний роздільник, і що, в очікуванні, розбиття має правильний розмір. Отримані константи дещо гірше.
Спектральний поділ