Classical eulerian cycle algorithm - Revision history

Weihe: /* Recursive step */

2015-11-02T08:15:50Z

Recursive step

← Older revision		Revision as of 08:15, 2 November 2015
Line 27:		Line 27:
	## Call the procedure recursively with <math>v</math> as the start node, giving path <math>p'</math>.		## Call the procedure recursively with <math>v</math> as the start node, giving path <math>p'</math>.
	## Replace <math>v</math> in <math>p</math> by <math>p'</math>.		## Replace <math>v</math> in <math>p</math> by <math>p'</math>.
	~~# If there are still edges/arcs, terminate the algorithm with the statement that no eulerian cycle exists.~~

	== Correctness ==		== Correctness ==

Weihe: /* Correctness */

2015-11-02T08:13:56Z

Correctness

← Older revision		Revision as of 08:13, 2 November 2015
Line 31:		Line 31:
	== Correctness ==		== Correctness ==

	Since each edge/arc is removed immediately when it is processed, no edge/arc occurs twice in the output. Obviously, steps 4.3 and 6.2 ensure that the order in which the nodes and edges/arcs occur in the output yields a correct path. Obviously, whenever step 4 is finished, it is <math>x=s</math> and the remaining graph is eulerian, if the original graph was eulerian. Consequently, the statement that no eulerian cycle exists is only delivered if the graph is indeed non-eulerian. Moreover, the graph handed over to a recursive call is Eulerian, if the original graph was Eulerian.		Since each edge/arc is removed immediately when it is processed, no edge/arc occurs twice in the output. Obviously, steps 4.3 and 6.2 ensure that the order in which the nodes and edges/arcs occur in the output yields a correct path. Obviously, whenever step 4 is finished, it is <math>x=s</math> and the remaining graph is eulerian, if the original graph was eulerian. Consequently, the statement that no eulerian cycle exists is only delivered in step 5 if the graph is indeed non-eulerian. Moreover, the graph handed over to a recursive call is Eulerian, if the original graph was Eulerian.

	Suppose for a contradiction that some edge/arc <math>e/a</math> is '''not''' in the output. Since the graph is (strongly) connected, there is a path <math>q</math> from the start node of the algorithm to the beginning node of <math>a</math> (an arbitrary endnode of <math>e</math> in the undirected case). Let <math>v</math> be the last node on <math>q</math> processed by any recursive call. Then the subsequent edge/arc on <math>q</math> has not been processed, which contradicts the procedure.		Suppose for a contradiction that some edge/arc <math>e/a</math> is '''not''' in the output. Since the graph is (strongly) connected, there is a path <math>q</math> from the start node of the algorithm to the beginning node of <math>a</math> (an arbitrary endnode of <math>e</math> in the undirected case). Let <math>v</math> be the last node on <math>q</math> processed by any recursive call. Then the subsequent edge/arc on <math>q</math> has not been processed, which contradicts the procedure.

Weihe: /* Recursive step */

2015-11-02T08:13:06Z

Recursive step

← Older revision		Revision as of 08:13, 2 November 2015
Line 27:		Line 27:
	## Call the procedure recursively with <math>v</math> as the start node, giving path <math>p'</math>.		## Call the procedure recursively with <math>v</math> as the start node, giving path <math>p'</math>.
	## Replace <math>v</math> in <math>p</math> by <math>p'</math>.		## Replace <math>v</math> in <math>p</math> by <math>p'</math>.
			# If there are still edges/arcs, terminate the algorithm with the statement that no eulerian cycle exists.

	== Correctness ==		== Correctness ==

BB91: /* Correctness */ kleine Einfügung zum Verständnis; Korrektur tail -> beginning node im Beweis

2015-01-02T08:10:10Z

Correctness: kleine Einfügung zum Verständnis; Korrektur tail -> beginning node im Beweis

