Teorema partiției plane

Teorema partiției plane  este o formă a inegalității izoperimetrice pentru grafurile plane , care afirmă că orice graf plan poate fi rupt în bucăți mai mici prin eliminarea unui număr mic de vârfuri. În special, eliminând O(√ n ) vârfuri dintr-un graf cu n vârfuri (aici O înseamnă „O mare” ), se poate împărți graficul în subgrafe deconectate , fiecare dintre ele având cel mult 2 n /3 vârfuri.

O teoremă de partiție plană mai slabă cu vârfuri O(√ n  log  n ) în separator în loc de O(√ n ) a fost demonstrată de Ungar ( Ungar 1951 ), iar o teoremă cu o limită asimptotică mai puternică a mărimii separatorului a fost demonstrată mai întâi. de Lipton şi Tarjan ( Lipton şi Tarjan 1979) . De la lucrările lor, teorema partiției plane a fost re-demonstrată în mai multe moduri diferite, iar constanta O(√ n ) din enunțul teoremei a fost îmbunătățită. Teorema a fost extinsă și la unele clase de grafuri neplanare.

Reaplicarea teoremei de partiționare conduce la o ierarhie separatoare, care poate lua forma fie o descompunere arborescentă, fie o descompunere a graficului ramificat . Ierarhia separatorului poate fi utilizată pentru a dezvolta algoritmi eficienți „ Divide and Conquer ” pentru graficele plane, iar programarea dinamică pe aceste ierarhii poate fi utilizată pentru a dezvolta solubili în timp exponențial și cu parametri fix pentru a rezolva probleme de optimizare NP-hard pe aceste grafice. Ierarhia separatorului poate fi folosită și în disecția imbricată , o variantă eficientă a eliminării gaussiene pentru rezolvarea sistemelor rare de ecuații algebrice liniare care apar în metoda elementelor finite .

Teoria bidimensionalității Eric Demain , Fedor Fomin, Mohammed Hadjigaya și Dimitros Tilikos generalizează și extinde în mod semnificativ domeniul de aplicare al teoremei de partiționare plană la un set vast de probleme privind grafurile plane și, mai general, pe grafurile care nu nu contine un anumit minor .

Enunțul teoremei

În formularea sa obișnuită, teorema partiției plane afirmă că în orice graf planar G  = ( V , E ) cu n vârfuri, există o împărțire a vârfurilor lui G în trei mulțimi A , S și B astfel încât fiecare dintre mulțimi A și B au maximum 2 n /3 vârfuri, S are O(√ n ) vârfuri și nu există muchii care să aibă un capăt în A și celălalt capăt în B . Nu este necesar ca A sau B să fie subgrafe conectate ale lui G . Mulțimea S este numită separator pentru această partiție.

O formulare echivalentă este aceea că muchiile oricărui graf plan G cu n vârfuri pot fi împărțite în două subgrafe G 1 și G 2 neconectate prin muchii astfel încât ambele subgrafe să aibă cel puțin n /3 vârfuri, în timp ce intersecția seturile de vârfuri ale acestor două subgrafe au O(√ n ) vârfuri. O astfel de scindare este cunoscută sub denumirea de scindare [1] . Dacă este dată o deconectare, intersecția mulțimilor de vârfuri formează un separator, iar vârfurile care aparțin unui subgraf, dar nu altuia formează două submulțimi cu cel mult 2 n /3 vârfuri. În schimb, dacă se dă o partiție în trei mulțimi A , S și B care îndeplinește condițiile teoremei partiției plane, atunci se poate forma o deconectare în care muchiile cu capete în A aparțin lui G 1 , muchiile cu capete în B. aparțin lui G 2 , iar muchiile rămase (cu ambele capete în S ) pot fi incluse în oricare dintre seturi.

Constanta 2/3 din enunțul teoremei este arbitrară și poate fi înlocuită cu orice alt număr din intervalul deschis (1/2,1) fără a schimba forma teoremei - o partiție în submulțimi de dimensiuni mai egale poate fi obținut din partiții mai puțin identice prin repartiționarea unui set mai mare în părți inegale și rearanjamente ale componentelor conectate rezultate [2] .

Exemplu

Luați în considerare o rețea cu r rânduri și c coloane. Numărul n de vârfuri ale acestei rețele este egal cu rc . De exemplu, în figură, r  = 5, c  = 8 și n  = 40. Dacă r este impar, există un singur rând central, în caz contrar există două rânduri la fel de aproape de centru. În mod similar, dacă c este impar, există o singură coloană centrală, altfel există două coloane echidistante de centru. Alegând aceste rânduri și coloane centrale ca S și eliminând S din grafic, am împărțit graficul în două subgrafe mai mici A și B conectate , fiecare dintre ele având cel mult n /2 vârfuri. Dacă r  ≤  c (ca în figură), alegerea coloanei centrale va da un separator S cu r  ≤ √ n vârfuri, iar în mod similar, dacă c  ≤  r , alegerea rândului central va da un separator cu cel mult √ n vârfuri. Astfel, orice graf reticulat are un separator S cu cel mult √ n vârfuri, a cărui eliminare împarte graficul în două componente conectate, a căror dimensiune nu depășește n /2 [3] .

Teorema partiției plane afirmă că o partiție similară poate fi construită pentru orice graf planar. Cazul unui graf planar arbitrar diferă de graful reticulat prin faptul că, în acest caz, separatorul are dimensiunea O(√ n ), care poate fi mai mare decât numărul √ n , și dimensiunile a două submulțimi A și B (în cel mai mult versiunea comună a teoremei) nu depășesc 2 n / 3, nu n /2, ca și în cazul graficelor latice. De asemenea, submulțimile A și B nu formează neapărat subgrafe conectate.

