Electrostriction

2013-04-23T21:44:00Z

82.181.86.60: Deleted some false information. Take for example terpolymers and you can harvest energy by straining electrostrictive elements. (Read http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1563285&tag=1 for instance)

[[Image:Graph cut edges.svg|thumb|200px|A graph with 6 bridges (highlighted in red)]]
[[Image:Undirected.svg|thumb|125px|An undirected connected graph with no cut edges]]

In [[graph theory]], a '''bridge''' (also known as a '''cut-edge''' or '''cut arc''' or an '''isthmus''') is an edge whose deletion increases the number of [[connected component (graph theory)|connected components]].<ref>{{citation
| last = Bollobás | first = Béla | author-link = Béla Bollobás
| doi = 10.1007/978-1-4612-0619-4
| isbn = 0-387-98488-7
| location = New York
| mr = 1633290
| page = 6
| publisher = Springer-Verlag
| series = Graduate Texts in Mathematics
| title = Modern Graph Theory
| url = http://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA6
| volume = 184
| year = 1998}}.</ref> Equivalently, an edge is a bridge if and only if it is not contained in any [[Cycle (graph theory)|cycle]]. A graph is said to be '''bridgeless''' if it contains no bridges.

==Trees and forests==
A graph with <math>n</math> nodes can contain at most <math>n-1</math> bridges, since adding additional edges must create a cycle. The graphs with exactly <math>n-1</math> bridges are exactly the [[tree (graph theory)|trees]], and the graphs in which every edge is a bridge are exactly the [[forest (graph theory)|forests]].

In every undirected graph, there is an [[equivalence relation]] on the vertices according to which two vertices are related to each other whenever there are two edge-disjoint paths connecting them. (Every vertex is related to itself via two length-zero paths, which are identical but nevertheless edge-disjoint.) The equivalence classes of this relation are called '''2-edge-connected components''', and the bridges of the graph are exactly the edges whose endpoints belong to different components. The '''bridge-block tree''' of the graph has a vertex for every nontrivial component and an edge for every bridge.<ref>{{citation
| last1 = Westbrook | first1 = Jeffery | author1-link = Jeff Westbrook
| last2 = Tarjan | first2 = Robert E. | author2-link = Robert Tarjan
| doi = 10.1007/BF01758773
| issue = 5-6
| journal = Algorithmica
| mr = 1154584
| pages = 433–464
| title = Maintaining bridge-connected and biconnected components on-line
| volume = 7
| year = 1992}}.</ref>

==Relation to vertex connectivity==
Bridges are closely related to the concept of [[Articulation vertex|articulation vertices]], vertices that belong to every path between some pair of other vertices. The two endpoints of a bridge are articulation vertices unless they have a degree of 1, although it may also be possible for a non-bridge edge to have two articulation vertices as endpoints. Analogously to bridgeless graphs being 2-edge-connected, graphs without articulation vertices are [[k-vertex-connected graph|2-vertex-connected]].

In a [[cubic graph]], every cut vertex is an endpoint of at least one bridge.

