Standard sea level: Difference between revisions

Revision as of 20:17, 3 May 2013

In the branch of mathematics called graph theory, the strength of an undirected graph corresponds to the minimum ratio edges removed/components created in a decomposition of the graph in question. It is a method to compute partitions of the set of vertices and detect zones of high concentration of edges.

Definitions

The strength $σ (G)$ of an undirected simple graph G = (V, E) admits the three following definitions:

Let $Π$ be the set of all partitions of $V$ , and $\partial π$ be the set of edges crossing over the sets of the partition $π \in Π$ , then $σ (G) = \min_{π \in Π} \frac{| \partial π |}{| π | - 1}$ .
Also if $𝒯$ is the set of all spanning trees of G, then

σ (G) = \max {\sum_{T \in 𝒯} λ_{T} : \forall T \in 𝒯 λ_{T} \geq 0 and \forall e \in E \sum_{T ∋ e} λ_{T} \leq 1} .

And by linear programming duality,

σ (G) = \min {\sum_{e \in E} y_{e} : \forall e \in E y_{e} \geq 0 and \forall T \in 𝒯 \sum_{e \in E} y_{e} \geq 1} .

Complexity

Computing the strength of a graph can be done in polynomial time, and the first such algorithm 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 $O (\min (\sqrt{m}, n^{2 / 3}) m n \log (n^{2} / m + 2))$ .

Properties

If $π = {V_{1}, \dots, V_{k}}$ is one partition that maximizes, and for $i \in {1, \dots, k}$ , $G_{i} = G / V_{i}$ is the restriction of G to the set $V_{i}$ , then $σ (G_{k}) \geq σ (G)$ .

The Tutte-Nash-Williams theorem: $⌊ σ (G) ⌋$ 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

W. H. Cunningham. Optimal attack and reinforcement of a network, J of ACM, 32:549–561, 1985.
A. Schrijver. Chapter 51. Combinatorial Optimization, Springer, 2003.
V. A. Trubin. Strength of a graph and packing of trees and branchings,, Cybernetics and Systems Analysis, 29:379–384, 1993.

@@ Line 1: / Line 1: @@
-They're always ready to help, and they're always making changes to the site to make sure you won't have troubles in the first place. The next step is to visit your Word - Press blog dashboard. Wordpress Content management systems, being customer friendly, can be used extensively to write and manage websites and blogs. s ultimately easy to implement and virtually maintenance free. All this is very simple, and the best thing is that it is totally free, and you don't need a domain name or web hosting. <br><br>If you are you looking for more info regarding [http://www.nt-protect.host.sk/?backup_plugin_566749 wordpress backup plugin] review our website. Any business enterprise that is certainly worth its name should really shell out a good deal in making sure that they have the most effective website that provides related info to its prospect. WPTouch is among the more well known Word - Press smartphone plugins which is currently in use by thousands of users. With the free Word - Press blog, you have the liberty to come up with your own personalized domain name. E-commerce websites are meant to be buzzed with fresh contents, graphical enhancements, and functionalities. You can also get a free keyword tool that is to determine how strong other competing sites are and number of the searches on the most popular search sites. <br><br>This gives a clearer picture that online shoppers are familiar with the WP ecommerce system. s cutthroat competition prevailing in the online space won. all the necessary planning and steps of conversion is carried out in this phase, such as splitting, slicing, CSS code, adding images, header footer etc. Thousands of plugins are available in Word - Press plugin's library which makes the task of selecting right set of plugins for your website a very tedious task. Converting HTML to Word - Press theme for your website can allow you to enjoy the varied Word - Press features that aid in consistent growth your online business. <br><br>Word - Press has plenty of SEO benefits over Joomla and Drupal. As an example, if you are promoting a product that cures hair-loss, you most likely would not wish to target your adverts to teens. The templates are designed to be stand alone pages that have a different look and feel from the rest of your website. Giant business organizations can bank on enterprise solutions to incorporate latest web technologies such as content management system etc, yet some are looking for economical solutions. See a product, take a picture, and it gives you an Amazon price for that product, or related products. <br><br>Under Settings &mdash;> Reading, determine if posts or a static page will be your home page, and if your home page is a static page, what page will contain blog posts. Here's a list of some exciting Word - Press features that have created waves in the web development industry:. Word - Press can also be quickly extended however improvement API is not as potent as Joomla's. with posts or testimonials updated as they are uploaded to a particular section of the website. Press CTRL and the numbers one to six to choose your option.
+{{infobox graph
+ | name     = Strength of a graph: example
+ | image    = [[Image:Force-wiki.jpg|360px]]
+ | image_caption = A graph with strength 2: the graph is here decomposed into three parts, with 4 edges between the parts, giving a ratio of 4/(3-1)=2.
+}}
+In the branch of [[mathematics]] called [[graph theory]], the '''strength''' of an undirected [[graph (mathematics)|graph]] corresponds to the minimum ratio ''edges removed''/''components created'' in a decomposition of the graph in question. It is a method to compute [[Partition of a set|partitions]] of the set of vertices and detect zones of high concentration of edges.
+== Definitions ==
+The '''strength''' <math>\sigma(G)</math> of an undirected [[Graph_(mathematics)#Simple_graph|simple graph]] ''G''&nbsp;=&nbsp;(''V'',&nbsp;''E'') admits the three following definitions:
+* Let <math>\Pi</math> be the set of all [[Partition_of_a_set|partitions]] of <math>V</math>, and <math>\partial \pi</math> be the set of edges crossing over the sets of the partition <math>\pi\in\Pi</math>, then  <math>\displaystyle\sigma(G)=\min_{\pi\in\Pi}\frac{|\partial \pi|}{|\pi|-1}</math>.
+* 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 ==
+Computing the strength of a graph can be done in polynomial time, and the first such algorithm
+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>.
+== Properties ==
+* 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 ==
+*W. H. Cunningham. [http://portal.acm.org/citation.cfm?id=3829 ''Optimal attack and reinforcement of a network,''] J of ACM, 32:549&ndash;561, 1985.
+*[[Alexander Schrijver|A. Schrijver]]. Chapter 51. [http://www.springer.com/math/applications/book/978-3-540-44389-6 ''Combinatorial Optimization,''] Springer, 2003.
+*V. A. Trubin. [http://www.springerlink.com/content/t82kl33q358754n7/ ''Strength of a graph and packing of trees and branchings,''], Cybernetics and Systems Analysis, 29:379&ndash;384, 1993.
+[[Category:Graph connectivity]]
+[[Category:Graph invariants]]

Standard sea level: Difference between revisions

Revision as of 20:17, 3 May 2013

Contents

Definitions

Complexity

Properties

References

Navigation menu

Standard sea level: Difference between revisions

Revision as of 20:17, 3 May 2013

Definitions

Complexity

Properties

References

Navigation menu

Search