Blackberry (teoria graficelor)

În teoria grafurilor, o mură pentru un graf nedirecționat G este o familie de subgrafe conectate ale unui graf G care se ating între ele: pentru orice pereche de subgrafe care nu au vârfuri comune, trebuie să existe o muchie ale cărei vârfuri de capăt se află în aceste două. subgrafe. Ordinea murului este cea mai mică dimensiune a mulțimii de vârfuri G care are o intersecție nevidă cu fiecare subgraf al murului. Murele sunt folosite pentru a descrie lățimea arborelui unui grafic G [1] .

Latimea si capacul lemnului

O acoperire de ordinul k într-un grafic G este o funcție β care preia fiecare mulțime X cu mai puțin de k vârfuri într-o componentă conexă G - X în așa fel încât oricare două submulțimi β ( X ) și β ( Y ) să se atingă reciproc . Adică, imaginile lui β formează o mură cu ordinul k în G . În schimb, orice mură poate fi folosită pentru a crea un adăpost - pentru fiecare set X mai mic decât ordinul murului, există o singură componentă conectată β ( X ) care conține toate subgrafele din mur care nu sunt conectate la X .

După cum au arătat Seymour și Thomas , ordinea unei mure (sau, în mod echivalent, adăpost) descrie lățimea arborelui —un grafic are o mură de ordinul k dacă și numai dacă lățimea arborelui este de cel puțin k − 1 [1] .

Dimensiunea murelor

După cum au observat Grohe și Marx, expansoarele de grade mărginite au o lățime a arborelui proporțională cu numărul de vârfuri și pentru a include toate subgrafele care nu împărtășesc vârfuri cu fiecare subset de acea dimensiune, blackberry pentru astfel de grafice trebuie să conțină exponențial multe subgrafe distincte. Mai exact, pentru aceste grafice, chiar și acele mure a căror ordine este puțin mai mare decât rădăcina pătrată a lățimii arborelui trebuie să aibă dimensiune exponențială. Cu toate acestea, Groh și Marx au arătat, de asemenea, că orice grafic cu lățimea arborelui k are un mărăcini de mărime și ordine polinomiale [2] . $\Omega (k^{1/2}/\log ^{2}k)$

Complexitate computațională

Deoarece mărăcinile pot avea dimensiuni exponențiale, nu este întotdeauna posibil să le construiți în timp polinomial pentru grafice cu lățime nelimitată a arborelui. Totuși, dacă lățimea arborelui este limitată, timpul de construcție polinomic este posibil - este posibil să găsim o mură de ordinul k , dacă există una, în timp , unde n este numărul de vârfuri din grafic. Algoritmi chiar mai rapizi sunt posibili pentru graficele cu un număr mic de separatori minimi [3] . $O(n^{k+2})$

Bodlender, Grigoriev și Coster [4] au studiat algoritmi euristici pentru găsirea murelor de ordin înalt. Metodele lor nu au dat întotdeauna mure cu o ordine apropiată de lățimea arborelui, dar pentru graficele plane dau un factor de aproximare constant . Kreutzer și Tazari [5] propun algoritmi de căutare probabilistică în timp polinomial pe grafice cu lățimea arborelui k mrăzuni de mărime și ordine polinomului , care corespunde factorului de ordine logaritmică derivat de Grohe și Marx ( Grohe, Marx 2009 ) pentru existența mrăznilor de polinom. mărimea. $\Omega (k^{1/2}/\log ^{3}k)$

Link -uri

↑ 1 2 Paul D. Seymour, Robin Thomas. Căutare de grafice și o teoremă min-max pentru lățimea arborelui // Journal of Combinatorial Theory . - 1993. - T. 58 , nr. 1 . — S. 22–33 . - doi : 10.1006/jctb.1993.1027 . . În acest articol, murele sunt numite „ecrane”, iar comenzile lor sunt numite „grosime”.
↑ Martin Grohe, Daniel Marx. Despre lățimea copacului, mărimea mărăcinilor și extinderea // Journal of Combinatorial Theory . - 2009. - T. 99 , nr. 1 . — S. 218–228 . - doi : 10.1016/j.jctb.2008.06.004 . .
↑ Mathieu Chapelle, Frédéric Mazoit, Ioan Todinca. Mathematical Foundations of Computer Science 2009: 34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovacia, 24-28 august 2009, Proceedings. - Berlin: Springer, 2009. - T. 5734. - S. 223-234. - doi : 10.1007/978-3-642-03816-7_20 . .
↑ Bodlaender. Limitele inferioare ale lățimii copacului cu mrăcini. - algoritmică . - 2008. - T. 51. - S. 81–98. - doi : 10.1007/s00453-007-9056-z . .
↑ Stephan Kreutzer, Siamak Tazari. Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10). - 2010. - S. 354-364. .