Rezistența unui grafic

Rezistența unui grafic (exemplu)
Un grafic al forței 2: graficul este descompus în trei părți cu un total de 4 muchii între componente, ceea ce dă raportul 4 / (3-1) = 2.

În teoria graficelor , puterea unui grafic ( strength engleză) nedirecționat este cel mai mic raport dintre numărul de muchii șterse și numărul de componente create într-o descompunere a graficului.

Definiție

Fie un grafic neorientat . Fie setul de partiții de , și, pentru orice partiție , sau setul de muchii care conectează părți ale peretelui despărțitor . Punctul forte este: $G = (V, E)$ ${\ displaystyle {\ cal {P}}}$ $V$ ${\ displaystyle P \ in {\ cal {P}}}$ ${\ displaystyle \ delta (P)}$ $P$ ${\ displaystyle \ sigma (G)}$

{\ displaystyle \ sigma (G) = \ min _ {P \ in {\ cal {P}}} {\ frac {| \ delta (P) |} {| P | -1}}}

Pentru o partiție de vârfuri, este setul tuturor marginilor care leagă părțile partiției. Pentru a exista cel puțin o margine între două componente, trebuie să alegeți marginile în mod corespunzător; forța este raportul mai mic dintre cele două numere întregi. $P$ ${\ displaystyle \ delta (P)}$ ${\ displaystyle | \ delta (P) |}$ ${\ displaystyle | \ delta (P) | -1}$

Pentru formulare în programarea liniară , avem definiții echivalente: Să set de copaci care acoperă G . Asa de ${\ mathcal T}$

{\ displaystyle \ sigma (G) = \ max \ sum _ {T \ in {\ mathcal {T}}} \ lambda _ {T} \ quad}

cu constrângerile: și .

{\ displaystyle \ \ lambda _ {T} \ geq 0 \}

{\ displaystyle \ \ sum _ {T \ ni e} \ lambda _ {T} \ leq 1}

sau, prin dualitate în programarea liniară :

{\ displaystyle \ sigma (G) = \ min \ sum _ {e \ in E} y_ {e} \ quad}

cu constrângerile: și .

{\ displaystyle \ y_ {e} \ geq 0 \}

{\ displaystyle \ \ sum _ {e \ în E} y_ {e} \ geq 1}

Complexitatea calculului

Calculul forței unui grafic se poate face în timp polinomial ; primul astfel de algoritm a fost descris de Cunningham în 1985. Algoritmul cu cea mai bună complexitate se datorează lui Trubin (1993); utilizând descompunerea fluxurilor Goldberg și Rao (1998), este în timp complexitatea unui grafic cu n vârfuri și m muchii. ${\ displaystyle O (\ min (m ^ {1/2}, n ^ {2/3}) mn \ log (n ^ {2} / m + 2))}$

Proprietăți

Fie un grafic nedirectat, cât și un număr întreg pozitiv. Dimensiunea maximă a unei uniuni forestiere este egală cu cea mai mică valoare a $G = (V, E)$ $k$ $k$

{\ displaystyle | \ delta (P) | + k (| V | - | P |)}

luate pe toate partițiile din .

P

V

Dacă este o partiție care maximizează și dacă este restricția lui G la set , atunci . ${\ displaystyle P = \ {V_ {1}, \ dots, V_ {k} \}}$ ${\ displaystyle \ sigma (G)}$ ${\ displaystyle G_ {i} = G | V_ {i}}$ $V_i$ ${\ displaystyle \ sigma (G_ {k}) \ geq \ sigma (G)}$
Teorema tuturor-Nash-Williams. - Un grafic conține k copaci care se întind cu margini disjuncte dacă și numai dacă $G = (V, E)$

{\ displaystyle | \ delta (P) | \ geq k (| P | -1)}

pentru orice partiție a .

P

V

Teorema Tutte-Nash-Williams este exprimată cu noțiunea de forță: este numărul maxim de copaci care acoperă marginile disjuncte care pot fi conținute în G. ${\ displaystyle \ lfloor \ sigma (G) \ rfloor}$
Spre deosebire de problema partiționării unui grafic , partițiile produse prin calculul forței nu sunt neapărat echilibrate (adică nu sunt de dimensiuni aproape egale).

Note și referințe

(fr) Acest articol este preluat parțial sau în totalitate din articolul din Wikipedia engleză intitulat „ Forța unui grafic ” ( vezi lista autorilor ) .

(în) William H. Cunningham , „ Atac optim și întărire a unei rețele ” , Jurnalul ACM , vol. 32, n o 3,Iulie 1985, p. 549-561 ( ISSN 0004-5411 și 1557-735X , DOI 10.1145 / 3828.3829 , citit online , accesat la 10 martie 2021 )
Goldberg și Rao 1998 .
Shrijver 2003 , (Teorema 51.1).
Shrijver 2003 , (Corolarul 51.1a).

Bibliografie

Alexander Schrijver , Optimizare combinatorie , Springer,2003( ISBN 978-3-540-44389-6 ) , capitolul 51.
William H. Cunningham, „ Atac optim și întărire a unei rețele ”, Jurnalul ACM , vol. 32, n o 3,1985, p. 549-561 ( DOI 10.1145 / 3828.3829 )
VA Trubin, „ Rezistența unui grafic și împachetarea copacilor și ramificațiilor ”, Cibernetică și Analiza sistemelor , vol. 29, n o 3,1993, p. 379–384 ( DOI 10.1007 / BF01125543 )
Andrew V. Goldberg și Satish Rao , „ Dincolo de bariera de descompunere a fluxului ”, Jurnalul ACM , vol. 45, nr . 5,1998, p. 783-797 ( DOI 10.1145 / 290179.290181 )

Articole similare

Duritatea unui grafic , un concept analog pentru ștergerile de vârf
Teorema Nash-Williams (ro)
Glosar al teoriei graficelor