==Bridgeless graphs==
A '''bridgeless graph''' is a graph that does not have any bridges. Equivalent conditions are that each [[Connected component (graph theory)|connected component]] of the graph has an [[ear decomposition|open ear decomposition]],<ref name="robbins39">{{citation
| last = Robbins | first = H. E. | authorlink = Herbert Robbins
| journal = [[The American Mathematical Monthly]]
| pages = 281–283
| title = A theorem on graphs, with an application to a problem of traffic control
| volume = 46
| year = 1939}}.</ref> that each connected component is [[K-edge-connected graph|2-edge-connected]], or (by [[Robbins' theorem]]) that every connected component has a [[strong orientation]].<ref name="robbins39"/>

An important open problem involving bridges is the [[cycle double cover conjecture]], due to [[Paul Seymour (mathematician)|Seymour]] and [[George Szekeres|Szekeres]] (1978 and 1979, independently), which states that every bridgeless graph admits a set of simple cycles which contains each edge exactly twice.<ref>{{citation
| last = Jaeger | first = F.
| contribution = A survey of the cycle double cover conjecture
| doi = 10.1016/S0304-0208(08)72993-1
| pages = 1–12
| series = North-Holland Mathematics Studies
| title = Annals of Discrete Mathematics 27 – Cycles in Graphs
| volume = 27
| year = 1985}}.</ref>

==Tarjan's Bridge-finding algorithm==
The first [[linear time]] algorithm for finding the bridges in a graph was described by [[Robert Tarjan]] in 1974.<ref>{{citation
| last = Tarjan | first = R. Endre | author-link = Robert Tarjan
| doi = 10.1016/0020-0190(74)90003-9
| issue = 6
| journal = Information Processing Letters
| mr = 0349483
| pages = 160–161
| title = A note on finding the bridges of a graph
| volume = 2}}.</ref> It performs the following steps:
* Find a [[spanning forest]] of <math>G</math>
* Create a rooted forest <math>F</math> from the spanning tree
* Traverse the forest <math>F</math> in [[Tree traversal|preorder]] and number the nodes. Parent nodes in the forest now have lower numbers than child nodes.
* For each node <math>v</math> in preorder, do:
** Compute the number of forest descendants <math>ND(v)</math> for this node, by adding one to the sum of its children's descendants.
** Compute <math>L(v)</math>, the lowest preorder label reachable from <math>v</math> by a path for which all but the last edge stays within the subtree rooted at <math>v</math>. This is the minimum of the set consisting of the values of <math>L(w)</math> at child nodes of <math>v</math> and of the preorder labels of nodes reachable from <math>v</math> by edges that do not belong to <math>F</math>.
** Similarly, compute <math>H(v)</math>, the highest preorder label reachable by a path for which all but the last edge stays within the subtree rooted at <math>v</math>. This is the maximum of the set consisting of the values of <math>H(w)</math> at child nodes of <math>v</math> and of the preorder labels of nodes reachable from <math>v</math> by edges that do not belong to <math>F</math>.
** For each node <math>w</math> with parent node <math>v</math>, if <math>L(w) = w</math> and <math>H(w) < w + ND(w)</math> then the edge from <math>v</math> to <math>w</math> is a bridge.

==Bridge-Finding with Chain Decompositions==
A very simple bridge-finding algorithm<ref name="Schmidt">{{citation
| last = Schmidt | first = Jens M. | author-link = Jens M. Schmidt
| doi = 10.1016/j.ipl.2013.01.016
| issue = 7
| journal = Information Processing Letters
| pages = 241–244
| year = 2013
| title = A Simple Test on 2-Vertex- and 2-Edge-Connectivity
| volume = 113}}.</ref> uses [[chain decompositions]].
Chain decompositions do not only allow to compute all bridges of a graph, they also allow to ''read off'' every [[cut vertex]] of ''G'' (and the [[Biconnected component|block-cut tree]] of ''G''), giving a general framework for testing 2-edge- and 2-vertex-connectivity (which extends to linear-time 3-edge- and 3-vertex-connectivity tests).

Chain decompositions are special ear decompositions depending on a DFS-tree ''T'' of ''G'' and can be computed very simply: Let every vertex be marked as unvisited. For each vertex ''v'' in ascending [[Depth-first search|DFS]]-numbers 1...''n'', traverse every backedge (i.e. every edge not in the DFS tree) that is incident to ''v'' and follow the path of tree-edges back to the root of ''T'', stopping at the first vertex that is marked as visited. During such a traversal, every traversed vertex is marked as visited. Thus, a traversal stops at the latest at ''v'' and forms either a directed path or cycle, beginning with v; we call this path
or cycle a ''chain''. The ''i''th chain found by this procedure is referred to as ''Ci''. ''C=C1,C2,...'' is then a ''[[chain decomposition]]'' of ''G''.

The following characterizations then allow to ''read off'' several properties of ''G'' from ''C'' efficiently, including all bridges of ''G''.<ref name="Schmidt"/> Let ''C'' be a chain decomposition of a simple connected graph ''G=(V,E)''.
# ''G'' is 2-edge-connected if and only if the chains in ''C'' partition ''E''.
# An edge ''e'' in ''G'' is a bridge if and only if ''e'' is not contained in any chain in ''C''.
# If ''G'' is 2-edge-connected, ''C'' is an [[ear decomposition]].
# ''G'' is 2-vertex-connected if and only if ''G'' has minimum degree 2 and ''C1'' is the only cycle in ''C''.
# A vertex ''v'' in a 2-edge-connected graph ''G'' is a cut vertex if and only if ''v'' is the first vertex of a cycle in ''C - C1''.
# If ''G'' is 2-vertex-connected, ''C'' is an [[Ear decomposition|open ear decomposition]].

==Notes==
{{reflist}}

[[Category:Graph connectivity]]

formulasearchengine - User contributions [en]

Electrostriction