Talk:Eulerian path

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated C-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
C Class
Mid Importance
 Field: Discrete mathematics

Error in article[edit]

From Discrete Mathematics, 4th Ed., by Dossey, Otto, Spence, and Vanden Eynden: Thm 3.5: "Suppose a multigraph G is connected. Then G has an Euler circuit iff every vertex has even degree. Furthermore, G has an Euler path iff every vertex has even degree except for two distinct vertices, which have odd degree. When this is the case, the Euler path starts at one and ends at the other of these two vertices of odd degree." Is this contradicting the article? I can't tell, and I don't want to edit it, being a mere CS major and not an expert in mathematics. --Aciel 02:05, 7 May 2005 (UTC)

I do not see how this is contradicting the article. Can you give a more detailed explanation what you refer to ? MathMartin 17:08, 7 May 2005 (UTC)
I also don't understand what point is being made, but I'll note that the quoted theorem from Dossey et al is wrong. To have an Euler path, one needs at most two vertices of odd degree, not exactly two. --Zero 03:46, 8 May 2005 (UTC)
In response to the first question, I think you may be confusing Euler paths and circuits. In response to this last comment, well it depends how you define euler paths, just like how you define natural numbers. For example, the starting and ending vertices can be defined to be distinct, as in "Discrete Mathematics" Third Edition, by Susanny S. Epp. Also an Euler path/circuit can be defined to be a graph/subgraph or a sequence.
For reference, the above mentioned definition: "Let G be a graph, and let v and w be two distinct vertices of G. An Euler path from v to w is a sequence of adjacent edges and vertices that starts at v, ends at w, passes through every vertex of G at least once, and traverses every edge of G exactly once."
124.177.66.44 (talk) 10:30, 29 January 2008 (UTC)

Edge Disjunct?[edit]

The article makes a reference to edge disjunct cycle graphs, but neither this article, nor the cycle graphs one that it links to, define edge disjunct. Eythian 05:52, August 11, 2005 (UTC)

Missing def[edit]

"diconnected" is linked to the glossary but not in the glossary. I assume it means something along the lines of "strongly connected". Deco 05:56, 30 August 2005 (UTC)

I'll change it to just "connected", since any type of connectivity implies strong connectivity when the in-degree and out-degree are equal at every vertex. (Proof: if the digraph is connected but not strongly connected, there is a strong component that has edges coming in but no edges coming out. Now count the heads and tails of edges inside that strong component to find a contradiction.) --Zero 11:14, 30 August 2005 (UTC)

Pentagram[edit]

Is a pentagram a unicursal star? --South Philly 03:39, 11 July 2006 (UTC)

image?[edit]

Why is an uneulerian path the only picture here?--Josh Rocchio 01:15, 29 September 2006 (UTC)

Missing proof of Euler Tour[edit]

I'm missing a proof which proofs that if G a connected graph with an Euler tour if and only if every vertex of V(G) has an even degree. Is it somewhere else on the wiki? Otherwise I'd like to give one. --Noud 15:57, 29 July 2007 (UTC)

I came to this article to find a proof, but unfortunately there is none. Please give yours! Thanks, --Abdull (talk) 09:17, 16 July 2008 (UTC)

'path'[edit]

This article says "an Eulerian path is a path (graph theory)", and the path article says that 'path' normally means a 'simple path', but an Eulerian path does not have to be a simple path, does it? Perhaps some mention should be made of this. Can someone confirm this? ssepp(talk) 08:47, 15 September 2007 (UTC)

The term "path" in graph theory and in computer science has contradictory meanings. Computer scientists seem to mean any trail (no repeated vertices; there may be repeated edges) or walk (any vertices or edges may be repeated). In graph theory a path must have no repeated vertices or edges. I will revise the article when I can to remove the unfortunate ambiguity of the word "path". Zaslav (talk) 04:21, 27 April 2010 (UTC)

From Glossary of graph theory#Walks:

  • "A walk is an alternating sequence of vertices and edges."
  • "A trail is a walk in which all the edges are distinct."
  • "Traditionally, a path referred to what is now usually known as an open walk. Nowadays, when stated without any qualification, a path is usually understood to be simple, meaning that no vertices (and thus no edges) are repeated."

I often see "path" used when "walk" would be more accurate, but it's not wrong to use "path" to mean "an alternating sequence of vertices/edges". Justin W Smith talk/stalk 05:54, 28 April 2010 (UTC)

