Content deleted Content added
Preposition. |
|||
(32 intermediate revisions by 16 users not shown) | |||
Line 1:
{{Short description|Graph-theoretic connectivity parameter}}
{{infobox graph
| name = Strength of a graph: example
Line 5 ⟶ 6:
}}
In
== Definitions ==
The '''strength''' <math>\sigma(G)</math> of an undirected [[
* Let <math>\Pi</math> be the set of all [[
* Also if <math> \mathcal T</math> is the set of all spanning trees of ''G'', then
:: <math>\sigma(G)=\max\left\{\sum_{T\in\mathcal T}\lambda_T\ :\ \forall T\in {\mathcal T}\ \lambda_T\geq 0\mbox{ and }\forall e\in E\ \sum_{T\ni e}\lambda_T\leq1\right\}.</math> * And by linear programming duality,
:: <math>\sigma(G)=\min\left\{\sum_{e\in E}y_e\ :\ \forall e\in E\ y_e\geq0\mbox{ and }\forall T\in {\mathcal T}\ \sum_{e\in E}y_e\geq1\right\}.</math> == Complexity ==
Line 21 ⟶ 23:
was discovered by Cunningham (1985). The algorithm with best complexity for computing exactly the strength is due to Trubin (1993), uses the flow decomposition of Goldberg and Rao (1998), in time <math>O(\min(\sqrt{m},n^ {2/3})mn\log(n^2/m+2))</math>.
==
* If <math>\pi=\{V_1,\dots,V_k\}</math> is one partition that maximizes, and for <math> i\in\{1,\dots,k\}</math>, <math>G_i=G/V_i</math> is the restriction of ''G'' to the set <math>V_i</math>, then <math>\sigma(G_k)\geq\sigma(G)</math>.
* The Tutte-Nash-Williams theorem: <math>\lfloor\sigma(G)\rfloor</math> is the maximum number of edge-disjoint spanning trees that can be contained in ''G''.
* Contrary to the [[graph partition]] problem, the partitions output by computing the strength are not necessarily balanced (i.e. of almost equal size).
== References ==
*
*[[Alexander Schrijver|A. Schrijver]]. Chapter 51. [
*V. A. Trubin. [https://doi.org/10.1007%2FBF01125543 ''Strength of a graph and packing of trees and branchings,''], Cybernetics and Systems Analysis, 29:379–384, 1993.
▲* W. H. Cunningham. [http://portal.acm.org/citation.cfm?id=3829 ''Optimal attack and reinforcement of a network''], J of ACM, 32:549-561, 1985.
▲* A. Schrijver. Chapter 51. [http://www.springer.com/math/applications/book/978-3-540-44389-6 ''Combinatorial Optimization,''] Springer, 2003.
▲[[Category:Graph theory]]
[[Category:Graph invariants]]
|