Talk:Path (graph theory)

Can cycles be simple?

"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)
  • Bad example, even non-simple cycles have only one of each vertex; it is the sequence of vertices that "repeats" the vertex or not (think: pointers or copies in e.g. C++). To the original question: path is defined as a sequence of edges, sequence of vertices are an emergent property. As a programmer, you would probably not include the end vertex in the list anyway. Depends how you wish to iterate the sequence of course; but makes sense to return for a given path (list of edges) a list of visited vertices and the last "current" vertex separately. --Sigmundur (talk) 12:22, 27 December 2013 (UTC)

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. --Doradus 13:58, 9 May 2006 (UTC)

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)

Definition of Path is wrong

A path is a list of edges (not a list of vertices). There is a subtle difference, since there may be more than one edge connecting two vertices. Furthermore, another restriction on paths is that no vertex may be visited more than once (except the starting/finishing vertex in the case of a cycle.) See: http://www.proofwiki.org/wiki/Definition:Path_%28Graph_Theory%29 Cowrider (talk) 01:32, 7 January 2013 (UTC)

This seems to have been fixed, but still it doesn't say sequence of edges must be non-repeating, or equivalently, ordered set, or something. --Sigmundur (talk) 12:18, 27 December 2013 (UTC)

The proofwiki.org article seems to argue that a path is normally described by a list of vertices.

> A path in is a trail in in which all vertices (except perhaps the first and last ones) are distinct.

> A trail is a walk in which all edges are distinct.

> To describe a walk on a simple graph it is sufficient to list just the vertices in order, as the edges (being unique between vertices) are unambiguous.

This definition is also supported by outside references:

> A path is a series of one or more nodes where consecutive nodes are adjacent.

[1]https://web.stanford.edu/class/archive/cs/cs103/cs103.1184/lectures/11/Small11.pdf Pillowmurder (talk) 09:43, 1 May 2024 (UTC)

this works only for simple graphs. it depends highly on the setting. for multigraphs (also known as quivers), this definition is not used. you can also see this in the quiver_(mathematics) article. the definition that either always includes a "start" node or just always includes the sequence of both the nodes and the arcs/edges is the most general: it can be applied to the most settings and is still consistent with other definitions that are more lenient. ZMBerber (talk) 15:40, 9 July 2024 (UTC)

i agree that the definition with vertices is better/correct, at least for simple graphs. vertices are necessary because we need empty paths at every node to be allowed. for multigraphs, this definition also has its problems, since there can indeed be multiple possible edges/arcs between nodes. ZMBerber (talk) 15:46, 9 July 2024 (UTC)

There are problems with this definition as well. If empty sequences are allowed (and they aren't disallowed in the article), then in graphs with at least two vertices, there is a path (the empty path) for which it cannot be determined which vertex it contains (and a path of length 0 (n) must/should contain exactly one (n+1) vertex). If empty sequences are disallowed, the following "A graph is connected if there are paths containing each pair of vertices." does not hold for a graph with just one vertex.

I think "a (nonempty) list of vertices where consecutive vertices are joined by an edge" is a usable definition, because by default we talk about ordinary graphs, not multigraphs. But a fully general definition could be "a sequence (v0, e0, v1, e1, ..., v_n, e_n, v_{n+1}), where v_i are unique vertices and e_j edges such that (v_k, v_{k+1}) = e_k". Susy 11 (talk) 11:58, 20 April 2020 (UTC)

The "fully general definition" you give is in my opinion the best one. Empty paths/walks should exist. And not only one empty path/walk, but for every node there shall exist the empty path/walk at that node: The one that starts at a node and never moves anywhere. This is also consistent with quiver algebras, where this becomes very relevant. I would, however, suggest writing the sequence as (v₀, e₁, v₁, e₂ …, v_{n − 1}, e_n, v_n) ZMBerber (talk) 15:30, 9 July 2024 (UTC)

A path with no vertices is problematic, because it doesn't have the usual property of paths that there is one more vertex than edges. However, a path with one vertices and no edges is standard, non-problematic, and sometimes necessary. —David Eppstein (talk) 18:02, 9 July 2024 (UTC)

I was indeed talking about a path with no edges/arcs, and one vertex. This is what is usually called the empty path (or trivial path, I think?) at a vertex. I agree that a path with no vertices is problematic. ZMBerber (talk) 11:17, 10 July 2024 (UTC)

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)

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)

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)

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)

Ok, then the second sentence The first vertex is called the start vertex and the last vertex is called the end vertex should be changed to reflect this case. Albmont (talk) 12:54, 16 March 2009 (UTC)

s-t path

What's an s-t path? 130.83.106.165 (talk) 15:49, 25 October 2011 (UTC)

A path from vertex s to vertex t? —David Eppstein (talk) 16:29, 25 October 2011 (UTC)

Internally disjoint paths

I changed "internally vertex-disjoint" to "internally disjoint". Paths P, Q with the same endpoints, having length 1, are internally vertex-disjoint even if they are identical, because although they have the same edge they have no internal vertices. Zaslav (talk) 22:53, 15 March 2024 (UTC)