Clădiri

Pachet

Lipton și Tarjan [4] măresc un graf planar dat adăugând muchii dacă este necesar, astfel încât să devină un graf planar maxim (fiecare față a unei înglobări plane este un triunghi). Apoi ei fac o primă căutare în lățime , începând de la un vârf arbitrar v și împart vârfurile în niveluri în funcție de distanța lor de la v . Dacă l 1 este o mediană (un nivel pentru care numărul de vârfuri deasupra și dedesubtul lui nu depășește n /2), atunci trebuie să existe niveluri l 0 și l 2 care sunt O(√ n ) trepte deasupra și sub l 1 conţinând O (√ n ) vârfuri, altfel există mai mult de n vârfuri în apropierea nivelului l 1 . Ei au arătat că trebuie să existe un separator S format din unirea dintre l 0 și l 2 și capetele muchiilor graficului G care se află între aceste două niveluri. Mărimea separatorului S construit în acest fel nu depășește √8√ n , care este aproximativ 2,83√ n . Vârfurile separatorului și două seturi de partiții pot fi găsite în timp liniar .

Această demonstrație a teoremei de partiționare plană se aplică și graficelor plane ponderate când fiecare vârf are un cost nenegativ. Graficul poate fi împărțit în trei mulțimi A , S și B , astfel încât A și B costă cel mult 2/3 din prețul integral, iar S are O(√ n ) vârfuri fără muchii de la A la B [4] . Analizând astfel de construcții de separatoare mai atent, Dzhidzhev [2] a arătat că limita de dimensiune S poate fi redusă la √6√ n , care este aproximativ egal cu 2,45√ n .

Holzer, Schultz Wagner, Prasinos și Zaroligis [5] au propus o versiune simplificată a abordării - ei extind graficul la un grafic planar maxim și efectuează o căutare pe lățimea întâi în același mod ca cel descris mai sus. Apoi, pentru fiecare muchie e care nu aparține arborelui de căutare, ele formează o buclă combinând e cu căi din arbore care leagă capetele marginii. Apoi folosesc una dintre aceste bucle ca separator de vârfuri. Deși această abordare nu garantează găsirea unui separator mic pentru grafurile plane cu diametru mare, experimentele lor arată că această abordare are rezultate mai bune decât metodele de fibrare Lipton-Tarjan și Didzhev pe multe tipuri de grafuri plane.

Cicluri simple de separare

Pentru un grafic care este deja maxim planar, se poate arăta o construcție riguroasă a unui ciclu-separator simplu , un ciclu de lungime mică ale cărui părți interioare și exterioare (pentru o anumită încorporare plană) nu au mai mult de 2n /3 vârfuri. Miller [6] a demonstrat acest lucru (cu un separator de dimensiune √8√ n ) folosind tehnica Lipton-Tarjan pentru o versiune modificată a căutării pe lățimea întâi în care nivelurile formează cicluri simple.

Alon, Seymour și Thomas [7] au demonstrat existența unui separator de ciclu simplu într-un mod mai direct — au considerat cicluri C cu cel mult √8√ n vârfuri care au cel mult 2 n /3 vârfuri în afara lui C , apoi formate o partiție în cât mai multe părți mai apropiate în interiorul și în afara buclei. Ei au arătat că în toate aceste condiții C ar trebui să fie un separator. În caz contrar, distanțele din interiorul C trebuie să fie egale cu distanțele din discul închis de C (cea mai scurtă cale prin interiorul discului ar face parte din cea mai bună limită a ciclului). În plus, ciclul C trebuie să aibă lungimea exact √8√ n , altfel poate fi îmbunătățit prin înlocuirea uneia dintre margini cu celelalte două laturi ale triunghiului. Dacă vârfurile ciclului C sunt numerotate (în sensul acelor de ceasornic) de la 1 la √8√ n și vârful i corespunde vârfului √8√ n − i + 1 , atunci aceste perechi de vârfuri pot fi conectate prin căi care nu se intersectează în interior. discul (conform uneia dintre formele teoremei lui Menger pentru grafurile plane). Cu toate acestea, lungimea totală a acestor căi ar depăși n , o contradicție. După câteva calcule suplimentare, ei au arătat, folosind metode similare, că există un separator de ciclu simplu de dimensiune de cel mult (3/√2)√ n , care este aproximativ egal cu 2,12√ n .

Jijev și Venkatesan [8] au îmbunătățit ulterior constanta din teorema separatorului de ciclu simplu la 1,97√ n . Metoda lor face posibilă, de asemenea, căutarea de separatori de ciclu simple pentru grafice cu greutăți de vârf nenegative cu o dimensiune a separatorului care nu depășește 2√ n . Metoda vă permite să creați separatori cu o dimensiune mai mică, totuși, datorită diferenței mai mari de dimensiuni ale părților partiției. Într-un graf planar nemaximal cu 2 conexiuni, există un ciclu-separator simplu cu o dimensiune proporțională cu norma euclidiană a vectorului lungime a feței, care poate fi găsit în timp aproape liniar [9] .

Separatoare de cicluri

Conform teoremei de împachetare a cercului Koebe-Andreev-Thurston, orice graf plan poate fi reprezentat ca un pachet de cercuri într-un plan cu regiuni interioare care nu se intersectează, astfel încât două vârfuri ale graficului să fie adiacente dacă și numai dacă cercurile corespunzătoare ating . După cum au arătat Miller, Teng, Thurston și Wawasis [10] , pentru astfel de ambalaje există un cerc care este atins sau se află în interiorul lui, nu mai mult de 3 n /4 discuri, nu mai mult de 3 n /4 discuri se află în afara cercului, sau atingeți-l și care intersectează discuri O(√ n ).