If this POV statement you quote is correct, "traditionally" must refer to 50 years ago. In graph theory, that's a long time! Why would we use 50-year-old obsolete terminology?
I don't understand how you can say "often see path"! I don't. Please provide citations. I've read a lot of graph theory. "Path" is wrong if you're following the general usage in graph theory. If you agree "path" is wrong, why are you reverting? It makes no sense. Please give a better explanation. Zaslav (talk) 16:46, 28 April 2010 (UTC)
Are you claiming that this article should be renamed "Eulerian trail"? If we strictly define "path" to only mean "simple path", then the article would need to be renamed as such. Justin W Smith talk/stalk 18:33, 28 April 2010 (UTC)
Yes, I am! But I'm not going to spend any more time on it. Zaslav (talk) 16:36, 29 April 2010 (UTC)
Strictly speaking "Eulerian paths" are not "paths" because they are not simple. Out of curiosity I just did a search for "Eulerian path" in articles since 2000 on google scholar and got over 400 hits. As I said before, I'm ok with using "path" in a more general sense (i.e., to mean a non-necessarily-simple walk). Justin W Smith talk/stalk 18:40, 28 April 2010 (UTC)

@Zaslav: You said, "I don't. Please provide citations." Here you go...

For comparison (results restricted to papers since 2000):

It appears "eulerian path" and "eulerian cycle" are the most commonly used terms, and Wikipedia should reflect that. Justin W Smith talk/stalk 18:47, 28 April 2010 (UTC)

