Separator de vârfuri (teoria graficelor)

În teoria grafurilor, o submulțime de vârfuri se numește separator de vârfuri pentru vârfuri neadiacente și , dacă eliminarea din grafic separă și în două componente conectate . $S\subset V$ $A$ $b$ $S$ $A$ $b$

Exemple

Să presupunem că având o rețea cu r rânduri și c coloane, atunci numărul total de n vârfuri este r*c . De exemplu, în figură, r = 5, c = 8 și n = 40. Dacă r este impar, există un rând central, altfel există două rânduri la fel de aproape de centru. În același mod, dacă c este impar, există o coloană centrală, în caz contrar există două coloane la fel de aproape de centru. Alegând unul dintre aceste rânduri sau coloane ca S și eliminând S din grafic, obținem o partiție a graficului în două subgrafe mai mici A și B conectate , fiecare dintre acestea conținând cel mult n / 2 vârfuri. Dacă r ≤ c (ca în ilustrație), atunci alegerea coloanei centrale va da un separator S cu r ≤ √ n vârfuri și, în mod similar, dacă c ≤ r , alegerea rândului central va da un separator cu cel mult √ n vârfuri . Astfel, orice graf-rețea are un separator S cu dimensiunea de cel mult √ n , a cărui îndepărtare împarte graficul în două componente conexe, fiecare având dimensiunea de cel mult n /2 [1] .

O altă clasă de exemple este un arbore liber T care are un separator cu un singur vârf S a cărui îndepărtare împarte T în două (sau mai multe) componente conectate, fiecare având dimensiunea de cel mult n /2. Mai exact, există exact unul sau două vârfuri, în funcție de faptul că arborele este centrat sau bicentrat [2] .

Spre deosebire de exemplele date, nu toate separatoarele de vârfuri sunt echilibrate , dar această proprietate este cea mai utilă pentru aplicațiile informatice.

Separatoare minime

Fie S un (a,b) -separator, adică o submulțime de vârfuri care separă două vârfuri neadiacente a și b . Atunci S este un (a,b)-separator minim dacă nicio submulțime a lui S nu separă a și b . O mulțime S se numește separator minim dacă este un separator minim pentru orice pereche (a,b) de vârfuri neadiacente. Mai jos este un rezultat binecunoscut privind caracterizarea separatorilor minimali [3] :

Lema. Un separator de vârfuri S în G este minim dacă și numai dacă graficul obținut prin eliminarea lui S din G are două componente conexe și astfel încât fiecare vârf din S este conectat la un vârf în și la un vârf în . $GS$ $C_{1}$ $C_{2}$ $C_{1}$ $C_{2}$

Separatoarele minime formează un sistem algebric : pentru două vârfuri fixe a și b ale unui graf dat G , un (a,b) -separator S poate fi considerat un predecesor al altui (a,b)-separator T dacă orice cale de la a la b lovește S înainte, decât pentru a ajunge la T . Mai strict, relația de precedență este definită după cum urmează: Fie S și T doi (a,b) -separatori în 'G'. Atunci S este predecesorul lui T , care este notat ca și cum, pentru orice vârf , orice cale între x și b conține un vârf din T . Din definiție rezultă că relația de precedență este o preordonare pe mulțimea tuturor (a,b) -separatorilor. Mai mult, Escalante [4] a demonstrat că relația de precedență devine o rețea completă dacă ne restrângem la mulțimea de separatoare minime (a,b) G . $S\sqsubseteq _{a,b}^{G}T$ $x\in S\setminus T$

Vezi și

Un graf cordal este un graf în care orice separator minim este o clică .

Note

↑ J. Alan George. Disecția imbricată a unei rețele obișnuite cu elemente finite // SIAM Journal on Numerical Analysis. - 1973. - T. 10 , nr. 2 . - S. 345-363 . - doi : 10.1137/0710032 . — . . În loc să folosească rândurile și coloanele graficului, George împarte graficul în patru părți combinând rândurile și coloanele ca separator.
↑ Camille Jordan. Sur les assemblages de lignes (franceză) // Journal für die reine und angewandte Mathematik . - 1869. - T. 70 , nr. 2 . - S. 185-190 .
↑ Martin Charles Golumbic. Teoria graficelor algoritmice și graficele perfecte. - Academic Press, 1980. - ISBN 0-12-289260-7 .
↑ F. Escalante. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. - 1972. - T. 38. - S. 199-220. - doi : 10.1007/BF02996932 .

Literatură

Arnold Rosenberg, Lenwood Heath. Separatoare grafice, cu aplicații. Springer. - 2002. - doi : 10.1007/b115747 .