Pentru a demonstra acest lucru, Miller și colab. au folosit proiecția stereografică pentru a mapa împachetarea pe suprafața unei singure sfere 3D. Cu o alegere atentă a proiecției, centrul sferei poate fi plasat la mijlocul al centrelor discurilor suprafeței, astfel încât orice plan care trece prin centrul sferei va împărți sfera în două emisfere, fiecare dintre care contine sau intersecteaza nu mai mult de 3 n /4 discuri. Dacă planul prin centru este ales aleatoriu și uniform, discul va fi tăiat cu o probabilitate proporțională cu raza. Astfel, numărul așteptat de discuri încrucișate este proporțional cu suma razelor discurilor. Cu toate acestea, suma razelor pătrate este proporțională cu aria totală a discurilor, care nu depășește suprafața unei sfere unitare, o constantă. Argumentele care folosesc inegalitatea lui Jensen arată că, dacă suma pătratelor a n numere nenegative este mărginită de o constantă, suma numerelor în sine nu depășește O(√ n ). Astfel, așteptarea numărului de intersecții ale discurilor cu un plan aleator este O(√ n ) și există un plan care nu intersectează mai mult decât acest număr de discuri. Acest plan intersectează sfera într-un cerc mare , a cărui proiecție înapoi pe plan dă proprietățile dorite. Discurile O(√ n ) intersectate de acest cerc corespund vârfurilor separatorului de graf plan, care separă vârfurile ale căror discuri se află în interiorul cercului de vârfurile ale căror discuri se află în afara cercului și fiecare dintre aceste submulțimi are cel mult 3 n /4 vârfuri [10] [11] .

Această metodă conduce la un algoritm probabilistic care găsește un separator în timp liniar [10] și un algoritm determinist mai puțin practic cu aceeași limită de timp liniară [12] . Analizând cu atenție acest algoritm și folosind limitele cunoscute ale densității de împachetare a cercurilor , se poate demonstra că este posibil să se găsească separatori care să nu depășească dimensiunea.

[13]

Deși această dimensiune îmbunătățită a separatorului are ca rezultat o partițiune mai inegală a graficului, Shpilman și Teng [14] susțin că metoda oferă un multiplicator îmbunătățit în timpul de rulare pentru partiționarea imbricată în comparație cu separatorul Alon, Seymour și Thomas [1] . Dimensiunea separatoarelor poate fi, în practică, îmbunătățită prin utilizarea unei distribuții neuniforme a planurilor de tăiere aleatoare [15] .

Proiecția stereografică din argumentul lui Miller și colab. poate fi evitată luând în considerare cel mai mic cerc care conține o fracțiune constantă de centrii discului, apoi extinzându-se cu o cantitate aleasă uniform în intervalul [1,2]. Este ușor să arăți, ca și în cazul lui Miller, că discurile străbătute de un astfel de cerc formează un separator regulat, iar atunci așteptarea matematică a numărului de intersecții va da rezultatul corect. Adevărat, constantele rezultate vor fi oarecum mai proaste [16] .

Partiționare spectrală

Metodele de grupare spectrală , în care vârfurile grafului sunt grupate în funcție de coordonatele cu valori proprii ale matricelor obținute din graf, au fost utilizate de mult timp ca metode euristice pentru rezolvarea problemelor de partiționare a grafurilor pentru grafurile neplanare [17] [18] . După cum au arătat Shpilman și Teng [19] , gruparea spectrală poate fi folosită și pentru a demonstra alternativ o formă slăbită a teoremei de partiție plană aplicată graficelor plane cu grad de vârf mărginit. În metoda lor, vârfurile unui graf plan dat sunt sortate după a doua coordonată a vectorilor proprii ai matricei Kirchhoff a grafului, iar această ordine este împărțită într-un punct care minimizează raportul dintre numărul de muchii eliminate și numărul de vârfuri ale părții mai mici a partiției. După cum au arătat, orice graf plan cu un grad mărginit de vârfuri are o partiție în care acest raport este O(1/√ n ). Deși această partiție poate să nu fie echilibrată, repetarea partiției celei mai mari dintre cele două părți și îmbinarea tăierilor obținute la fiecare iterație duce în cele din urmă la o partiție echilibrată cu muchii O(√ n ). Vârfurile de capăt ale acestor muchii formează un separator de dimensiune (√ n ).

Separatoare nervuri

O variantă a teoremei de descompunere plană vorbește despre separatori de muchii , seturi mici de muchii care formează o tăietură între două submulțimi A și B ale vârfurilor unui graf. Cele două mulțimi, A și B , trebuie să aibă o dimensiune de cel mult o fracțiune constantă din numărul n de vârfuri din grafic (de obicei, ambele mulțimi trebuie să nu fie mai mari de 2 n /3), iar fiecare vârf al graficului aparține doar la A sau B. Separatorul este format din muchii care au un capăt în A și celălalt capăt în B . Limitele de mărime a separatorului de muchii depind atât de gradul vârfurilor graficului, cât și de numărul de vârfuri din graficul - grafice plane, în care un vârf are gradul n  - 1, unde cad roțile și stelele , nu are un separator cu un subliniar. număr de muchii, deoarece orice separator de muchii ar trebui să includă toate muchiile care conectează un vârf de grad înalt la vârfurile de pe cealaltă parte a tăieturii. Totuși, orice graf plan cu gradul maxim Δ are un separator de muchii de dimensiunea O(√(Δ n )) [20]

