Výkon grafu

Mohutnost neorientovaného grafu je charakteristika grafu rovna minimálnímu poměru počtu hran odstraněných z grafu k počtu složek získaných v důsledku takového odstranění (sníženo o 1). Tato metoda umožňuje identifikovat oblasti s vysokou koncentrací hran. Mohutnost grafu je podobná konceptu tuhosti grafu , která je však určena postupem pro odstranění vrcholů, nikoli hran.

Definice

Mohutnost neorientovaného jednoduchého grafu lze definovat třemi ekvivalentními způsoby: $\sigma (G)$ $G=(V,E)$

Dovolit být soubor všech oddílů souboru . Pro dělení označme jako množinu hran spojujících vrcholy z různých komponent . Pak . $\Pí$ $PROTI$ $\pi \in \Pi$ $\partial \pi$ $\pi$ $\displaystyle \sigma (G)=\min _{\pi \in \Pi }{\frac {|\částečné \pi |}{|\pi |-1))$
Dovolit je množina všech kostry grafu . Pak ${\mathcal {T}}$ $G$

\sigma (G)=\max \left\{\součet _{T\in {\mathcal {T))}\lambda _{T}\ :\ \forall T\in {\mathcal {T} }\ \lambda _{T}\geqslant 0;\forall e\in E\ \sum _{T\ni e}\lambda _{T}\leqslant 1\right\}.

Podle duality lineárního programování

\sigma (G)=\min \left\{\součet _{e\in E}y_{e}\ :\ \forall e\in E\ y_{e}\geqslant 0;\forall T\ v {\mathcal {T}}\ \součet _{e\in E}y_{e}\geqslant 1\right\}.

Obtížnost

Výpočet mohutnosti grafu lze provést v polynomiálním čase. První polynomiální algoritmus objevil Cunningham (1985). Algoritmus pro výpočet výkonu s nejlepší složitostí podle Trubina (1993) používá rozklad toku podle Goldberga a Raa (1998) a běží v čase . $O(\min({\sqrt {m)),n^{2/3})mn\log(n^{2}/m+2))$

Vlastnosti

Jestliže je oddíl maximalizující poměr a for je omezení grafu G na množinu , pak . $\pi =\{V_{1},\tečky ,V_{k}\}$ ${\displaystyle i\in \{1,\tečky ,k\))$ $G_{i}=G/V_{i}$ $V_i$ $\sigma (G_{k})\geqslant \sigma (G)$
Tutt-Nash-Williamsova věta: je maximální počet hranově disjunktních překlenovacích stromů, které mohou být obsaženy v G . $\lfloor \sigma (G)\rfloor$
Na rozdíl od problému rozdělení grafu nejsou výsledné výpočty mohutnosti rozdělení nutně vyvážené (tj. téměř stejné velikosti).

Literatura

Cunningham WH Optimální útok a posílení sítě // J of ACM. - 1985. - Vydání. 32 . - S. 549-561 .
Alexander Schrijver. Kapitola 51 // Kombinatorická optimalizace. Mnohostěny a účinnost . - Springer, 2003. - ISBN 978-3-540-44389-6 .
Trubin VA Síla grafu a uspořádání stromů a větví // Kybernetika a systémová analýza. - 1993. - Vydání. 29 . - S. 379-384 .