Graph Path

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

• AKA: Trail.
• Context:
  • It can range from being a Simple Graph Path to being a Complex Graph Path.
  • It can range from being a Directed Path to being an Undirected Path.
  • It can range from being a Finite Path to being an Infinite Path.
  • It can be represented by a Graph Path Record.
  • It can be an Optimal Graph Path, depending on the presence, of a Graph Capacity Function (such as a shortest path or a longest path).
  • It can be a member of a Graph Path Population, such as a graph path cluster.
  • …
• Example(s):
  • a Eulerian Cycle.
  • a Website Navigation Path.
  • …
• Counter-Example(s):
  • a Graph Cycle.
  • a Random Walk.
• See: Connected Graph, Graph Path Clustering Task, Graph Random Walk.

---

---

References

2012

• http://en.wikipedia.org/wiki/Glossary_of_graph_theory#Walks
  • 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.
• http://en.wikipedia.org/wiki/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.
    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.

2009

• http://en.wikipedia.org/wiki/Glossary_of_graph_theory
  • path: A route that does not pass any edge more than once. If the path does not pass any node more than once, it is a simple path.

---