Un separator de ciclu simplu în graficul dual al unui grafic plan formează un separator de margini al graficului original [6] [9] . Aplicarea teoremei separatorului de ciclu simplu a lui Gacit și Miller [9] la graficul dual al unui graf plan dat întărește estimarea O(√(Δ n )) pentru dimensiunea separatorului de muchii, deoarece arată că orice graf planar are un separator de muchii. a cărei mărime este proporţională cu norma euclidiană a gradelor de vârf vectoriale ale graficului.

Papadimitrou și Sideri [21] au descris un algoritm în timp polinomial pentru găsirea unui separator de muchii care împarte un grafic G în două subgrafe de dimensiune egală dacă G este un subgraf generat al unui grafic reticulat fără găuri sau cu un număr constant de găuri. Cu toate acestea, ei au presupus că problema este NP-completă pentru cazul grafurilor plane arbitrare și au arătat că complexitatea problemei pentru grafurile cu rețea cu un număr arbitrar de găuri este aceeași ca și pentru grafurile plane arbitrare.

Limite inferioare

În graficul rețelei √ n  × √ n , mulțimea S care conține s  < √ n puncte poate înconjura o submulțime de cel mult s ( s  − 1)/2 puncte ale rețelei, iar maximul se atinge plasând S pe diagonală linie mai aproape de colțul zăbrelei. Astfel, pentru a forma un separator care separă cel puțin n /3 puncte de grilă, s trebuie să aibă o dimensiune de cel puțin √(2 n /3), care este de aproximativ 0,82√ n .

Există grafice plane cu n vârfuri (pentru valori arbitrar de mari ale lui n ) astfel încât, pentru orice separator S care împarte graficul rămas în subgrafe cu cel mult 2n /3 vârfuri, S are cel puțin √(4π√3)√ n vârfuri, aproximativ 1,56√ n [2] . Construcția folosește o aproximare a unei sfere cu un poliedru convex prin înlocuirea fiecărei fețe a poliedrului cu o plasă triunghiulară. Teorema izoperimetrică este apoi aplicată pe suprafața unei sfere.

Ierarhii separatoare

Separatoarele pot fi combinate într- o ierarhie a separatoarelor de grafice plane , o descompunere recursivă în grafice mai mici. Ierarhia separatorului poate fi reprezentată ca un arbore binar , în care rădăcina reprezintă graficul însuși, iar cele două noduri copil ale rădăcinii sunt rădăcinile subgrafelor generate ale submulților A și B ale ierarhiei separatoare construite recursiv.

Ierarhia separatorilor de acest tip formează baza pentru o descompunere arborescentă a unui graf dat, în care mulțimea de vârfuri asociate unui nod arborescent este uniunea separatoarelor pe calea de la acest nod până la rădăcina arborelui. Deoarece dimensiunile graficelor scad cu un factor constant la fiecare nivel al arborelui, limitele superioare ale mărimii separatorilor scad și ele cu un factor constant la fiecare nivel, astfel încât dimensiunile separatorilor de-a lungul acestor căi se adună exponențial la O(√ n ). Adică, separatorul astfel format are lățimea O(√ n ) și aceasta poate fi folosită pentru a arăta că orice graf plan are lățimea arborelui O(√ n ).

Construirea unei ierarhii separatoare direct prin parcurgerea arborelui binar de sus în jos și aplicarea unui algoritm de timp liniar pentru a găsi un separator plan la fiecare dintre subgrafele generate asociate cu fiecare nod al arborelui binar ar dura timp total O( n  log  n ) . Cu toate acestea, este posibil să construim întreaga ierarhie a separatorului în timp liniar dacă folosim abordarea de fibrare a lățimii Lipton-Tarjan și folosim structuri de date adecvate pentru a implementa fiecare pas de partiționare în timp subliniar [22] .

Dacă formăm ierarhii bazate nu pe separatori, ci pe deconectări, în care două vârfuri copil devin rădăcini pentru construcția recursivă a ierarhiilor separatoare pentru două subgrafe G 1 și G 2 ale separării unui graf dat, atunci structura completă formează o descompunere. a graficului în ramuri și nu o descompunere a arborelui. Lățimea oricărei diviziuni în această descompunere este din nou mărginită de suma dimensiunilor separatorilor de pe calea de la orice nod la rădăcina ierarhiei, astfel încât orice descompunere astfel obținută are lățimea O(√ n ) și orice grafic planar are lățimea ramurilor O(√ n ). Deși multe alte probleme legate de partiționarea grafurilor sunt NP-complete chiar și pentru grafurile plane, este posibil să se găsească o descompunere a unui graf plan în ramuri cu lățime minimă în timp polinomial [23] .

Aplicând metodele lui Alon, Seymour și Thomas [7] mai direct pentru a construi o descompunere a graficului în ramuri, Fomin și Tilikos [24] au arătat că orice graf plan are o lățime de ramificare care nu depășește 2,12√ n , adică cu aceeași constantă ca și pentru teorema de partiționare a lui Alon Alon, Seymour și Thomas prin separatori de ciclu simple. Deoarece lățimea arborelui oricărui grafic este de cel mult 3/2 din lățimea ramurilor, acest lucru arată, de asemenea, că graficele plane au o lățime a arborelui de cel mult 3,18√ n .

Alte clase de grafice

Unele grafice rare nu au separatori subliniari de dimensiune - într-un expander , eliminarea unei fracțiuni constante de vârfuri lasă o componentă conectată [4] [25] .

