A path in a graph is a finite sequence of alternating vertices and edges, beginning and ending with a vertex, such that every consecutive pair of vertices and are adjacent and is incident with and with . Typically, the edges may be omitted when writing a path (e.g., ) since only one edge of a graph may connect two adjacent vertices. In a multigraph, however, the choice of edge may be significant.
The length of a path is the number of edges in it.
Consider the following graph:
Paths include (but are certainly not limited to) (length 3), (length 4), and (length 12). is not a path since is not adjacent to .
Consider this digraph:
, , and are all valid paths. is not a valid path because and are not connected. is not a valid path because the edge connecting to has the opposite orientation.
|Date of creation||2013-03-22 12:16:49|
|Last modified on||2013-03-22 12:16:49|
|Last modified by||CWoo (3771)|