Robbins theorem


Robbins theorem

In graph theory, the Robbins theorem, named after Herbert Robbins, states that a connected graph G has astrongly connected orientation if and only if G has no bridge.

Sources

* "A theorem on graphs with an application to a problem on traffic control", American Mathematical Monthly, 46:281-283, 1939.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Robbins algebra — A Robbins algebra is an algebra consisting of the set {0,1} and the logical operations lor (disjunction, or ) and eg (negation, not ), with the following axioms:* Associativity: a lor (b lor c) = (a lor b) lor c * Commutativity: a lor b = b lor a …   Wikipedia

  • Herbert Robbins — Herbert Ellis Robbins (born January 12, 1915 in New Castle, Pennsylvania; died February 12, 2001 in Princeton, New Jersey) was a mathematician and statistician who did research in topology, measure theory, statistics, and a variety of other… …   Wikipedia

  • Automated theorem proving — (ATP) or automated deduction, currently the most well developed subfield of automated reasoning (AR), is the proving of mathematical theorems by a computer program. Decidability of the problem Depending on the underlying logic, the problem of… …   Wikipedia

  • Lionel Robbins, Baron Robbins — Lionel Charles Robbins, Baron Robbins (1898 2008) was a British economist and adherent to the Austrian School of Economics. He is known for his proposed definition of economics, and for his instrumental efforts in shifting Anglo Saxon economics… …   Wikipedia

  • Maximum power transfer theorem — In electrical engineering, the maximum power transfer theorem states that, to obtain maximum external power from a source with a finite internal resistance, the resistance of the load must be equal to the resistance of the source as viewed from… …   Wikipedia

  • Maximum power theorem — In electrical engineering, the maximum power (transfer) theorem states that, to obtain maximum external power from a source with a finite internal resistance, the resistance of the load must be made the same as that of the source. It is claimed… …   Wikipedia

  • List of mathematics articles (R) — NOTOC R R. A. Fisher Lectureship Rabdology Rabin automaton Rabin signature algorithm Rabinovich Fabrikant equations Rabinowitsch trick Racah polynomials Racah W coefficient Racetrack (game) Racks and quandles Radar chart Rademacher complexity… …   Wikipedia

  • Nowhere-zero flow — In graph theory, nowhere zero flows are a special type of network flow which is related (by duality) to coloring planar graphs. Let G = (V,E) be a directed graph and let M be an abelian group. We say that a map is a flow or an M flow if the… …   Wikipedia

  • Strongly connected component — Graph with strongly connected components marked A directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex. In particular, this means paths in each direction; a path from a to b and also a …   Wikipedia

  • Bridge (graph theory) — A graph with 6 bridges (highlighted in red) An undirected connected graph with no cut …   Wikipedia