← Older revision		Revision as of 08:10, 2 January 2015
Line 32:		Line 32:
	Since each edge/arc is removed immediately when it is processed, no edge/arc occurs twice in the output. Obviously, steps 4.3 and 6.2 ensure that the order in which the nodes and edges/arcs occur in the output yields a correct path. Obviously, whenever step 4 is finished, it is <math>x=s</math> and the remaining graph is eulerian, if the original graph was eulerian. Consequently, the statement that no eulerian cycle exists is only delivered if the graph is indeed non-eulerian. Moreover, the graph handed over to a recursive call is Eulerian, if the original graph was Eulerian.		Since each edge/arc is removed immediately when it is processed, no edge/arc occurs twice in the output. Obviously, steps 4.3 and 6.2 ensure that the order in which the nodes and edges/arcs occur in the output yields a correct path. Obviously, whenever step 4 is finished, it is <math>x=s</math> and the remaining graph is eulerian, if the original graph was eulerian. Consequently, the statement that no eulerian cycle exists is only delivered if the graph is indeed non-eulerian. Moreover, the graph handed over to a recursive call is Eulerian, if the original graph was Eulerian.

	Suppose for a contradiction that some edge/arc <math>e/a</math> is '''not''' in the output. Since the graph is (strongly) connected, there is a path <math>q</math> from the start node to the ~~tail~~ of <math>e/a</math> (an arbitrary endnode of <math>e/a</math> in the undirected case). Let <math>v</math> be the last node on <math>q</math> processed by any recursive call. Then the subsequent edge/arc on <math>q</math> has not been processed, which contradicts the procedure.		Suppose for a contradiction that some edge/arc <math>e/a</math> is '''not''' in the output. Since the graph is (strongly) connected, there is a path <math>q</math> from the start node of the algorithm to the beginning node of <math>a</math> (an arbitrary endnode of <math>e</math> in the undirected case). Let <math>v</math> be the last node on <math>q</math> processed by any recursive call. Then the subsequent edge/arc on <math>q</math> has not been processed, which contradicts the procedure.

	== Complexity ==		== Complexity ==

Weihe: /* Recursion anchor */

2014-12-06T13:02:54Z

Recursion anchor

← Older revision		Revision as of 13:02, 6 December 2014
Line 9:		Line 9:
	== Recursion anchor ==		== Recursion anchor ==

	~~'''Break condition:'''~~ No edges/arcs leave the start node <math>s</math> of that recursive call.		No edges/arcs leave the start node <math>s</math> of that recursive call.

	== Recursive step ==		== Recursive step ==

Weihe at 13:02, 6 December 2014

2014-12-06T13:02:44Z

← Older revision		Revision as of 13:02, 6 December 2014
Line 6:		Line 6:

	''' Type of algorithm:''' recursion with an arbitrarily chosen start node <math>s\in V</math> as an additional input. Before the proper recursive procedure is invoked, the output sequence <math>S</math> is initialized so as to contain the start node <math>s</math> and nothing else.		''' Type of algorithm:''' recursion with an arbitrarily chosen start node <math>s\in V</math> as an additional input. Before the proper recursive procedure is invoked, the output sequence <math>S</math> is initialized so as to contain the start node <math>s</math> and nothing else.

			== Recursion anchor ==

	'''Break condition:''' No edges/arcs leave the start node <math>s</math> of that recursive call.		'''Break condition:''' No edges/arcs leave the start node <math>s</math> of that recursive call.

	== ~~Induction basis ==~~		== Recursive step ==

	~~'''Abstract view:''' Nothing to do.~~

	~~== Induction~~ step ==

	For notational convenience, both undirected edges and directed arcs are denoted by parentheses in the following (in the direction in which they are looked at).		For notational convenience, both undirected edges and directed arcs are denoted by parentheses in the following (in the direction in which they are looked at).

Pezi22 at 18:50, 11 November 2014

2014-11-11T18:50:02Z

← Older revision		Revision as of 18:50, 11 November 2014
Line 1:		Line 1:
	[[File:Nikolaus.png\|~~200px~~\|thumb\|right\|Another may well know example with 44 solutions]]		[[File:Nikolaus.png\|400px\|thumb\|right\|Another may well know example with 44 solutions]]

	== General information ==		== General information ==

Weihe: /* Correctness */

2014-11-07T11:14:53Z

Correctness