Well, thanks for doing the research. A few remarks: My feeling is that the results partially reflect carelessness in terminology, which makes sense because most people even in math and computer science are not very careful. If you were to make the search more thorough, you would ask about "euler path/trail"; I wonder what you'd find. I also wonder how many of these "path" and "cycle" usages are in computer science, where those terms seem to be used indiscriminately for walks, trails, or paths in the graph-theory sense. Also, I don't think the frequencies of "cycle" vs. "circuit" are that different; I would give some weight to correctness/consistency of terminology, not only frequency of usage. (When one term is rare, it's a different matter.) Also, while checking all kinds of terminology, there's "eulerian/euler tour", tour = circuit = closed trail. But seriously, we've spent enough time on it. Thanks again for the data. Zaslav (talk) 16:46, 29 April 2010 (UTC)

At MathSciNet, "eulerian trail" beats "eulerian path" 54 to 33. In my experience, many graph theorists who call it "eulerian path" would never otherwise use the word "path" for a self-intersecting walk, in other words they don't think an eulerian path is a path. Zerotalk 17:07, 29 April 2010 (UTC)

That sounds exactly right to me. Did you also check "euler path/trail/walk"? Zaslav (talk) 21:44, 1 May 2010 (UTC)
I did it again using "euler" as well as "eulerian", plus plurals: cycle 39, tour 106, circuit 69, path 62, walk 16, trail 83. Zerotalk 05:17, 2 May 2010 (UTC)
Thanks again! That's tour (106), circuit (69), cycle (39) for closed, and trail (83), path (62) for open, with walk (16) ambiguous. I'm surprised at how many say tour. No one term is totally dominant. "Path" is not favored. Zaslav (talk) 15:23, 2 May 2010 (UTC)

John Dwyer paper on Eulerian circuits[edit]

I've reverted the latest edit, which referenced http://www.algana.co.uk/Research/Circuits.pdf by John Dwyer. This paper is not a peer-reviewed publication and contains no proofs. Equation 34 of this paper, which claims to have a closed formula for the number of Eulerian circuits in a complete graph on n vertices, gives values for K5 and K7 appear to contradict those given in the paper "Asymptotic Enumeration of Eulerian Circuits in the Complete Graph" by McKay and Robinson. —Preceding unsigned comment added by Myasuda (talkcontribs) 15:30, April 6, 2008

Error in source code[edit]

The link to C++ source code http://tuxv.blogspot.com/2007/05/eulerian-path.html should be removed since the source code is, beside a number of bugs, incorrect. It generates a path (or cycle) which visits each edge *at most* once and not *exactly* once, thus it is simply *not* Eulerian. —Preceding unsigned comment added by 58.186.123.121 (talk) 18:20, 29 May 2008 (UTC)

Semi-Eulerian[edit]

I added a mention of semi-Eulerian, because that's a not uncommon term used, but we should also have an example for that. While Pn of course works, perhaps something that's also simple, but slightly more interesting like Image:Semi-Eulerian graph.png would be good. Unfortunately I don't know of any easy programs to label that more nicely and make it look like the other two images in the article. Can somebody help out? - Taxman Talk 14:15, 31 May 2008 (UTC)

self-intersecting path[edit]

Please define self-intersecting path. Thanks, --Abdull (talk) 09:17, 16 July 2008 (UTC)

WTH is a Even Degree?[edit]

WTH is a Even Degree? —Preceding unsigned comment added by 193.136.166.125 (talk) 20:28, 6 April 2009 (UTC)

As I understand evenness and oddness is determined by counting the number of edges associated with a given vertex. For a vertex to be even it must have an equal number of "incoming" and "outgoing" edges. Odd vertices do not, which is why there cannot be more than two for the graph to be Eulerian.
Should this be explained somewhere in the article?Reaster (talk) 16:27, 10 August 2009 (UTC)

Faster algorithm than Fleury[edit]

Isn't there a faster recursive O(edges+vertices) algorithm than Fleury? I can't remember the name, but it was like start at any vertice (if we are finding a eulerian path, start at a vertice of odd degree), if the vertice has degree 0, add it to the circuit and return, else for each neighbour, delete the edge between the vertice and the neighbour and recurse on the neighbour. Rand0m011 (talk) 22:48, 18 April 2009 (UTC)

I'm sure it can be done in O(#edges) time but we need to find a reference. McKay (talk) 06:51, 19 April 2009 (UTC)
I may be a bit late, but I was just looking into this today and yes, here is a link [1]. Fleury's algorithm seems impractical because you have to check for bridges at each step. That cycle finding algorithm is cool but kind of sneaky. Is is something we want in the article? Alejandro Erickson (talk) 18:44, 4 June 2010 (UTC)
The "algorithm" at that link is wrong and useless. But we need a linear time alg for this page. Zerotalk 10:10, 5 June 2010 (UTC)

Commentary in the article[edit]

The following commentary on the article was at the end of the introduction. I've moved it here to discuss. WRONG! A graph made by starting from an Eulerian graph and adding any number of isolated vertices is not connected but still Eulerian!

This is correct... but rather pedantic. Perhaps it could be discussed later in the article? —Preceding unsigned comment added by 76.29.6.37 (talk) 00:15, 28 January 2010 (UTC)

Pedantic, is it? Well don't let me get in the way of amateur academicians happily editing away at anything mathematical in sight, totally unconcerned with such arcane notions as rigor. You will actually find that the article already has a correct exposition further down, where it says something to the effect of connected simple graphs will be Eulerian if and only if all their vertices have even degree. Quite different from what is presented in the 'helpful' introductory paragraph, isn't it? Unless you find arguing over such minute differences already exhausts your monthly allowance of 'pedantism'. —Preceding unsigned comment added by 83.132.117.74 (talk) 00:31, 28 January 2010 (UTC)
Well, given that the sentence in question starts with "In 1873, Carl Hierholzer published the first complete characterization", we have to check what he (Carl Hierholzer) actually proved... --Martynas Patasius (talk) 21:52, 28 January 2010 (UTC)
Obviously, he (Carl Hierholzer) did not prove anything as previously stated in the introductory paragraph, since you cannot prove a falsehood. (And it is immediately obvious, i think, that what was previously asserted was false; in fact, the correct statement actually appeared further down the article.) The interesting aspect to all this is that when some imbecile originally wrote the introduction, no one cared or even noticed that it was wrong; but as soon as you point it out it, somehow it becomes paramount to make sure we're not incurring in 'Original Research'... Wikipedia has become a bureaucratic joke. —Preceding unsigned comment added by 83.132.234.45 (talk) 22:09, 28 January 2010 (UTC)
Well, I wouldn't say it is as obviously false, as you seem to think. The statement "further down the article" doesn't seem to be incompatible with either version. Also, let's take an example - a graph with several vertices and no edges. Is it an Eulerian graph? Does it have an Eulerian cycle? Well, does a graph having no cycle have an Eulerian cycle? If we word the question like this, the answer seems to be "No.". On the other hand, if we take your definition, then the graph in question would be an Eulerian graph, as it has no vertex with an odd degree... I am not going to claim that this example obviously disproves anything, but I guess it should prove that a source wouldn't hurt... --Martynas Patasius (talk) 22:31, 28 January 2010 (UTC)
But you misunderstand: What i said is that if you take a (conventional, ie, connected) Eulerian graph and then add isolated vertices, you still have an Eulerian graph. That has no bearing on whether an edgeless graph is itself an Eulerian graph (since if you start from a conventional Eulerian graph, you'll already have edges in it). But, to answer your question directly, yes, i consider an edgeless graph to be an Eulerian graph, just as it is customary to say that (for instance) the empty set is a closed set (in the topological sense), but also an open set, since it trivially verifies the properties needed in both cases.
So, I found a random article (C. ST J. A. Nash-Williams, "Connected Detachments of Graphs and Generalized Euler Trails", J. London Math. Soc. s2-31: 17-29, [2]) that defines the "Eulerian graph" as both connected and having no vertices of odd degree... Of course, it doesn't prove anything by itself, but at least it shows that the falsity of the statement in question is not "immediately obvious"... --Martynas Patasius (talk) 22:48, 28 January 2010 (UTC)
Precisely, the article defines; it doesn't prove. That is, at any point, you're free to say that you only allow a graph to be Eulerian if it is also connected (which is reasonable, since the unconnected variants are uninteresting). The previous introduction to the Wikipedia article, however, claimed that someone (Hierholzer) had proved that Eulerian graphs were connected, when, using the definition of Eulerian graph previously offered by the article, this isn't true: The definition in the introduction didn't require Eulerian graphs to be connected. If you allow unconnected Eulerian graphs, these will, in fact, exist. Now, if you know your way around graphs, that little confusion is harmless; you'll always know what the other person is referring to. But in an encyclopedia, this is a grave error. It might induce someone to think that Eulerian implies connectedness, as, for example, a graph being complete actually implies connectedness.
Ah, finally - a source that shows your version might be considered to be generally accepted - Weisstein, Eric W. "Eulerian Graph." From MathWorld--A Wolfram Web Resource. [3] (why didn't I look at it from the beginning..?). Although, of course, it would still be nice if someone who understands German better than I do would check if the Hierholzer's article (C. Hierholzer "Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren" Mathematische Annalen VI (1873), 30–32. [4]) uses the same definition as this (Wikipedia's) article. Actually, it seems to be at least somewhat different: looks like he considered graphs with "keiner oder zwei ungerade Knottenpunkte" (none or two vertices with odd degrees?), thus the note in this (Wikipedia's) article ("The first complete characterization of connected graphs that have an Eulerian circuit was published in 1873 by Carl Hierholzer, [...]") seems to be inexact (looks like he considered the graphs with Eulerian cycle or Eulerian path)... --Martynas Patasius (talk) 01:01, 29 January 2010 (UTC)
Don't rely on this MathWorld article - it's quite messy. E.g., it talks about connected Eulerian graphs and shows illustration of non-connected ones. And the definition given there works only for connected graphs. I've already reported these problems to MathWorld's team. Maxal (talk) 01:56, 29 January 2010 (UTC)

O( | V | + | E | ) complexity[edit]

So, how does the cycle finding algorithm have a O(n + m) time complexity? It does

3          pick an incident vertex v and remove (u,v) from E

|E| times. If the graph is represented with a linked list removing each edge costs O(|E|). If it's represented with a matrix removing an edge costs O(1), but picking an incident vertex costs O(|V|). So step 3 costs O(|E|) with a linked list graph, and it has to be done |E| times, so the time complexity can't be smaller than O(|E| ^ 2). If it's with a matrix it can't cost less than O(|E| * |V|). What am I missing something here? Is there a quick way to delete an edge that I don't know? Shinra.Electric.Power.Company (talk) 22:12, 29 May 2011 (UTC)

With an adjacency list structure, the while loop can be executed in constant time per incident edge plus constant overhead. This is not entirely trivial because of the requirement to "delete" each edge, which means that when (u,v) is deleted, (v,u) must be deleted too (I assume we are working on a undirected graph). Simply marking the edge as deleted in a standard adjacency list structure won't do since the call find_tour(u) can be made many times for a single vertex u and we don't want to have to skip over the deleted edge multiple times. One solution is to represent the adjacency lists as doubly-linked lists, since these allow a node to be deleted in constant time when the position of the node is known. This is also more tricky than it looks because the while loop has to be implemented in a way that doesn't break when recursive calls delete nodes from the list being scanned. The constant time overhead per call to find_tour() adds up to O(|E|+1) altogether since there is at most |E|+1 calls. So the total cost is O(|E|+1). The V is not required since the algorithm only scans one component of the graph. Some people would simplify O(|E|+1) to O(|E|) but I don't think that is correct. McKay (talk) 01:02, 30 May 2011 (UTC)
I don't understand exactly your method of deleting an edge in constant time, but it doesn't matter; the algorithm can definitely be done in O(|E|) (or O(|E|+1)) in other ways I didn't think before (using pointers to booleans for the edges and always picking the first edge in the list so you only go through the list once and it doesn't become a problem if some edges are marked). Shinra.Electric.Power.Company (talk) 01:07, 1 June 2011 (UTC)
See Doubly linked list#Removing a node for node deletion. Marking edges does not suffice because the whole list of neighbours is scanned multiple times for each vertex. There is not just a single call to find_tour(u) for each vertex u like there is for other algorithms like depth-first search. There can be many calls to find_tour(u) for the same vertex u active even at the same time, because the recursion follows a path in the graph that can repeatedly intersect itself. It is required for a good running time that the total for all the scans of the neighbours of u be proportional to the degree of u. So when one of the scans deletes an edge, the other scans must not see it at all even just to skip it. McKay (talk) 02:04, 1 June 2011 (UTC)

Pronunciation[edit]

Does anyone know who made Fleury's algorithm?24.123.191.50 15:58, 16 November 2006 (UTC)

someone hook up the pronounciationAshwinr 14:31, 9 August 2006 (UTC)

    Sounds like oiler, but I don't know how to link pronunciations 144.13.15.245 15:36, 21 September 2007 (UTC)

Unicursal redirects to here. There should be an explanation of how unicursality (?) relates to an Eulerian path so that the link doesn't seem confusing. moink 14:54, 11 Apr 2004 (UTC)

Strange question I suddenly got curious about[edit]

If, in a connected undirectional graph, all vertices are of degree 4, does there necessarily exist an Eulerian path with the additional criterion that every vertex is visited once before any are revisited? 2.25.121.100 (talk) 17:48, 22 June 2011 (UTC)

No. An easy counterexample is three vertices in a triangle, each also having a loop connecting it to itself. 213.249.135.36 (talk) 19:27, 26 June 2011 (UTC)

Connected?[edit]

I notice the definition given does not state the graph must be connected. Discrete Mathematics by Richard Johnsonbaugh states that it must. Thoughts? What does your reference book say?Handsofftibet (talk) 12:06, 23 August 2011 (UTC)

Who cares whether the text says it or not, it's true: the graph must be connected. —David Eppstein (talk) 16:03, 23 August 2011 (UTC)
There are obviously (trivial examples of) graphs that satisfy the definition given in this article that aren't connected, so maybe you can rephrase your response so it's a little more helpful? Cheers, Ben (talk) 11:30, 24 August 2011 (UTC)
Oh, ok. graphs, in general, need not be connected. In order to be Eulerian, a graph must not only have even degree, but also be connected. I thought this question was referring to textbooks that made the mistake of leaving out the connectivity condition, but maybe I'm misreading? —David Eppstein (talk) 16:04, 24 August 2011 (UTC)
Ok, I think you're right and there is some confusion, so allow me to be careful for a minute. From the introduction:
The term Eulerian graph has two common meanings in graph theory. One meaning is a graph with a Eulerian circuit, and the other is a graph with every vertex of even degree. These definitions coincide for connected graphs.
This infers that your connectedness requirement isn't universal, otherwise why not just say that these two definitions are equivalent? So, it's easy to see that the two definitions are not equivalent for disconnected graphs. Now given the definition of an Euler cycle in this article:
In graph theory, an Eulerian trail is a trail in a graph which visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is a Eulerian trail which starts and ends on the same vertex.
we see that in the disconnected case the sets of graphs satisfying either of the two definitions aren't disjoint either: consider the graph with two vertices and a single loop - it clearly satisfies both definitions. However, according to Johnsonbaugh:
In honor of Euler, a cycle in a graph G that includes all of the edges and all of the vertices of G is called an Euler Cycle.
In which case, my example graph fails to have an Euler cycle. It is, however, Eulerian according to (at least on of) the definitions in this article, but not Eulerian according to your connectedness requirement.
I think the point is: this is all a big mess. We're going to have get some things down very explicitly in this article or readers aren't going to have a hope. If you agree with that, then maybe we can start to put forward some suggestions on how best to do that. Cheers, Ben (talk) 22:50, 24 August 2011 (UTC)
Ok, I see what you mean: the necessary condition isn't connectivity, it's a weaker condition that involves connectivity only of the nonzero-degree vertices. I've corrected the "properties" section of the article to take this into account. I think the rest is still ok because it generally does not try to provide strict "if and only if" characterizations, only sufficient conditions. —David Eppstein (talk) 23:50, 24 August 2011 (UTC)

The text reflects the fact that some sources use "Eulerian" or "Euler" to mean "all degrees are even" rather than "has an Eulerian circuit". There is an example cited, and it cites two others. I see this reasonably often, especially in enumeration papers. McKay (talk) 03:11, 25 August 2011 (UTC)