Talk:Path (graph theory)
From Wikipedia, the free encyclopedia
"A path is called a cycle if its start vertex is also its end vertex."
"A cycle with no repeated vertices is called simple cycle."
that means every cycle isn't simple cycle because start vertex and end vetex are same???--Sukolsak 10:25, 8 May 2005 (UTC)
- They are the same, but they are not repeated. I have my mother and my brother has his mother, but there are no two mothers in our family. Mikkalai 02:09, 9 May 2005 (UTC)
Contents |
[edit] This article is a glossary
Does this article add anything beyond what's in Glossary of graph theory? Maybe we should just merge it in there. --P3d0 13:58, 9 May 2006 (UTC)
[edit] Expert tag
I removed the expert tag; if there are specific concerns, please list them on the talk page. I added an unreferenced tag; just one or two standard reference texts would suffice, but I am not familiar with any. CMummert 19:58, 15 July 2006 (UTC)
[edit] Cite sources?!
Why the devil should anyone need to cite sources for this page!? This is all such universal knowledge I don't even know what you would cite! Wikipedia is ridiculous.
- I think we should cite the appropriate pages of a graph theory text or three, in the style suggested by Wikipedia:Scientific citation guidelines: a sentence near the start saying that this is elementary material that can be found in any graph theory text such as (whatever citation we end up using). Obviously, it's too basic to find much in the way of relevant journal articles or for line-by-line citation to be useful, but that doesn't mean it's impossible for any citations to be useful. —David Eppstein 00:24, 13 November 2006 (UTC)
[edit] Some problems and a suggested fix
(i) The article merely requires existence of an edge between consecutive vertices, which would be fine if the article on graphs only allowed one edge from one vertex to another but it doesn't, in fact it has a figure showing one with three edges. To fix this requires specifying the edge between each consecutive pair. One might think to fix it by redefining "path" to be a sequence of edges, but that then leaves unclear what it means to be a path of zero length. One solution would be to define a path as a nonempty alternating sequence of vertices and edges such that every edge is preceded by its start vertex and followed by its end vertex, with no other constraints, but that seems a bit clunky.
(ii) The article says that every path has a start vertex and an end vertex, implying that all paths are finite, yet articles that deal with infinite paths rely on this article for the definition of "path," causing confusion. In contrast the article on sequences allows both infinite and bi-infinite sequences. So, can there be a path with a start vertex but no end vertex, or conversely, or neither? And which text authorizes each of these decisions? The clunky definition I suggest in (i) allows all of these, by not imposing any endpoint constraints.
(iii) What does "Note that the choice of the start vertex in a cycle is arbitrary" mean? That cycles don't have a well-defined start and end, or that the start and end don't matter, or what? Is there any reason not to simply delete this sentence?
My suggested fix is to provide the following rigorous definition, preferably not at the start which should retain its current informal character, but somewhere so that those bothered by issues like those raised in (i)-(iii) have somewhere to go. Define a path in a graph G to be a map p: P → G from a path graph P to G. A path graph is a nonempty connected acyclic directed graph such that every vertex has in-degree and out-degree at most 1 each. These conditions permit at most one vertex to have in-degree 0, called the start of P when it exists, and dually a possible end of P with out-degree 0. The start or end of a path in G if any is then the image under p of the start or end of P. The length of a path is the number of edges in P, and is finite if and only if P has both a start and an end. There is one path graph of each finite length, and three infinite path graphs, lacking respectively an end, a start, and both. A path of length zero is called an empty path even though its domain P is a nonempty graph (by virtue of containing a vertex). A simple path is an injective map. A cycle in G is a finite nonempty path in G mapping the start and end of P to the same vertex in G; a cycle in G is simple when the only vertices mapped to the same vertex in G are the ends. A self-loop is a cycle of length one. Every graph has one empty path at each vertex (which cannot be considered cycles or the only acyclic graph would be the empty graph). The finite paths in any graph G form a category under concatenation, called the free category on G. --Vaughan Pratt (talk) 22:44, 2 February 2009 (UTC)
[edit] Graph shown
'The length of a path is the number of edges that the path uses, counting multiple edges multiple times. In the graph shown, (1, 2, 5, 1, 2, 3) is a path of length 5, and (5, 2, 1) is a simple path of length 2.'
This probably refers to the graph from several other articles including the graph article, but it is not shown here...
- Removed that sentence... ElommolE 11:40, 12 July 2007 (UTC)
[edit] Empty paths
Are path of zero length are counted as paths? The theory of connectivity is smoother if to allow zero-length paths. But what is the convention, to allow zero-length paths or to not allow.
77.125.7.194 (talk) 12:26, 26 December 2007 (UTC)
[edit] Infinite paths
The definition does not explicitly say that the sequence must be finite. Is there any case where infinite (either to +infty or from -infty) paths are useful? Albmont (talk) 19:10, 13 March 2009 (UTC)
- Yes. See for instance König's lemma. —David Eppstein (talk) 21:08, 13 March 2009 (UTC)
