Siła wykresu

Siła wykresu: przykład
Wykres o sile 2: wykres jest tutaj rozłożony na trzy części, z 4 krawędziami między częściami, co daje stosunek 4/(3-1)=2.
Tabela wykresów i parametrów

W gałęzi matematyki zwanej teorią grafów siła grafów nieskierowanych odpowiada minimalnemu stosunkowi usuniętych krawędzi do składowych utworzonych w dekompozycji danego grafu. Jest to metoda obliczania podziałów zbioru wierzchołków i wykrywania stref o dużej koncentracji krawędzi i jest analogiczna do twardości grafu , która jest definiowana podobnie do usuwania wierzchołków.

Definicje

Siła nieskierowanego prostego wykresu $G)}$ V , mi ) dopuszcza trzy następujące definicje: ( sol ) { \ Displaystyle \ sigma (

• Niech ${\ Displaystyle \ Pi}$ będzie zbiorem wszystkich przegród i będzie $zbiorem$$\ pi$$} styl wyświetlania \pi \in \Pi }$ zbiory przegrody , wtedy ${\ Displaystyle \ Displaystyle \ sigma (G) = \ min _ {\ pi \ w \ Pi}} {\ Frac {|\ częściowe \ pi |}}}$ .
• Również jeśli jest zbiorem wszystkich drzew rozpinających G , to ${\ displaystyle {\ mathcal {T}}}$

${\ Displaystyle \ sigma (G) = \ max \ lewo \ {\ suma _ {T \ in {\ mathcal {T}}} \ lambda _ {T} \: \ \ forall T \ in {\ mathcal {T} }\ \lambda _{T}\geq 0{\mbox{ i }}\forall e\in E\ \sum _{T\ni e}\lambda _{T}\leq 1\right\}.}$

• I przez dualność programowania liniowego,

${\ Displaystyle \ sigma (G) = \ min \ lewo \ {\ suma _ {e \ in E} y_ {e} \ : \ \ forall e \ in E \ y_ {e} \ geq 0 {\ mbox {i }}\forall T\in {\mathcal {T}}\ \sum _{e\in E}y_{e}\geq 1\right\}.}$

Złożoność

Obliczenie siły grafu można wykonać w czasie wielomianowym, a pierwszy taki algorytm odkrył Cunningham (1985). Algorytm o największej złożoności do dokładnego obliczenia siły pochodzi od Trubina (1993), wykorzystuje rozkład przepływu Goldberga i Rao (1998) w czasie ${\ Displaystyle O (\ min ({\ sqrt {m}}, n ^ {2/3}) mn \ log (n ^ {2} / m + 2)}}$ .

Nieruchomości

• Jeśli ${\ Displaystyle \ pi = \ {V_ {1}, \ kropki, V_ {k} \}}$ to jedna partycja, która maksymalizuje, i dla ${\ Displaystyle i \ in \ {1, \ kropki, k \}}$ sol $\ Displaystyle G_ {i} = G / V_ {i}}$ jest ograniczeniem G do zbioru ${\ displaystyle V_ {i}}$$sigma (G_ {k}) \ geq \ sigma (G)}$ sol .
• Twierdzenie Tutte-Nasha-Williamsa: ${\ Displaystyle \ lfloor \ sigma (G) \ rfloor}$ to maksymalna liczba rozłącznych krawędziowo drzew rozpinających, które mogą być zawarte w G .
• W przeciwieństwie do problemu podziału grafu , wyniki podziału wynikające z obliczenia siły niekoniecznie są zrównoważone (tj. prawie równej wielkości).

• WH Cunninghama. Optymalny atak i wzmocnienie sieci, J of ACM, 32: 549–561, 1985.
• A. Schrijvera . Rozdział 51. Optymalizacja kombinatoryczna, Springer, 2003.
• VA Trubin. Siła wykresu i upakowanie drzew i gałęzi, Cybernetics and Systems Analysis, 29:379–384, 1993.