cover image

Path (graph theory)

Sequence of edges which join a sequence of nodes on a given graph / From Wikipedia, the free encyclopedia

Dear Wikiwand AI, let's keep it short by simply answering these key questions:

Can you list the top facts and stats about Path (graph theory)?

Summarize this article for a 10 year old

SHOW ALL QUESTIONS

In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct (and since the vertices are distinct, so are the edges). A directed path (sometimes called dipath[1]) in a directed graph is a finite or infinite sequence of edges which joins a sequence of distinct vertices, but with the added restriction that the edges be all directed in the same direction.

Snake-in-the-box_and_Hamiltonian_path.svg
A three-dimensional hypercube graph showing a Hamiltonian path in red, and a longest induced path in bold black.

Paths are fundamental concepts of graph theory, described in the introductory sections of most graph theory texts. See e.g. Bondy & Murty (1976), Gibbons (1985), or Diestel (2005). Korte et al. (1990) cover more advanced algorithmic topics concerning paths in graphs.

Oops something went wrong: