Graph Path

(Redirected from graph path)
Jump to navigation Jump to search

A Graph Path is a graph walk with no repeated graph edges or graph nodes.



    • QUOTE: Traditionally, a path referred to what is now usually known as an open walk. Nowadays, when stated without any qualification, a path is usually understood to be simple, meaning that no vertices (and thus no edges) are repeated. (The term chain has also been used to refer to a walk in which all vertices and edges are distinct.) In the example graph, (5, 2, 1) is a path of length 2. The closed equivalent to this type of walk, a walk that starts and ends at the same vertex but otherwise has no repeated vertices or edges, is called a cycle.
    • 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.

      File:Directed cycle.svg
      A directed cycle. Without the arrows, it is just a cycle. This is not a simple cycle, since the blue vertices are used twice.

      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.