Poate că cea mai veche teoremă de partiționare este rezultatul lui Jordan [26] că orice arbore poate fi împărțit în doi subarbori cu cel mult n /2 vârfuri în fiecare prin eliminarea unui singur vârf [10] . În special, vârful care minimizează dimensiunea componentei maxime are această proprietate. Aplicând aceeași tehnică la descompunerea arborelui unui grafic arbitrar, se poate demonstra că orice grafic are un separator cu o dimensiune care nu depășește lățimea arborelui .

Dacă graficul G nu este plan, dar poate fi încorporat într-o suprafață de genul g , atunci are un separator cu vârfuri O(( gn ) 1/2 ). Gilbert, Hutchinson și Tarjan [27] au demonstrat acest lucru folosind o abordare apropiată de cea a lui Lipton și Tarjan [4] . Aceștia grupează vârfurile graficului după niveluri de căutare pe lățimea întâi și găsesc două niveluri a căror eliminare lasă cel mult o componentă mare constând dintr-un număr mic de niveluri. Această componentă rămasă poate fi făcută plană prin eliminarea unui număr de căi de căutare pe lățimea întâi proporțional cu genul graficului, după care metoda Lipton-Tarjan poate fi aplicată graficului planar rămas. Rezultatul se obține prin echilibrarea cu atenție a dimensiunii celor două niveluri îndepărtate și a numărului de niveluri dintre ele. Având în vedere încorporarea unui grafic, separatorul acestuia poate fi găsit în timp liniar . Graficele genului g au separatori de mărimea O(( g Δ n ) 1/2 ) [28] .

Graficele de gen mărginit formează un exemplu de familie de grafuri închise sub operațiunea de a lua minori , iar teoremele de partiție se aplică familiilor arbitrare de grafuri închise sub luarea unui minor. În special, dacă o familie de grafuri are un minor interzis cu h vârfuri, atunci are un separator cu vârfuri O( h √ n ), iar un astfel de separator poate fi găsit în timp O( n 1 + ε ) pentru orice ε > 0 [29]

Metoda ciclurilor-separatoare a lui Miller, Teng, Thurston și Vavasis [10] este generalizată pentru graficele de intersecție ale oricărui sistem de bile d - dimensionale, care au proprietatea că orice punct al suprafeței este acoperit de bile cel mult o constantă. număr k ori, pentru graficele k - vecinii cei mai apropiați în spațiul de dimensiune d [10] , și pentru graficele care apar în grile cu elemente finite [30] . Separatoarele sferice construite în acest fel împart graficul de intrare în subgrafe cu cel mult n ( d + 1)/( d + 2) vârfuri. Mărimea separatoarelor pentru graficele de bile care se suprapun de k - ori și graficele de k -cei mai apropiati vecini este O( k 1/ d n 1 − 1/ d ) [10] .

Aplicații

Algoritmi Divide and Conquer

Partițiile de separare pot fi folosite pentru a construi algoritmi eficienți „ Divide and Conquer ” pentru rezolvarea problemelor pe grafice plane. Un exemplu de problemă care poate fi rezolvată cu această abordare este găsirea celui mai scurt ciclu într-un grafic direcționat plan ponderat. O poți face astfel:

Timpul a două apeluri recursive pentru A și B în acest algoritm este dominat de timpul de rulare O(√ n ) al algoritmului lui Dijkstra, astfel încât acest algoritm găsește cel mai scurt ciclu în timpul O( n 3/2  log  n ).

Un algoritm mai rapid pentru aceeași problemă de găsire a celui mai scurt ciclu, care rulează în timp O( n  log 3 n ), a fost dat de Wolf-Nielsen [31] . Algoritmul său folosește aceeași structură de împărțire și cucerire bazată pe separatoare, dar folosește separatoare de ciclu simple în loc de separatoare arbitrare, astfel încât vârfurile mulțimii S să aparțină aceleiași fețe (pentru graficul interior și pentru graficul exterior cu privire la la separator) . Apoi înlocuiește apelurile individuale O(√ n ) la algoritmul lui Dijkstra cu algoritmi mai sofisticați pentru găsirea celor mai scurte căi de la toate vârfurile pe o singură față a unui graf plan și combinarea distanțelor de la două subgrafe. Pentru graficele plane ponderate, dar nedirecționate, cel mai scurt ciclu este echivalent cu cea mai mică tăietură din graficul dual și poate fi găsit în timp O( n  log log  n ) [32] și cel mai scurt ciclu într-un grafic planar nedirecționat cu ciclu ponderat (sau circumferința ) poate fi găsită în timp O( n ) [33] . (Cu toate acestea, algoritmul mai rapid pentru graficele neponderate nu se bazează pe teorema partiției.)

Frederickson a propus în 1986 un alt algoritm rapid pentru calea cea mai scurtă dintr-o singură sursă utilizând teorema de partiționare pentru graficele plane [34] . Algoritmul este o îmbunătățire a căutării iterative a lui Dijkstra pe un subset de vârfuri ales cu grijă. Această versiune rulează în timp O( n √(log n )) pe un grafic cu n vârfuri. Separatoarele sunt folosite pentru a găsi împărțirea unui grafic, adică împărțirea acestuia în două sau mai multe submulțimi, numite zone. Se spune că un nod este conținut într-o regiune dacă o margine a regiunii este incidentă cu nodul. Un nod care este conținut în mai multe zone se numește nodul de limită al zonelor care îl conțin. Metoda folosește noțiunea de r -diviziune a unui graf cu n noduri, care corespunde împărțirii graficului în O( n / r ) regiuni, fiecare dintre acestea conținând O( r ) noduri, inclusiv O(√ r ) noduri limită. . Frederickson a arătat că r -diviziunea poate fi găsită în timp O( n log n ) prin aplicarea recursivă a teoremei partiției.

