Talk:Cycle (graph theory)

This is the talk page for discussing improvements to the Cycle (graph theory) article.
This is not a forum for general discussion of the article's subject.

Put new text under old text. Click here to start a new topic.
New to Wikipedia? Welcome! Learn to edit; get help.

Article policies

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL

Diagram(s)

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

Contradictions

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

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)[reply]

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)[reply]

I started a section, Cycle (graph theory)#Cycle detection. Vadmium (talk) 05:45, 14 September 2011 (UTC).[reply]

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)[reply]

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)[reply]

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)[reply]

Merge

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)[reply]

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).[reply]

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)[reply]

+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)[reply]

One more diagram

Be a graph of minimal degree $\delta \geq 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)[reply]

Definition Needed

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)[reply]

I've cleaned up the top section to only include the definition used in the rest of the article, and added a section about the possible alternative definitions. --Blacklemon67 (talk) 23:43, 15 May 2016 (UTC)[reply]

ah, nevermind, got reverted --Blacklemon67 (talk) 23:48, 15 May 2016 (UTC)[reply]

The point is that there are multiple inconsistent definitions and we should not be taking sides over which one is the right one. Rather, we should teach people that there are multiple inconsistent definitions. —David Eppstein (talk) 23:50, 15 May 2016 (UTC)[reply]

That is understandable. My main intention was to reduce the size of the top section. I've split it into a definitions section without changing any of the text. I think that's a fair compromise. --Blacklemon67 (talk) 00:02, 16 May 2016 (UTC)[reply]

Yes, that looks ok to me. —David Eppstein (talk) 00:57, 16 May 2016 (UTC)[reply]

Simple cycles may also be described by their sets of edges?

The article says "Simple cycles may also be described by their sets of edges".

It seems that it is false, because a cycle and its "reverse" cycle have the same set of edges, but these two cycles are different. --VictorPorton (talk) 18:50, 6 December 2014 (UTC)[reply]

For directed graphs the reverse is not a cycle. And for undirected graphs many (most?) uses of cycles treat them as undirected subgraphs, not caring about the distinction between walking one way or the other around the cycle. —David Eppstein (talk) 20:39, 6 December 2014 (UTC)[reply]

David, what you say here is obviously true, but a mathematical article in Wikipedia must be exact, now it isn't. Please edit it. — Preceding unsigned comment added by VictorPorton (talk • contribs) 20:57, 6 December 2014 (UTC)[reply]

Accuracy is important, but it's not actually as important as readability. And if you can edit this talk page, you're capable of editing the article yourself. —David Eppstein (talk) 21:29, 6 December 2014 (UTC)[reply]

I am not an expert in graph theory. I leave editing to experts. --VictorPorton (talk) 21:40, 6 December 2014 (UTC)[reply]

Needs a section on directed cycles

104.228.101.152 (talk) 22:06, 29 November 2017 (UTC)[reply]