Síla grafu - Strength of a graph
Síla grafu: příklad | |
---|---|
![]() Graf se silou 2: graf je zde rozložen na tři části se 4 hranami mezi částmi, což dává poměr 4 / (3-1) = 2. | |
Tabulka grafů a parametrů |
V oboru matematika volala teorie grafů, síla neorientovaného graf odpovídá minimálnímu poměru okraje odstraněny/vytvořené komponenty při rozkladu dotyčného grafu. Je to metoda výpočtu oddíly množiny vrcholů a detekovat zóny s vysokou koncentrací hran, a je analogický k houževnatost grafu který je definován podobně pro odstranění vrcholů.
Definice
The síla neorientovaného jednoduchý graf G = (PROTI, E) připouští tři následující definice:
- Nechat být množinou všeho oddíly z , a být množina hran překračujících sady přepážky , pak .
- Také pokud je množina všech klenutých stromů G, pak
- A díky dualitě lineárního programování
Složitost
Výpočet síly grafu lze provést v polynomiálním čase a první takový algoritmus objevil Cunningham (1985). Algoritmus s nejlepší složitostí pro výpočet přesné síly je způsoben Trubinem (1993), využívá tokový rozklad Goldberga a Raa (1998), v čase .
Vlastnosti
- Li je jeden oddíl, který maximalizuje, a pro , je omezení G do sady , pak .
- Věta Tutte-Nash-Williams: je maximální počet hranových disjunktních stromů, které mohou být obsaženy v G.
- Na rozdíl od grafický oddíl Problém, výstup oddílů výpočtem síly nemusí být nutně vyvážený (tj. téměř stejné velikosti).
Reference
- W. H. Cunningham. Optimální útok a posílení sítě, J z ACM, 32: 549–561, 1985.
- A. Schrijver. Kapitola 51. Kombinatorická optimalizace, Springer, 2003.
- V. A. Trubin. Síla grafu a balení stromů a větví, „Cybernetics and Systems Analysis, 29: 379–384, 1993.