formulasearchengine - User contributions [en]

Semivariance

2014-01-19T11:37:15Z

82.181.11.232: /* References */

{{redirect|Positive infinity|the band|Positive Infinity}}
{{Unreferenced|date=January 2012}}
In [[mathematics]], the '''affinely extended real number system''' is obtained from the [[real number]] system '''R''' by adding two elements: +∞ and −∞ (read as '''positive [[infinity]]''' and '''negative infinity''' respectively). These new elements are not real numbers. It is useful in describing various [[limit of a function|limiting behavior]]s in [[calculus]] and [[mathematical analysis]], especially in the theory of [[measure (mathematics)|measure]] and [[integral|integration]]. The affinely extended real number system is denoted '''{{Overline|R}}''' or [−∞, +∞].

When the meaning is clear from context, the symbol +∞ is often written simply as ∞.

==Motivation==
===Limits===

We often wish to describe the behavior of a function ''f''(''x''), as either the argument ''x'' or the function value ''f''(''x'') gets "very big" in some sense. For example, consider the function

:<math>f(x) = x^{-2}.</math>

The graph of this function has a horizontal [[asymptote]] at y = 0. Geometrically, as we move farther and farther to the right along the ''x''-axis, the value of 1/''x''2 approaches 0. This limiting behavior is similar to the [[limit of a function]] at a [[real number]], except that there is no real number to which ''x'' approaches.

By adjoining the elements +∞ and −∞ to '''R''', we allow a formulation of a "limit at infinity" with [[topology|topological]] properties similar to those for '''R'''.

To make things completely formal, the [[Cauchy sequences]] definition of '''R''' allows us to define +∞ as the set of all sequences of rationals which, for any K>0, from some point on exceed K. We can define −∞ similarly.

===Measure and integration===

In [[measure theory]], it is often useful to allow sets which have infinite measure and integrals whose value may be infinite.

Such measures arise naturally out of calculus. For example, in assigning a [[measure (mathematics)|measure]] to '''R''' that agrees with the usual length of intervals, this measure must be larger than any finite real number. Also, when considering infinite integrals, such as

:<math>\int_1^{\infty}\frac{dx}{x}</math>

the value "infinity" arises. Finally, it is often useful to consider the limit of a sequence of functions, such as

:<math>f_n(x) = \begin{cases} 2n(1-nx), & \mbox{if } 0 \le x \le \frac{1}{n} \\ 0, & \mbox{if } \frac{1}{n} < x \le 1\end{cases}</math>

Without allowing functions to take on infinite values, such essential results as the [[monotone convergence theorem]] and the [[dominated convergence theorem]] would not make sense.

==Order and topological properties==

The affinely extended real number system turns into a [[totally ordered set]] by defining −∞ ≤ ''a'' ≤ +∞ for all ''a''. This order has the desirable property that every subset has a [[supremum]] and an [[infimum]]: it is a [[complete lattice]].

This induces the [[order topology]] on '''{{Overline|R}}'''. In this topology, a set ''U'' is a [[neighborhood (topology)|neighborhood]] of +∞ if and only if it contains a set {''x'' : ''x'' > ''a''} for some real number ''a'', and analogously for the neighborhoods of −∞. '''{{Overline|R}}''' is a [[Compact space|compact]] [[Hausdorff space]] [[homeomorphism|homeomorphic]] to the [[unit interval]] [0, 1]. Thus the topology is [[metrizable]], corresponding (for a given homeomorphism) to the ordinary metric on this interval. There is no metric which is an extension of the ordinary metric on '''R'''.

With this topology the specially defined [[Limit of a function|limits]] for ''x'' tending to +∞ and −∞, and the specially defined concepts of limits equal to +∞ and −∞, reduce to the general topological definitions of limits.

==Arithmetic operations==

The arithmetic operations of '''R''' can be partially extended to '''{{Overline|R}}''' as follows:

:<math>
\begin{align}
a + \infty = +\infty + a & = +\infty, & a & \neq -\infty \\
a - \infty = -\infty + a & = -\infty, & a & \neq +\infty \\
a \cdot (\pm\infty) = \pm\infty \cdot a & = \pm\infty, & a & \in (0, +\infty] \\
a \cdot (\pm\infty) = \pm\infty \cdot a & = \mp\infty, & a & \in [-\infty, 0) \\
\frac{a}{\pm\infty} & = 0, & a & \in \mathbb{R} \\
\frac{\pm\infty}{a} & = \pm\infty, & a & \in (0, +\infty) \\
\frac{\pm\infty}{a} & = \mp\infty, & a & \in (-\infty, 0)
\end{align}
</math>