Schița algoritmului de rezolvare a problemei.

1. Pregătirea preliminară . Împărțim graficul în subseturi de vârfuri atent selectate și găsim cele mai scurte căi între toate perechile de vârfuri din aceste submulțimi, în care vârfurile intermediare ale căii nu aparțin submulțimii. În această fază, este necesară transformarea graficului plan G 0   în G , care nu are vârfuri cu grad mai mare de 3. Din formula lui Euler , numărul de vârfuri din graficul rezultat va fi n ≤ 6 n 0  −12, unde n 0   este numărul de vârfuri din graficul G 0  . Această fază oferă, de asemenea, următoarele proprietăți ale diviziunilor r adecvate. O r -diviziune adecvată a unui graf plan este o r -diviziune astfel încât

2. Căutați

Henzinger și colab. au extins tehnica r -division a lui Frederickson pentru algoritmul de găsire a celei mai scurte căi de la o singură sursă în grafice plane cu lungimi de muchii nenegative și au propus un algoritm de timp liniar [35] . Metoda lor generalizează noțiunea de partiție Fredrekson pentru un graf, astfel încât acum o partiție ( r , s ) a unui graf cu n noduri devine o partiție în O( n / r ) regiuni, fiecare conținând r {O(1) }   noduri și cel mult s noduri de frontieră. Dacă partiția ( r , s ) se repetă secvențial pentru a partiționa în regiuni mai mici, aceasta se numește o partiție recursivă. Algoritmul utilizează aproximativ log* n niveluri de diviziune. Diviziunea recursiva este reprezentată de un arbore înrădăcinat ale cărui frunze sunt etichetate cu diferite margini ale graficului G. Rădăcina arborelui reprezintă regiunea formată din întregul grafic G , copiii rădăcinii reprezintă subregiunile în care este împărțită regiunea. Fiecare frunză reprezintă exact o margine.

Disecția imbricată  este o variație bazată pe separator a abordării împărțiți și cuceriți a metodei de eliminare gaussiene pentru rezolvarea sistemelor rare simetrice de ecuații algebrice liniare cu o structură de graf plană, cum ar fi cele care apar în metoda elementelor finite . Metoda folosește căutarea unui separator pentru graficul de descriere a ecuației, excluzând recursiv variabilele din două subsarcini separate una de cealaltă printr-un separator și apoi excluzând variabilele din separator [36] . Ocuparea acestei metode (numărul de coeficienți non-zero ai expansiunii Cholesky rezultate pentru o matrice) este O( n  log  n ) [37] [38] , ceea ce permite acestei metode să concureze cu metodele iterative pentru aceleași probleme [ 36] .

Klein, Moses și Weimann [39] au propus un algoritm de memorie liniară O( n log 2  n ) pentru găsirea celor mai scurte distanțe de la s pentru toate nodurile unui graf planar direcționat cu lungimi de arc pozitive și negative care nu conține cicluri negative. Algoritmul lor folosește separatori de grafice plane pentru a găsi o curbă Jordan C care trece prin O(√ n ) noduri (dar nu prin arce), astfel încât între n /3 și 2 n /3 noduri să fie în interiorul curbei (zona delimitată de curba închisă). C . Nodurile prin care trece curba C sunt noduri limită . Graficul original G este împărțit în două subgrafe G 0   și G 1 , tăind înglobarea plană de-a lungul curbei C și duplicând nodurile de limită. Pentru i =0 și 1, în G i   nodurile limită se află pe o față a  lui Fi .

O prezentare generală a acestei abordări este prezentată mai jos.

O parte importantă a acestui algoritm este utilizarea funcțiilor de preț și lungime redusă. Pentru un grafic direcționat G cu lungimi de arc ι(•), funcția de cost este funcția φ de la nodurile graficului G la numerele reale . Pentru un arc uv , lungimea redusă în raport cu φ este ιφ( uv )=ι( uv ) + φ( u ) − φ( v ). O funcție de cost admisibilă este o funcție care oferă lungimi reduse nenegative pe toate arcele lui G . Este util să convertiți o problemă cu calea cea mai scurtă care are atât lungimi de arc pozitive, cât și negative într-o problemă cu lungimi nenegative, ceea ce permite utilizarea algoritmului lui Dijkstra.

Paradigma divide-and-conquer bazată pe separator este, de asemenea, utilizată pentru a dezvolta structuri de date pentru algoritmi grafici dinamici [40] [41] și localizarea punctelor [42] , algoritmi de triangulare a poligoanelor [22] , cele mai scurte căi [ 43] [44] , pentru construirea grafurilor de vecin cel mai apropiat [45] și algoritmi de aproximare pentru găsirea mulțimii independente maxime pe grafurile plane [42] .

Soluția exactă a problemelor de optimizare NP-hard

Când se utilizează programarea dinamică pe descompunerea arborelui sau descompunerea ramurilor pentru un graf plan, multe clase de probleme de optimizare NP-hard pot fi rezolvate în timp exponențial, în funcție de √ n sau √ n  log  n . De exemplu, granițele de acest fel sunt cunoscute pentru căutarea de mulțimi independente maxime , arbori Steiner , cicluri hamiltoniene și pentru rezolvarea problemei vânzătorului ambulant pe grafice plane [46] . Metode similare folosind teoreme de partiționare pentru grafice geometrice pot fi folosite pentru a rezolva problema euclidiană a vânzătorului ambulant și pentru a construi un arbore Steiner în aceleași limite de timp [47] .

