Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Path (graph theory)
open-in-new
<h2 id="definitions">Definitions</h2> <h3>Walk, trail, and path</h3> <ul><li>A walk is a finite or infinite <a href="/facts/Sequence/gV2S4uqp">sequence</a> of <a href="/facts/Edge_(graph_theory)/W0MqKkyE">edges</a> which joins a sequence of <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">vertices</a>.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a></li></ul> Let <i>G</i> = (<i>V</i>, <i>E</i>, <i>Φ</i>) be a graph. A finite walk is a sequence of edges (<i>e</i>1, <i>e</i>2, ..., <i>e</i><i>n</i> − 1) for which there is a sequence of vertices (<i>v</i>1, <i>v</i>2, ..., <i>v</i><i>n</i>) such that <i>Φ</i>(<i>e</i><i>i</i>) = {<i>v</i><i>i</i>, <i>v</i><i>i</i> + 1} for <i>i</i> = 1, 2, ..., <i>n</i> − 1. (<i>v</i>1, <i>v</i>2, ..., <i>v</i><i>n</i>) is the <i>vertex sequence</i> of the walk. The walk is <i>closed</i> if <i>v</i>1 = <i>v</i><i>n</i>, and it is <i>open</i> otherwise. An infinite walk is a sequence of edges of the same type described here, but with no first or last vertex, and a semi-infinite walk (or <a href="/facts/End_(graph_theory)/l5B9xEQz">ray</a>) has a first vertex but no last vertex. <ul><li>A trail is a walk in which all edges are distinct.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a></li> <li>A path is a trail in which all vertices (and therefore also all edges) are distinct.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a></li></ul> <p>If <i>w</i> = (<i>e</i>1, <i>e</i>2, ..., <i>e</i><i>n</i> − 1) is a finite walk with vertex sequence (<i>v</i>1, <i>v</i>2, ..., <i>v</i><i>n</i>) then <i>w</i> is said to be a <i>walk from</i> <i>v</i>1 <i>to</i> <i>v</i><i>n</i>. Similarly for a trail or a path. If there is a finite walk between two <i>distinct</i> vertices then there is also a finite trail and a finite path between them. </p><p>Some authors do not require that all vertices of a path be distinct and instead use the term simple path to refer to such a path where all vertices are distinct. </p><p>A <a href="/facts/Weighted_graph/W0MqKkyE">weighted graph</a> associates a value (<i>weight</i>) with every edge in the graph. The <i>weight of a walk</i> (or trail or path) in a weighted graph is the sum of the weights of the traversed edges. Sometimes the words <i>cost</i> or <i>length</i> are used instead of weight. </p> <h3>Directed walk, directed trail, and directed path</h3> <ul><li>A directed walk is a finite or infinite <a href="/facts/Sequence/gV2S4uqp">sequence</a> of <a href="/facts/Edge_(graph_theory)/W0MqKkyE">edges</a> directed in the same direction which joins a sequence of <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">vertices</a>.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a></li></ul> Let <i>G</i> = (<i>V</i>, <i>E</i>, <i>Φ</i>) be a directed graph. A finite directed walk is a sequence of edges (<i>e</i>1, <i>e</i>2, ..., <i>e</i><i>n</i> − 1) for which there is a sequence of vertices (<i>v</i>1, <i>v</i>2, ..., <i>v</i><i>n</i>) such that <i>Φ</i>(<i>e</i><i>i</i>) = (<i>v</i><i>i</i>, <i>v</i><i>i</i> + 1) for <i>i</i> = 1, 2, ..., <i>n</i> − 1. (<i>v</i>1, <i>v</i>2, ..., <i>v</i><i>n</i>) is the <i>vertex sequence</i> of the directed walk. The directed walk is <i>closed</i> if <i>v</i>1 = <i>v</i><i>n</i>, and it is <i>open</i> otherwise. An infinite directed walk is a sequence of edges of the same type described here, but with no first or last vertex, and a semi-infinite directed walk (or <a href="/facts/End_(graph_theory)/l5B9xEQz">ray</a>) has a first vertex but no last vertex. <ul><li>A directed trail is a directed walk in which all edges are distinct.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a></li> <li>A directed path is a directed trail in which all vertices are distinct.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a></li></ul> <p>If <i>w</i> = (<i>e</i>1, <i>e</i>2, ..., <i>e</i><i>n</i> − 1) is a finite directed walk with vertex sequence (<i>v</i>1, <i>v</i>2, ..., <i>v</i><i>n</i>) then <i>w</i> is said to be a <i>walk from</i> <i>v</i>1 <i>to</i> <i>v</i><i>n</i>. Similarly for a directed trail or a path. If there is a finite directed walk between two <i>distinct</i> vertices then there is also a finite directed trail and a finite directed path between them. </p><p>A "simple directed path" is a path where all vertices are distinct. </p><p>A <a href="/facts/Weighted_graph/W0MqKkyE">weighted directed graph</a> associates a value (<i>weight</i>) with every edge in the directed graph. The <i>weight of a directed walk</i> (or trail or path) in a weighted directed graph is the sum of the weights of the traversed edges. Sometimes the words <i>cost</i> or <i>length</i> are used instead of weight. </p> <h2 id="examples">Examples</h2> <ul><li>A graph is <a href="/facts/Connectivity_(graph_theory)/FSNjsYhz">connected</a> if there are paths containing each pair of vertices.</li> <li>A directed graph is <a href="/facts/Strongly-connected_digraph/YBdfQ0um">strongly connected</a> if there are oppositely oriented directed paths containing each pair of vertices.</li> <li>A path such that no graph edges connect two nonconsecutive path vertices is called an <a href="/facts/Induced_path/zfcIx9Sw">induced path</a>.</li> <li>A path that includes every vertex of the graph without repeats is known as a <a href="/facts/Hamiltonian_path/MHjY2xoY">Hamiltonian path</a>.</li> <li>Two paths are <i>vertex-independent</i> (alternatively, <i>internally disjoint</i> or <i>internally vertex-disjoint</i>) if they do not have any internal vertex or edge in common. Similarly, two paths are <i>edge-independent</i> (or <i>edge-disjoint</i>) if they do not have any edge in common. Two internally disjoint paths are edge-disjoint, but the converse is not necessarily true.</li> <li>The <a href="/facts/Distance_(graph_theory)/EmQFKvqa">distance</a> between two vertices in a graph is the length of a shortest path between them, if one exists, and otherwise the distance is infinity.</li> <li>The diameter of a connected graph is the largest distance (defined above) between pairs of vertices of the graph.</li></ul> <h2 id="finding-paths">Finding paths</h2> <p>Several algorithms exist to find <a href="/facts/Shortest_path_problem/g4nsrswr">shortest</a> and <a href="/facts/Longest_path_problem/W17hlDKs">longest</a> paths in graphs, with the important distinction that the former problem is computationally much easier than the latter. </p><p><a href="/facts/Dijkstra%27s_algorithm/ehun88jl">Dijkstra's algorithm</a> produces a list of shortest paths from a source vertex to every other vertex in directed and undirected graphs with non-negative edge weights (or no edge weights), whilst the <a href="/facts/Bellman%E2%80%93Ford_algorithm/Sx6INcdr">Bellman–Ford algorithm</a> can be applied to directed graphs with negative edge weights. The <a href="/facts/Floyd%E2%80%93Warshall_algorithm/fo2XUseS">Floyd–Warshall algorithm</a> can be used to find the shortest paths between all pairs of vertices in weighted directed graphs. </p> <h2 id="the-path-partition-problem">The path partition problem</h2> <p>The k-path partition problem is the problem of partitioning a given graph to a smallest collection of vertex-disjoint paths of length at most <i>k</i>.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Glossary_of_graph_theory/W0MqKkyE">Glossary of graph theory</a></li> <li><a href="/facts/Path_graph/4Y2f35eM">Path graph</a></li> <li><a href="/facts/Polygonal_chain/GRQ6BMQS">Polygonal chain</a></li> <li><a href="/facts/Shortest_path_problem/g4nsrswr">Shortest path problem</a></li> <li><a href="/facts/Longest_path_problem/W17hlDKs">Longest path problem</a></li> <li><a href="/facts/Dijkstra%27s_algorithm/ehun88jl">Dijkstra's algorithm</a></li> <li><a href="/facts/Bellman%E2%80%93Ford_algorithm/Sx6INcdr">Bellman–Ford algorithm</a></li> <li><a href="/facts/Floyd%E2%80%93Warshall_algorithm/fo2XUseS">Floyd–Warshall algorithm</a></li> <li><a href="/facts/Self-avoiding_walk/23chozBY">Self-avoiding walk</a></li> <li><a href="/facts/Shortest-path_graph/7lSJPrKo">Shortest-path graph</a></li></ul> <h2 id="notes">Notes</h2> <ul><li>Bender, Edward A.; Williamson, S. Gill (2010). <a href="https://books.google.com/books?id=vaXv_yhefG8C"><i>Lists, Decisions and Graphs. With an Introduction to Probability</i></a>.</li> <li>Bondy, J. A.; Murty, U. S. R. (1976). <a href="https://archive.org/details/graphtheorywitha0000bond/page/12"><i>Graph Theory with Applications</i></a>. North Holland. p. <a href="https://archive.org/details/graphtheorywitha0000bond/page/12">12-21</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-444-19451-7.</li> <li><a href="/facts/Reinhard_Diestel/Fzv2bX8x">Diestel, Reinhard</a> (2005). <a href="http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/"><i>Graph Theory</i></a>. Springer-Verlag. pp. 6–9. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 3-540-26182-6.</li> <li>Gibbons, A. (1985). <i>Algorithmic Graph Theory</i>. Cambridge University Press. pp. 5–6. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-521-28881-9.</li> <li><a href="/facts/Bernhard_Korte/xp59tdBv">Korte, Bernhard</a>; <a href="/facts/L%C3%A1szl%C3%B3_Lov%C3%A1sz/X0VB38Ee">Lovász, László</a>; Prömel, Hans Jürgen; <a href="/facts/Alexander_Schrijver/eJHJNRGz">Schrijver, Alexander</a> (1990). <a href="https://archive.org/details/pathsflowsvlsila0000unse"><i>Paths, Flows, and VLSI-Layout</i></a>. Springer-Verlag. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-387-52685-4.</li> <li>McCuaig, William (1992). <a href="https://archive.org/details/graphstructureth0000amsi/page/205/">"Intercyclic Digraphs"</a>. In Robertson, Neil; Seymour, Paul (eds.). <i>Graph Structure Theory</i>. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors, Seattle, June 22 – July 5, 1991. American Mathematical Society. p. 205.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>McCuaig 1992, p. 205. - McCuaig, William (1992). "Intercyclic Digraphs". In Robertson, Neil; Seymour, Paul (eds.). Graph Structure Theory. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors, Seattle, June 22 – July 5, 1991. American Mathematical Society. p. 205. <a href="https://archive.org/details/graphstructureth0000amsi/page/205/" target="_blank">https://archive.org/details/graphstructureth0000amsi/page/205/</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Bender & Williamson 2010, p. 162. - Bender, Edward A.; Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability. <a href="https://books.google.com/books?id=vaXv_yhefG8C" target="_blank">https://books.google.com/books?id=vaXv_yhefG8C</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Bender & Williamson 2010, p. 162. - Bender, Edward A.; Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability. <a href="https://books.google.com/books?id=vaXv_yhefG8C" target="_blank">https://books.google.com/books?id=vaXv_yhefG8C</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Bender & Williamson 2010, p. 162. - Bender, Edward A.; Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability. <a href="https://books.google.com/books?id=vaXv_yhefG8C" target="_blank">https://books.google.com/books?id=vaXv_yhefG8C</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Bender & Williamson 2010, p. 162. - Bender, Edward A.; Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability. <a href="https://books.google.com/books?id=vaXv_yhefG8C" target="_blank">https://books.google.com/books?id=vaXv_yhefG8C</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Bender & Williamson 2010, p. 162. - Bender, Edward A.; Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability. <a href="https://books.google.com/books?id=vaXv_yhefG8C" target="_blank">https://books.google.com/books?id=vaXv_yhefG8C</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Bender & Williamson 2010, p. 162. - Bender, Edward A.; Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability. <a href="https://books.google.com/books?id=vaXv_yhefG8C" target="_blank">https://books.google.com/books?id=vaXv_yhefG8C</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Chen, Yong; Goebel, Randy; Lin, Guohui; Su, Bing; Xu, Yao; Zhang, An (2019-07-01). "An improved approximation algorithm for the minimum 3-path partition problem". Journal of Combinatorial Optimization. 38 (1): 150–164. doi:10.1007/s10878-018-00372-z. ISSN 1382-6905. <a href="https://doi.org/10.1007/s10878-018-00372-z" target="_blank">https://doi.org/10.1007/s10878-018-00372-z</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> </ol>