Here, "''a'' + ∞" means both "''a'' + (+∞)" and "''a'' − (−∞)", while "''a'' − ∞" means both "''a'' − (+∞)" and "''a'' + (−∞)".

The expressions ∞ − ∞, 0 × (±∞) and ±∞ / ±∞ (called [[indeterminate form]]s) are usually left [[Defined and undefined|undefined]]. These rules are modeled on the laws for [[Limit_of_a_function#Limit_of_a_function_at_infinity|infinite limits]]. However, in the context of probability or measure theory, 0 × (±∞) is often defined as 0.

The expression 1/0 is not defined either as +∞ or −∞, because although it is true that whenever ''f''(''x'') → 0 for a [[continuous function]] ''f''(''x'') it must be the case that 1/''f''(''x'') is eventually contained in every [[neighborhood (topology)|neighborhood]] of the set {−∞, +∞}, it is ''not'' true that 1/''f''(''x'') must tend to one of these points. An example is ''f''(''x'') = (sin ''x'')/''x'' (as ''x'' goes to infinity). (The [[absolute value|modulus]] | 1/''f''(''x'') |, nevertheless, does approach +∞.)

==Algebraic properties==

With these definitions '''{{Overline|R}}''' is '''not''' a [[field (mathematics)|field]], nor a [[ring (mathematics)|ring]], and not even a [[group (mathematics)|group]] or [[semigroup]]. However, it still has several convenient properties:
* ''a'' + (''b'' + ''c'') and (''a'' + ''b'') + ''c'' are either equal or both undefined.
* ''a'' + ''b'' and ''b'' + ''a'' are either equal or both undefined.
* ''a'' × (''b'' × ''c'') and (''a'' × ''b'') × ''c'' are either equal or both undefined.
* ''a'' × ''b'' and ''b'' × ''a'' are either equal or both undefined
* ''a'' × (''b'' + ''c'') and (''a'' × ''b'') + (''a'' × ''c'') are equal if both are defined.
* if ''a'' ≤ ''b'' and if both ''a'' + ''c'' and ''b'' + ''c'' are defined, then ''a'' + ''c'' ≤ ''b'' + ''c''.
* if ''a'' ≤ ''b'' and ''c'' > 0 and both ''a'' × ''c'' and ''b'' × ''c'' are defined, then ''a'' × ''c'' ≤ ''b'' × ''c''.

In general, all laws of arithmetic are valid in '''{{Overline|R}}''' as long as all occurring expressions are defined.

==Miscellaneous==

Several [[function (mathematics)|functions]] can be [[continuity (topology)|continuously]] extended to '''{{Overline|R}}''' by taking limits. For instance, one defines [[exponential function|exp]](−∞) = 0, exp(+∞) = +∞, [[natural logarithm|ln]](0) = −∞, ln(+∞) = +∞ etc.

Some discontinuities may additionally be removed. For example, the function 1/''x''2 can be made continuous (under ''some'' definitions of continuity) by setting the value to +∞ for ''x'' = 0, and 0 for ''x'' = +∞ and ''x'' = −∞. The function 1/''x'' can ''not'' be made continuous because the function approaches −∞ as ''x'' approaches 0 from below, and +∞ as ''x'' approaches 0 from above.

Compare the [[real projective line]], which does not distinguish between +∞ and −∞. As a result, on one hand a function may have limit ∞ on the real projective line, while in the affinely extended real number system only the absolute value of the function has a limit, e.g. in the case of the function 1/''x'' at ''x'' = 0. On the other hand
:<math>\lim_{x \to -\infty}{f(x)}</math> and <math>\lim_{x \to +\infty}{f(x)}</math>
correspond on the real projective line to only a limit from the right and one from the left, respectively, with the full limit only existing when the two are equal. Thus e''x'' and arctan(''x'') cannot be made continuous at ''x'' = ∞ on the real projective line.

==See also==
* [[Real projective line]], which adds positive infinity without negative infinity to the real number line.
* [[Division by zero]]
* [[Extended complex plane]]
* [[Improper integral]]
* [[Series (mathematics)]]

==References==
* {{MathWorld|author= David W. Cantrell|title=Affinely Extended Real Numbers|urlname=AffinelyExtendedRealNumbers}}
{{Number Systems}}

[[Category:Infinity]]
[[Category:Real numbers]]

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]]