Pentru problemele parametrizate care permit reducerea parametrică care păstrează planaritatea și reduce fișierul de intrare la un nucleu cu o dimensiune care depinde liniar de parametru, această abordare poate fi utilizată pentru a construi algoritmi soluționați parametric fix al căror timp de execuție depinde polinomial pe dimensiunea graficului de intrare și exponențial în √ k , unde k  este un parametru al algoritmului. De exemplu, limitele de timp de rulare de acest fel sunt cunoscute pentru găsirea acoperirilor de vârfuri și seturi dominante de mărime k [48] [49] .

Algoritmi de aproximare

Lipton și Tarjan [42] au observat că teorema partiției poate fi utilizată pentru a deriva scheme de aproximare în timp polinomial pentru probleme de optimizare NP-hard pe grafice plane, cum ar fi găsirea mulțimii independente maxime . În special, prin trunchierea ierarhiei separatorilor într-un loc potrivit, se poate găsi un separator de dimensiune O( n /√log  n ), a cărui eliminare împarte graficul în subgrafe de dimensiune c  log  n pentru orice constantă c . Prin teorema celor patru culori , există o mulțime independentă de dimensiune de cel puțin n /4, astfel încât nodurile îndepărtate formează o mică fracțiune din mulțimea independentă maximă, iar mulțimile independente maxime din subgrafele rămase pot fi găsite independent în timp dependent exponențial. pe dimensiunea lor. Combinând această abordare cu metodele în timp liniar de construire a unei ierarhii separatoare [22] cu o căutare în tabel pentru a reduce timpul de căutare a mulțimilor independente în subgrafe izomorfe , se pot construi mulțimi independente care deviază de la cele optime cu un factor de 1 − O(1/√log  n ) în timp liniar. Totuși, pentru o eficiență garantată chiar mai aproape de 1 decât acest factor, abordarea ulterioară a lui Baker ( Baker 1994 ) (bazată pe descompunerea arborilor mai degrabă decât pe separatori plani) oferă un compromis mai bun între timp și calitatea aproximării.

Scheme similare de aproximare bazate pe construcția separatoarelor sunt folosite pentru a aproxima alte probleme dificile, cum ar fi problema acoperirii vârfurilor [50] [51] . Arora, Grigni, Karger, Klein și Voloshin [52] au folosit separatori într-un mod diferit pentru a aproxima problema vânzătorului ambulant pentru metrica cu calea cea mai scurtă pe graficele plane ponderate. Algoritmul lor folosește programarea dinamică pentru a găsi calea cea mai scurtă care, la fiecare nivel al ierarhiei separatorului, traversează separatorul de un număr limitat de ori. Ei au arătat că pe măsură ce limita numărului de intersecții crește, traseele astfel construite au o lungime care aproximează traseul optim.

Comprimarea graficului

Separatoarele sunt utilizate ca parte a algoritmilor de compresie a datelor pentru a reprezenta grafice plane și alte grafice separabile folosind un număr mic de biți. Principiul principal al acestor algoritmi este alegerea unui număr k și repartizarea graficului plan dat folosind separatori în O( n / k ) subgrafe de mărime de cel mult k , cu O( n /√ k ) vârfuri în separatori. Cu o alegere adecvată a lui k (proporțională maximă cu logaritmul lui n ), numărul de subgrafe plane neizomorfe cu k vârfuri este substanțial mai mic decât numărul de subgrafe din descompunere, astfel încât graficele pot fi comprimate prin construirea unui tabel cu toate posibilele subgrafe neizomorfe și reprezentând fiecare subgraf din descompunere printr-un indice din tabel. Restul graficului format din vârfurile separatorului poate fi reprezentat explicit sau cu o versiune recursivă a aceleiași structuri de date. Folosind această metodă, grafurile plane și familiile mai limitate de grafuri plane pot fi codificate folosind numărul optim de biți (în termeni de teoria informației ) - dacă există grafuri P n cu n vârfuri într-o familie de grafuri, atunci un graf individual din familia poate fi reprezentată folosind doar (1 + o( n ))log 2 P n biți [53] . De asemenea, se pot construi vederi de acest tip, în care se poate verifica adiacența nodurilor, se poate determina gradul unui vârf și se poate enumera vecinii vârfurilor în timp constant (pe interogare), prin extinderea tabelului subgraf cu informații suplimentare cu date corespunzătoare interogări [54] [55] .

Grafice universale

Un grafic universal pentru o familie de grafice F  este un grafic care conține orice element al familiei F ca subgraf. Separatorii pot fi folosiți pentru a arăta că graficele plane cu n vârfuri au un graf universal cu n vârfuri și O( n 3/2 ) muchii [56] .

Construcția folosește o formă mai puternică a teoremei partiției, în care dimensiunea celor trei submulțimi de vârfuri din partiție nu depinde de structura graficului - există un număr c , a cărui valoare este un factor constant mai mare decât √ n , astfel încât vârfurile oricărui graf plan cu n vârfuri pot fi împărțite în submulțimi A , S și B fără muchii de la A la B și cu dimensiuni | S | =  c , | A | = | b | = ( n  −  c )/2. Acest lucru poate fi demonstrat prin aplicarea în mod repetat a formei obișnuite a teoremei de partiționare la partițiile rezultate ale graficului până când toate componentele partiției sunt colectate în două subseturi, fiecare dintre ele având dimensiunea mai mică de n /2 vârfuri și apoi transferând vârfuri de la aceste submulțimi la separator până când acesta nu va avea dimensiunea dată.

