Path (graph Theory)
In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them are called terminal vertices of the path. The other vertices in the path are internal vertices. A cycle is a path such that the start vertex and end vertex are the same. The choice of the start vertex in a cycle is arbitrary.
Paths and cycles are fundamental concepts of graph theory, described in the introductory sections of most graph theory texts. See e.g. Bondy and Murty (1976), Gibbons (1985), or Diestel (2005). Korte et al. (1990) cover more advanced algorithmic topics concerning paths in graphs.
The vertices of a path are said to be connected. The vertices of a directed cycle are said to be strongly connected.
Read more about Path (graph Theory): Different Types of Paths
Famous quotes containing the word path:
“Another danger is imminent: A contested result. And we have no such means for its decision as ought to be provided by law. This must be attended to hereafter.... If a contest comes now it may lead to a conflict of arms. I can only try to do my duty to my countrymen in that case. I shall let no personal ambition turn me from the path of duty. Bloodshed and civil war must be averted if possible. If forced to fight, I have no fears from lack of courage or firmness.”
—Rutherford Birchard Hayes (1822–1893)