← Older revision		Revision as of 11:14, 7 November 2014
Line 32:		Line 32:
	== Correctness ==		== Correctness ==

	Since each edge/arc is removed immediately when it is processed, no edge/arc occurs twice in the output. Obviously, steps 4.3 and 6.2 ensure that the order in which the nodes and edges/arcs occur in the output yields a correct path. Obviously, whenever step 4 is finished, it is <math>x=s</math> and the remaining graph is eulerian, if the original graph was eulerian. Consequently, the statement that no eulerian cycle exists is only delivered if indeed ~~valid~~, ~~and~~ the graph handed over to a recursive call is Eulerian, if the original graph was Eulerian.		Since each edge/arc is removed immediately when it is processed, no edge/arc occurs twice in the output. Obviously, steps 4.3 and 6.2 ensure that the order in which the nodes and edges/arcs occur in the output yields a correct path. Obviously, whenever step 4 is finished, it is <math>x=s</math> and the remaining graph is eulerian, if the original graph was eulerian. Consequently, the statement that no eulerian cycle exists is only delivered if the graph is indeed non-eulerian. Moreover, the graph handed over to a recursive call is Eulerian, if the original graph was Eulerian.

	Suppose for a contradiction that some edge/arc <math>e/a</math> is '''not''' in the output. Since the graph is (strongly) connected, there is a path <math>q</math> from the start node to the tail of <math>e/a</math> (an arbitrary endnode of <math>e/a</math> in the undirected case). Let <math>v</math> be the last node on <math>q</math> processed by any recursive call. Then the subsequent edge/arc on <math>q</math> has not been processed, which contradicts the procedure.		Suppose for a contradiction that some edge/arc <math>e/a</math> is '''not''' in the output. Since the graph is (strongly) connected, there is a path <math>q</math> from the start node to the tail of <math>e/a</math> (an arbitrary endnode of <math>e/a</math> in the undirected case). Let <math>v</math> be the last node on <math>q</math> processed by any recursive call. Then the subsequent edge/arc on <math>q</math> has not been processed, which contradicts the procedure.

Weihe: /* Correctness */

2014-11-07T11:12:50Z

Correctness

← Older revision		Revision as of 11:12, 7 November 2014
Line 32:		Line 32:
	== Correctness ==		== Correctness ==

	Since each edge/arc is removed immediately when it is processed, no edge/arc occurs twice in the output. Obviously, steps 4.3 and 6.2 ensure that the order in which the nodes and edges/arcs occur in the output yields a correct path. Obviously, whenever step 4 is finished, it is <math>x=s</math> and the remaining graph is ~~Eulerian~~, if the original graph was ~~Eulerian~~. Consequently, the statement that no ~~Eulerian~~ cycle exists is only delivered if ~~true~~, and the graph handed over to a recursive call is Eulerian, if the original graph was Eulerian.		Since each edge/arc is removed immediately when it is processed, no edge/arc occurs twice in the output. Obviously, steps 4.3 and 6.2 ensure that the order in which the nodes and edges/arcs occur in the output yields a correct path. Obviously, whenever step 4 is finished, it is <math>x=s</math> and the remaining graph is eulerian, if the original graph was eulerian. Consequently, the statement that no eulerian cycle exists is only delivered if indeed valid, and the graph handed over to a recursive call is Eulerian, if the original graph was Eulerian.

	Suppose for a contradiction that some edge/arc <math>e/a</math> is '''not''' in the output. Since the graph is (strongly) connected, there is a path <math>q</math> from the start node to the tail of <math>e/a</math> (an arbitrary endnode of <math>e/a</math> in the undirected case). Let <math>v</math> be the last node on <math>q</math> processed by any recursive call. Then the subsequent edge/arc on <math>q</math> has not been processed, which contradicts the procedure.		Suppose for a contradiction that some edge/arc <math>e/a</math> is '''not''' in the output. Since the graph is (strongly) connected, there is a path <math>q</math> from the start node to the tail of <math>e/a</math> (an arbitrary endnode of <math>e/a</math> in the undirected case). Let <math>v</math> be the last node on <math>q</math> processed by any recursive call. Then the subsequent edge/arc on <math>q</math> has not been processed, which contradicts the procedure.

Weihe: /* Induction step */

2014-11-07T11:10:48Z

Induction step

← Older revision		Revision as of 11:10, 7 November 2014
Line 25:		Line 25:
	## Append <math>(x,y)</math> and then <math>y</math> to <math>p</math>.		## Append <math>(x,y)</math> and then <math>y</math> to <math>p</math>.
	## Set <math>x:=y</math>.		## Set <math>x:=y</math>.
	# If <math>x\neq s</math>, terminate the algorithm with the statement that no ~~Eulerian~~ cycle exists.		# If <math>x\neq s</math>, terminate the algorithm with the statement that no eulerian cycle exists.
	# Otherwise: For each node <math>v</math> on <math>p</math> that still has leaving edges/arcs,:		# Otherwise: For each node <math>v</math> on <math>p</math> that still has leaving edges/arcs,:
	## Call the procedure recursively with <math>v</math> as the start node, giving path <math>p'</math>.		## Call the procedure recursively with <math>v</math> as the start node, giving path <math>p'</math>.