The topic I chose is called Eulerian cycle, Euler is pronounced oil-er. " In this issue also called Euler circuit, Euler circuit, Euler tour or euler tour. Definition
An Eulerian cycle is a path in a graph G that begins and ends at the same vertex, which includes every edge of the graph exactly once and may have repeated vertices, ie, a cycle that includes all the edges of E and that these do not recur. Similar Topics
This topic is extremely mind related to Eulerian path that is about finding a path in a graph G so as to include all edges without repetition, and also compared further with the Hamiltonian cycle about a cycle that includes all vertices at once. Sources
This conundrum arises with the problem of the 7 pu entities Königsberg (eighteenth-century German town situated on the river Prague) which was decided by the Swiss mathematician Leonhard Euler in 1736 and published in an article entitled Solutio ad geometriam problematis pertinentis situs (Solve a problem with the geometry of position).
The problem is about the 7 bridges through the city connecting 2 islands, once each.
Königsberg 
roads bridges are white on the gray river.
Euler solved the problem by imagining the territory of the islands and the river with a connected graph.
Now we must try to find a cycle that includes all the edges so that the line has not been repeated edges.
...
Euler discovered that this is impossible in this graph!, But it was he who gave the mathematical proof but was Carl Hierholzer until 1873.
What I said was Leonhard Euler (in our terms) a Eulerian cycle in a graph G exists if and only if:
- The graph was connected, ie there is at least one way to reach any vertex
- The degree of all vertices of G is an even number or put another way, if there is one vertex of odd degree.
We can understand the argument of Euler because in an Eulerian cycle as we pass through a vertex we have to have 2 paths (edges) or any other even number, this is gra (e) mod 2 = 0, one to get the other to leave, or vice versa and complete the cycle, otherwise we would be "stuck" in the same vertex or else we might never return, in any case always an edge to go missing to complete the cycle.
Problem must resolve
can say that Euler solved the problem following decision:
"There is a path that includes all the edges without repeated, starting from a vertex v back to the same vertex v in a graph G ?. "
Without their algorithm to determine this decision problem, we should make all possible routes to determine whether there is any Eulerian cycle and it will have an asymptotic complexity O (n!), but with the simple rules we get the complexity O Euler (n). Example
Eulerian cycle
is interesting that no matter how large or complex a graph, if it complies with the 2 above conditions (1 and 2), this has an Eulerian cycle.
In this picture the graph is also related to the degree of all vertices is an even number. Algorithm
problem
several algorithms are possible depending on what it intends to solve, for example, one that solves the decision problem: There is an Eulerian cycle in a graph G?, One that solves the problem of decision: What is an Eulerian cycle in G?, and even a third party to solve the decision problem: What are all Eulerian cycles in G? (A variant of above). Besides
variations may exist Eulerian cycle optimization to solve problems like: Find an Eulerian cycle so as to travel some vertices before others, in this case could balance the vertices according to preference and optimizing the way to go to get the best possible cycle. Algorithm
existence
- For each vertex in the graph will analyze their degree (ignore the neighbors, it is trivial).
- If anyone has an odd degree, we can say that there is no Eulerian cycle in the graph and ends the algorithm.
- If at the end of analyzing all the corners, never said there was no Eulerian cycle, then said that if there is a Eulerian cycle.
- started at a vertex chosen at random or
- imagine starting a barrier to cross an edge chosen at random.
- The barrier will move until it can reach a vertex with degree other than 1. The barrier stored in a stack each edge of the journey he visited, in order.
- Note: This barrier aside a way of arriving at the initial vertex, ensuring the cycle.
- barrier each time you move to a new position, remove the edges covered.
- other hand imagine a traveler travel edges at random and that of course does not have access to the removed edges in the path of the barrier.
- Every time you move the passenger to a nearby ridge, keep the edge covered in a list or array and removes the same edge (not to go through there.)
- When the barrier and the traveler can not move to any neighboring vertex, which it says is the Eulerian cycle, showing first the list and then the stack whose items appear in reverse order of their introduction.
Note: There is probably a better way to find a Eulerian cycle due to time but I just thought in this algorithm. Computational Complexity
In the algorithm consider the instance of there n as the number of edges in the graph, in step 1 is known from a series of n times to conduct operations within it. In the second step (which is inside the loop) modular operation is performed with 3 and compared with 0 to determine if the degree is odd, these are 2 operations (2n so far). And the third step is waiting to complete the cycle to say that if there is a Eulerian cycle. In total was:
$ O (2n) $, as the constants do not matter is $ O (n) $. The problem of existence of an Eulerian cycle is in P because the complexity O (n) is polynomial.
pseudocode of the algorithm
Decision problem (there is an Eulerian cycle?)
# define num_de_vertices 4000
main () int i, grad [ num_de_vertices ];
for (i = 0 i \u0026lt;= size (grad []) i + +)
if (degree [i]> 1)
if (degree [i]% 3 == 0)
Puts On Eulerian cycle exists;
goto end;
else puts
There Eulerian cycle;
end
decision problem (which is an Eulerian cycle?)
# define num_vertices 4000
int n, end = 0, shift = 1, barrier, travel, view, edges [400] [ 400], / / \u200b\u200bedges [] [] is nothing more than an adjacency matrix
main ()
datafile read / / Is the information in the graph
ver = rand (0)% 3 / / We choose a vertex to the "random" barrier =
see;
while (! fin)
switch (shift) / / shifts the barrier functions and traveler
case 1:
fbarrera ();
break;
case 2:
fviajero();
break;
if (detenerbarrera==true&&detenerviajero==true)
print path (); / / The end of the day and show results
print stack () / / in the correct order
end
fbarrera ()
if (degree (barrier) == 0) / / If you do not have anywhere to go, check over
detenerbarrera ();
, end = true;
if (degree (barrier) == 1) / / If there is only one way possible, moves
battery (barrier) / / Stores the path when it moved
barrier = neighbor (barrier) / / This moves
delete (barrier, neighbor ());// barrier that path is removed / / to avoid repeating
shift + +;
end
fviajero ()
if (degree (traveler) == 0) / / If you do not have anywhere to go, check over
detenerviajero ();
way (passenger) / / Storing the path is
traveler = neighbor (passenger) / / Moves an edge allowed
delete (traveler, neighbor (traveler ));// To avoid repeating edges
shift -;
end
neighbor (int x) int i
;
for (i = 0; i \u0026lt;= num_vertices; i + +)
if (edges [x] [j] == 1) / / If there is an edge incident on x, / / \u200b\u200breturns the vertex to the leading edge
return alpha (j) end
remove (int t, int k)
edges [t] [k] = null; / / By removing the relationship ensures remove
edges [k] [t] = null, / / \u200b\u200bin any direction
end
asymptotic analysis algorithm
For the first algorithm in the worst case is $ O (n) $ because:
is assigned a constant (num_de_vertices). The
+1 step for creating a cycle where the complexity depends upon the processes within it.
two comparisons are made, grad [i]> 1 and grad [i] == 0 mod 3, and a modular operation, mod 3. N +3 steps
We then O (3n +3) but as the constants do not matter is O (n) and is polynomial.
In this pseudocode the best is O (1) this is because the first vertex can be introduced odd degree and therefore eliminate the possibility of owning a cycle graph Eulerian, then the average case would be $ O (\\ frac {1 + (3n +1)} {2}) $, as the constants are trivial, is still $ O (n) $.
For the second algorithm (search) is $ O (n) $ because:
declare a constant, num_vertices, and a variable shift. +2 Steps
attach a vertex to "chance." Match
barrier +2 steps and see. +1
step command are exchanged and fviajero fbarrera program in turn, this depends on how fast we find the Eulerian cycle.
fbarrera to compare if I end up searching for the cycle (1 transaction), compares the current vertex degree (1 stored procedure if its degree).
steps
+2 Here comes the interesting part, if the vertex degree is 1, the barrier can move forward and do the following:
- Stores your journey on the stack (1 operation) changes of position (1 transaction) to a neighbor node to find it done in about n steps depending on the extent of current vertex (n operations so), and removes the edge that ran (2 operations). n +4
- steps increases the shift. +1 Step
fviajero stores its way into an array or list, moves (1 operation) to a neighbor node to find it done in about n steps depending on the degree of current vertex and removes the edge that ran (2 operations). n +3 steps
The result is $ O ((t / 2) (2n +9)) $, where t is the number of times it turns.
Note: Actually the asymptotic complexity is lower than before but I will not get into details of numbers. Finally
constants are ignored and we are left with $ O (n) $. The problem is P , polynomial time.
data structures used
Use dimensional arrays in the first pseudocode and dimensional arrays, batteries and ready in the second. Applications
Eulerian cycle An application may be in the optimization of route maps, for example if we were asked if there is a way for a tourist trip so that they do not flown any of the paths more than once or in the extended version, which is the best cycle for tourists visiting certain places before others and without going through the same paths over than once?.
also just occurred to me that can be applied in determining the flexibility in decision problems in large institutions or companies, for example if you create a graphical model to simulate the choices that you can choose a company with edges and final states to carry out what with vertices chosen, one could know then the degree of flexibility in decisions of each state depending on whether there is an Eulerian cycle that allows return to the initial state by different options (different edges), it becomes more real if we allow the elimination of options over time, ie remove edges from time to time, either randomly or not. Curiosities
- The 7 Bridges of Königsberg were bombed and destroyed by the Allies in 1944 and only 5 were rebuilt.
- The city Königsberg was renamed Kaliningrad and is now part of Russia.
- Now you can visit the bridges with an Euler path but not an Euler cycle.
- The problem of the 7 bridges of Königsberg solved by L. Euler gave way to the topology, a branch of mathematics which is responsible for studying properties of geometric objects that have to do with the relative position between points. Sources
http://www.itl.nist.gov/div897/sqg/dads/HTML/eulercycle.html
1 2
http://www.economicexpert.com/a/Eulerian : path.htm http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK4/NODE165.HTM
3 4
http://books.google.com.mx / books? id = 7XUSn0IKQEgC & pg = PA502 & lpg = PA502 & dq = euler + cycle + Applications & source = bl & ots = z6cFQPOS0e & sig = gCQCrKXT4T2ZWCFZLVtJ9k-juhk & hl = en & ei = x-DpS5DhHoyCtgOX3IX-Bw & sa = X & oi = book_result & ct = result & resnum = 9 & ved = 0CFkQ6AEwCA # v = onepage & q & f = false Http://theoremoftheweek.wordpress.com/2009/09/29/theorem-8-eulerian-circuits/
5 6
http://www.personal.kent.edu/ ~ rmuhamma / Algorithms / MyAlgorithms / GraphAlgor / eulerTour.htm
http://mathworld.wolfram.com/EulerianCycle.html
7 8 9 http://mathforum.org/isaac/problems/bridges2.html
http:// www.cs.sunysb.edu/ ~ Skiena / combinator / animations / euler.html
10 http://mathdl.maa.org/mathDL/46/?pa=content&sa=viewDocument&nodeId=1310&bodyId = 1452 (paragraph explains each show written by L. Euler)
11 http://math.dartmouth.edu/~euler/docs/originals/E053.pdf
12 http://www.iesezequielgonzalez.com/matematicas/grafos.htm
13 http://www.mathematische-basteleien.de/house.html
14 http://books.google.com.mx/books?id=aFDWuZZslUUC&printsec=frontcover&dq=CRC+concise+encyclopedia+of+mathematics&ei=f1z0S9qxLpTukgSM_YS8Bw&cd=1
15 http://books.google.com.mx/books?id=TrXd-gxPhVYC&printsec=frontcover&dq=The+algorithm+design+manual+2&ei=x1z0S9aPFJf4lASauI2uBw&cd=1
16 ~ Jlrodri/Topgen5/introduccion.html http://www.ual.es/
Self-Assessment Review
I think make a good job with the blog report, included all requirements, add images, try to explain in the simplest way possible, on the other hand showed the algorithm that I thought to solve the problem, and some parts I asked the reader's participation, was very comprehensive and included 16 source links at the bottom for readers to find more information on the subject.
Regarding the presentation, the first few seconds at the beginning was a little nervous but after I was as time passed and I concentrated on the theory, the number of slides to show that I found exceeded 2 for the time of this opportunity but I explain them to jump and very fast, yet so focused on only those 2 slides the later example of the algorithm and was easier for the public to understand the solution to the problem of the latter form. The design of the presentation was very simple to keep everything clean, clear and concise.
participant also made the public presentation and comment a little curious about the Eulerian cycle problem afterwards. The time I was a bit late but the limit agreed but it was worth those extra seconds to the public.
0 comments:
Post a Comment