Path graph - Revision history

en>David Eppstein: remove cat

2014-07-28T07:29:27Z

remove cat

← Older revision		Revision as of 09:29, 28 July 2014
Line 1:		Line 1:
	~~{{DISPLAYTITLE:''k''-edge-connected graph}}~~		Hello. Allow me introduce over the counter std test ([http://riddlesandpoetry.com/?q=node/19209 a knockout post]) writer. Her name is Refugia Shryock. To collect coins is what her family and her appreciate. My day job is a meter reader. California is where I've usually been living and I love every working day living right here.
	~~In [[graph theory]], a graph is '''''k''-edge-connected''' if it remains [[connectivity (graph theory)\|connected]] whenever fewer than ''k'' edges are removed~~.

	~~==Formal definition==~~
	~~Let <math>G =~~ (~~V, E)<~~/~~math> be an arbitrary graph~~.
	~~If subgraph <math>G'~~ = ~~(V, E \setminus X)</math> is connected for all <math>X \subseteq E</math> where <math>\|X\| < k<~~/~~math>, then ''G'' is ''k''-edge-connected. Trivially,~~ a ~~graph that is ''k''-edge-connected is also (''k''−1)-edge-connected.~~

	~~==Relation to minimum vertex degree==~~
	~~Minimum [[degree (graph theory)\|vertex degree~~]~~] gives a trivial upper bound on edge-connectivity. That is, if a graph <math>G = (V, E~~)~~</math> is ''k''-edge-connected then it is necessary that ''k'' ≤ δ(''G''), where δ(''G'') is the minimum degree of any vertex ''v'' ∈ ''V''~~. ~~Obviously, deleting all edges incident to a vertex, ''v'', would then disconnect ''v'' from the graph.~~

	~~== Computational aspects ==~~
	~~There~~ is a polynomial-time algorithm to determine the largest ''k'' for which a graph ''G'' is ''k''-edge-connected. A simple algorithm would, for every pair ''(u,v)'', determine the [[Maximum flow problem\|maximum flow]] from ''u'' to ''v'' with the capacity of all edges in ''G'' set to 1 for both directions. ~~A graph~~ is ~~''k''-edge-connected if~~ and ~~only if the maximum flow from ''u'' to ''v'' is at least ''k'' for any pair ''(u,v)'', so ''k'' is the least ''u-v''-flow among all ''(u,v)''~~.

	~~If ''n''~~ is ~~the number of vertices in the graph, this simple algorithm would perform <math>O(n^2)</math> iterations of the Maximum flow problem, which can be solved in <math>O(n^3)</math> time~~. ~~Hence the complexity of the simple algorithm described above~~ is ~~<math>O(n^5)</math> in total.~~

	~~An improved algorithm will solve the maximum flow problem for every pair ''(u,v)''~~ where '~~'u'' is arbitrarily fixed while ''v'' varies~~
	~~over all vertices. This reduces the complexity to <math>O(n^4)</math>~~ and ~~is sound since, if a [[Cut_(graph_theory)\|cut]] of capacity less than ''k'' exists,~~
	it is bound to separate ''u'' from some other vertex. It can be further improved by [[Gabow's algorithm]] that runs in worst case <math>O(n^3)</math> time. <ref> Harold N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. ''J. ~~Comput. Syst. Sci.'', 50(2):259–273, 1995.</ref>~~

	A related problem: finding the minimum ''k''-edge-connected subgraph of ''G'' (that is: select as few as possible edges in ''G'' that your selection is ''k''-edge-connected) is NP-hard for <math>k\geq 2</math>.<ref>M.R. Garey and D.S. Johnson. ''Computers and Intractability: a Guide to the Theory of NP-Completeness''. Freeman, San Francisco, CA, 1979.</ref>

	~~== See also ==~~
	* [[k-vertex-connected graph]]
	* [[Connectivity (graph theory)]]
	* [[Matching preclusion]]
	* [[Menger's theorem]]
	* [[Robbins theorem]]

	~~==References==~~
	~~{{reflist}}~~

	~~[[Category:Graph connectivity]]~~
	~~[[Category:Graph families]]~~

en>Satellizer: Reverted 1 edit by 72.26.9.78 identified as test/vandalism using STiki

2013-10-27T01:26:41Z

Reverted 1 edit by 72.26.9.78 identified as test/vandalism using STiki

← Older revision		Revision as of 03:26, 27 October 2013
Line 1:		Line 1:
	~~Hi there~~. ~~Allow me begin by introducing the author~~, ~~her name~~ is ~~Sophia Boon but she never truly favored~~ that ~~name. What me and my family members love~~ is ~~performing ballet but I~~'~~ve been using~~ on ~~new issues lately~~. ~~My day occupation~~ is a ~~journey agent. Ohio~~ is ~~exactly~~ where my [~~http://bigpolis~~.~~com/blogs/post/6503 good psychic] home~~ is ~~but my spouse wants us~~ to ~~transfer~~.<br><br>~~Also visit my homepage; best [http:~~//~~test~~.~~jeka-nn~~.ru/~~node/129 real psychic readings~~] - [~~http:~~/~~/hknews~~.~~classicmall~~.~~com~~.hk/~~groups/some~~-~~simple~~-~~tips~~-~~for~~-~~personal~~-~~development~~-~~progress/ classicmall~~.~~com~~.hk] -		{{DISPLAYTITLE:''k''-edge-connected graph}}
			In [[graph theory]], a graph is '''''k''-edge-connected''' if it remains [[connectivity (graph theory)\|connected]] whenever fewer than ''k'' edges are removed.

			==Formal definition==
			Let <math>G = (V, E)</math> be an arbitrary graph.
			If subgraph <math>G' = (V, E \setminus X)</math> is connected for all <math>X \subseteq E</math> where <math>\|X\| < k</math>, then ''G'' is ''k''-edge-connected. Trivially, a graph that is ''k''-edge-connected is also (''k''−1)-edge-connected.

			==Relation to minimum vertex degree==
			Minimum [[degree (graph theory)\|vertex degree]] gives a trivial upper bound on edge-connectivity. That is, if a graph <math>G = (V, E)</math> is ''k''-edge-connected then it is necessary that ''k'' ≤ δ(''G''), where δ(''G'') is the minimum degree of any vertex ''v'' ∈ ''V''. Obviously, deleting all edges incident to a vertex, ''v'', would then disconnect ''v'' from the graph.

			== Computational aspects ==
			There is a polynomial-time algorithm to determine the largest ''k'' for which a graph ''G'' is ''k''-edge-connected. A simple algorithm would, for every pair ''(u,v)'', determine the [[Maximum flow problem\|maximum flow]] from ''u'' to ''v'' with the capacity of all edges in ''G'' set to 1 for both directions. A graph is ''k''-edge-connected if and only if the maximum flow from ''u'' to ''v'' is at least ''k'' for any pair ''(u,v)'', so ''k'' is the least ''u-v''-flow among all ''(u,v)''.

			If ''n'' is the number of vertices in the graph, this simple algorithm would perform <math>O(n^2)</math> iterations of the Maximum flow problem, which can be solved in <math>O(n^3)</math> time. Hence the complexity of the simple algorithm described above is <math>O(n^5)</math> in total.

			An improved algorithm will solve the maximum flow problem for every pair ''(u,v)'' where ''u'' is arbitrarily fixed while ''v'' varies
			over all vertices. This reduces the complexity to <math>O(n^4)</math> and is sound since, if a [[Cut_(graph_theory)\|cut]] of capacity less than ''k'' exists,
			it is bound to separate ''u'' from some other vertex. It can be further improved by [[Gabow's algorithm]] that runs in worst case <math>O(n^3)</math> time. <ref> Harold N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. ''J. Comput. Syst. Sci.'', 50(2):259–273, 1995.</ref>

			A related problem: finding the minimum ''k''-edge-connected subgraph of ''G'' (that is: select as few as possible edges in ''G'' that your selection is ''k''-edge-connected) is NP-hard for <math>k\geq 2</math>.<ref>M.R. Garey and D.S. Johnson. ''Computers and Intractability: a Guide to the Theory of NP-Completeness''. Freeman, San Francisco, CA, 1979.</ref>

			== See also ==
			* [[k-vertex-connected graph]]
			* [[Connectivity (graph theory)]]
			* [[Matching preclusion]]
			* [[Menger's theorem]]
			* [[Robbins theorem]]

			==References==
			{{reflist}}

			[[Category:Graph connectivity]]
			[[Category:Graph families]]

en>David Eppstein: /* References */ link Alexander Schrijver

2012-03-31T07:12:42Z

References: link Alexander Schrijver

New page

Hi there. Allow me begin by introducing the author, her name is Sophia Boon but she never truly favored that name. What me and my family members love is performing ballet but I've been using on new issues lately. My day occupation is a journey agent. Ohio is exactly where my [http://bigpolis.com/blogs/post/6503 good psychic] home is but my spouse wants us to transfer.<br><br>Also visit my homepage; best [http://test.jeka-nn.ru/node/129 real psychic readings] - [http://hknews.classicmall.com.hk/groups/some-simple-tips-for-personal-development-progress/ classicmall.com.hk] -