Styrkan hos en graf

Styrka av en graf: exempel
En graf med styrka 2: grafen är här uppdelad i tre delar, med 4 kanter mellan delarna, vilket ger förhållandet 4/(3-1)=2.
Tabell över grafer och parametrar

Inom den gren av matematiken som kallas grafteori , motsvarar styrkan hos en oriktad graf det minsta förhållandet som avlägsnas / komponenter som skapas i en nedbrytning av grafen i fråga. Det är en metod för att beräkna partitioner av uppsättningen av hörn och detektera zoner med hög koncentration av kanter, och är analog med grafens seghet som definieras på liknande sätt för borttagning av vertex.

Definitioner

Styrkan σ $(G)}$ sigma för en oriktad enkel graf G = ( V , E tillåter de tre följande definitionerna:

• Låt $\Pi$ vara mängden av alla partitioner av $V$ , och $\partial \pi$ vara mängden kanter som korsar uppsättningarna av partitionen ${\ displaystyle \pi \in \Pi }$ , då $\displaystyle \sigma (G)=\min _{\pi \in \Pi }{\frac {|\partial \pi |}{|\pi |-1}}$ .
• Även om ${\mathcal {T}}$ är mängden av alla spännande träd i G , då

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

• Och genom linjär programmeringsdualitet,

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

Komplexitet

Att beräkna styrkan hos en graf kan göras i polynomtid, och den första sådana algoritmen upptäcktes av Cunningham (1985). Algoritmen med bäst komplexitet för att beräkna exakt styrkan beror på Trubin (1993), använder flödessönderdelningen av Goldberg och Rao (1998), i tiden O $O(\min({\sqrt {m}},n^{2/3})mn\log(n^{2}/m+2))$ .

Egenskaper

• Om $\pi =\{V_{1},\dots ,V_{k}\}$ är en partition som maximerar, och för $i\in \{1,\dots ,k\}$ , $G_{i}=G/V_{i}$ begränsningen av G till mängden $V_{i}$ , sedan $\sigma (G_{k})\geq \sigma (G)$ .
• Tutte-Nash-Williams sats: $\lfloor \sigma (G)\rfloor$ är det maximala antalet kant-disjunkta spännande träd som kan finnas i G .
• I motsats till grafpartitionsproblemet är partitionerna som matas ut genom att beräkna styrkan inte nödvändigtvis balanserade (dvs. nästan lika stora).

• WH Cunningham. Optimal attack och förstärkning av ett nätverk, J of ACM, 32:549–561, 1985.
• A. Schrijver . Kapitel 51. Combinatorial Optimization, Springer, 2003.
• VA Trubin. Styrka av en graf och packning av träd och förgreningar, , Cybernetics and Systems Analysis, 29:379–384, 1993.