Talk:Cycle (graph theory)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-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:
Start Class
Mid Importance
 Field: Discrete mathematics


Diagram(s)[edit]

It would be nice to have a simple diagram for each example. —ScouterSig 18:19, 6 October 2007 (UTC)

Contradictions[edit]

There are too many contradictory interwoven definitions for cycle in graph theory. My text describes it as a closed walk that has no repeating edges or vertices. Walk, trail, circuit, path, and cycle should have clear distinct meanings.


Open - two 'end' vertices; Closed - starts and ends on same vertex

Walk - allows repeated vertices, edges, can be open or closed.

Trail - open walk that may have repeating vertices. Edges can not repeat.

Circuit - closed walk; vertices may repeat, edges may not.

Path - open walk; edges and vertices can not repeat.

Cycle - closed walk; edges and vertices may not repeat.

Algorithms for cycle detection in graph theory[edit]

Can someone name algorithms to find cycles in a graph? (The article cycle detection is about cycle detection within another mathematical topic). --Abdull (talk) 20:55, 3 August 2010 (UTC)

The answer I know as standard is given here. Feel free to add it to the article. Rp (talk) 20:44, 10 August 2010 (UTC)
I started a section, Cycle (graph theory)#Cycle detection. Vadmium (talk) 05:45, 14 September 2011 (UTC).
Sorry, but the answers on that stackoverflow page are generally useless. It also fails WP:RS for use as a source in Wikipedia. In the case of undirected graphs, DFS is the fastest way to detect if there is a cycle (BFS is not good for that). It is a common exercise in algorithms textbooks to show that it only takes O(n) time. In the case of directed graphs, a suitable topological sorting algorithm is the best (this is the only correct answer on the page). If you want to find all cycles, that is a harder problem for which there are specialised algorithms. McKay (talk) 06:57, 14 September 2011 (UTC)
In what sense are the "check whether DFS has a back edge" or "find strongly connected components and check whether any of them are nontrivial" answers incorrect for digraphs? Running Kahn's algorithm until either topologically sorting the whole graph or finding a subgraph in which all vertices have nonzero indegree, and then tracing backwards through the incoming cycles, will also work of course. —David Eppstein (talk) 07:04, 14 September 2011 (UTC)
Using a strong component finder is not wrong, but would be a bit of sledge-hammer. Most strong component algorithms use either one DFS with complex bookkeeping, or two DFS's, so why not just watch for back edges? A topological sorting algorithm would be ok, but the simplest of those is just a DFS anyway. McKay (talk) 03:19, 26 September 2011 (UTC)

Merge[edit]

This article should be merged with the much more complete:

http://en.wikipedia.org/wiki/Cycle_graph

This article even references that article. How does that make sense? StatisticsMan (talk) 13:46, 27 September 2011 (UTC)

When I was reading these articles I think I concluded that this Cycle (graph theory) article was about a more general “closed walk” where repeated vertexes are allowed, and Cycle graph was only about the more specific “simple” cycle where only the “start and end” vertex repeats. If no merge happens, perhaps someone should make this distinction clearer. Vadmium (talk, contribs) 14:11, 27 September 2011 (UTC).
To me, the distinction is that Cycle graph is about graphs that consist only of a single cycle, whereas this article is about cycles in larger graphs. —David Eppstein (talk) 14:47, 27 September 2011 (UTC)
+1. Exactly the same reasoning has been made on the French wikipedia in 2010 (see article history). --MathsPoetry (talk) 09:52, 7 April 2013 (UTC)

One more diagram[edit]

Cycles and minimal degree.svg

Be a graph of minimal degree \delta \ge 2. It has a cycle of length at least \delta + 1. This diagram helps demonstrate this assertion. It is provided with the hope that it might help. --MathsPoetry (talk) 09:52, 7 April 2013 (UTC)

Definition Needed[edit]

I don't know enough about this topic to do this, but the term "cycle" needs to actually be defined in the first paragraph (and preferably the first few sentences). 149.43.80.121 (talk) 18:42, 19 June 2013 (UTC)