Acum această teoremă poate fi utilizată pentru a obține o ierarhie separatoare pentru un graf plan cu n vârfuri, care este din nou independentă de structura graficului - descompunerea arborelui obținută din această ierarhie este lată de O(√ n ) și poate fi utilizată pentru orice grafic planar. Mulțimea tuturor perechilor de vârfuri din această descompunere arborescentă, în care fiecare dintre cele două vârfuri aparține unui nod comun al descompunerii arborescente, formează un grafic trivial perfect cu O( n 3/2 ) vârfuri, care conține orice grafic plan cu n vârfuri ca subgraf. O construcție similară arată că graficele plane de grad mărginit au grafice universale cu muchii O( n  log  n ), unde constanta ascunsă în notația O depinde de gradul graficului. Orice grafic universal pentru grafice plane (sau chiar pentru arbori de grad nemărginit) trebuie să aibă muchii Ω( n  log  n ), dar rămâne necunoscut dacă această limită inferioară sau limita superioară O( n 3/2 ) este clară pentru graficele universale ale grafice plane arbitrare [56] .

Vezi și

Note

  1. ↑ 1 2 Alon, Seymour, Thomas, 1990 .
  2. ↑ 1 2 3 Djidjev, 1982 .
  3. ↑ George, 1973 . În loc să folosească rânduri și coloane ca separator pentru a împărți graficul, George folosește uniunea lor și împarte graficul în patru părți.
  4. ↑ 1 2 3 4 Lipton, Tarjan, 1979 .
  5. ↑ Holzer, Schulz, Wagner, Prasinos, Zaroliagis, 2009 .
  6. ↑ 12 Miller , 1986 .
  7. ↑ 1 2 Alon, Seymour, Thomas, 1994 .
  8. ↑ Djidjev, Venkatesan, 1997 .
  9. ↑ 1 2 3 Gazit, Miller, 1990 .
  10. ↑ 1 2 3 4 5 6 7 Miller, Teng, Thurston, Vavasis, 1997 .
  11. ↑ Pach, Agarwal, 1995 .
  12. ^ Eppstein , Miller, Teng, 1995 .
  13. ↑ Spielman, Teng (1996 ).
  14. ↑ Spielman, Teng, 1996 .
  15. ↑ Gremban, Miller, Teng, 1997 .
  16. ↑ Har-Peled, 2011 .
  17. ↑ Donath, Hoffman, 1972 .
  18. ↑ Fiedler, 1973 .
  19. ↑ Spielman, Teng, 2007 .
  20. ↑ Miller ( Miller 1986 ) a demonstrat acest rezultat pentru grafurile plane cu două conexiuni, în timp ce Diks, Djidjev, Sýkora, Vrt'o (1993 ) au extins rezultatul la toate grafurile plane.
  21. ↑ Papadimitriou, Sideri, 1996 .
  22. ↑ 1 2 3 Goodrich, 1995 .
  23. ↑ Seymour, Thomas, 1994 .
  24. ↑ Fomin, Thilikos, 2006a .
  25. ↑ Erdős, Graham, Szemerédi, 1976 .
  26. ↑ Iordania, 1869 .
  27. ↑ Gilbert, Hutchinson, Tarjan, 1984 .
  28. ↑ Sýkora, Vrt'o, 1993 .
  29. ↑ Kawarabayashi, Reed, 2010 . Lucrări anterioare privind separatorii familiilor minore închise - Alon, Seymour, Thomas, 1990 ; Plotkin, Rao, Smith, 1994 ; Reed, Wood, 2009 .
  30. ↑ Miller, Teng, Thurston, Vavasis, 1998 .
  31. ↑ Wulff-Nilsen, 2009 .
  32. ↑ Łącki, Sankowski, 2011 .
  33. ↑ Chang, Lu, 2011 .
  34. ↑ Frederickson, 1987 , p. 1004-1022.
  35. ↑ Henzinger, Klein, Rao, Subramanian, 1997 .
  36. ↑ 12 George, 1973 .
  37. ↑ Lipton, Rose, Tarjan, 1979 .
  38. ↑ Gilbert, Tarjan, 1986 .
  39. ↑ Klein, Mozes, Weimann, 2009 .
  40. ↑ Eppstein, Galil, Italiano, Spencer, 1996 .
  41. ↑ Eppstein, Galil, Italiano, Spencer, 1998 .
  42. ↑ 1 2 3 Lipton, Tarjan, 1980 .
  43. ↑ Klein, Rao, Rauch, Subramanian, 1994 .
  44. ↑ Tazari, Müller-Hannemann, 2009 .
  45. ↑ Frieze, Miller, Teng, 1992 .
  46. ↑ Berna, 1990 ; Deĭneko, Klinz, Woeginger, 2006 ; Dorn, Penninkx, Bodlaender, Fomin, 2005 ; Lipton, Tarjan, 1980 .
  47. ↑ Smith, Wormald, 1998 .
  48. ↑ Alber, Fernau, Niedermeier, 2003 .
  49. ↑ Fomin, Thilikos, 2006b .
  50. ↑ Bar-Yehuda, Even, 1982 .
  51. ↑ Chiba, Nishizeki, Saito, 1981 .
  52. ↑ Arora, Grigni, Karger, Klein, Woloszyn, 1998 .
  53. ↑ He, Kao, Lu, 2000 .
  54. ↑ Blandford, Blelloch, Kash, 2003 .
  55. ↑ Blelloch, Farzan, 2010 .
  56. ↑ 1 2 Babai, Chung, Erdős, Graham, Spencer, 1982 ; Bhatt, Chung, Leighton, Rosenberg, 1989 ; Chung, 1990 .

Literatură