Graphs Paths
The notion of a path in a graph is intuitively clear but a little hard to pin down formally.
Suppose G(V,E) is a graph with vertices v0,v1,…,vk (not necessarily distinct) and edges e1,e2,…,ek (not necessarily distinct) in which edge ei={vi-1,vi} for i=1,…,k. Then the alternating sequence of vertices and edges v0e1v1e2v2…ekvk is a path from v0 to vk of length k (note that the length is the number of edges, not vertices). Unless we work with multigraphs the listing of the edges is redundant, so we may speak more simply of the path as v0v1v2…vk. This definition allows for incredibly knotty, repetitious paths. If we want to rule out that possibility, we can speak of simple paths, which are paths in which no vertices (and thus no edges) are repeated.
The notion of a path in a graph is intuitively clear but a little hard to pin down formally.
Suppose G(V,E) is a graph with vertices v0,v1,…,vk (not necessarily distinct) and edges e1,e2,…,ek (not necessarily distinct) in which edge ei={vi-1,vi} for i=1,…,k. Then the alternating sequence of vertices and edges v0e1v1e2v2…ekvk is a path from v0 to vk of length k (note that the length is the number of edges, not vertices). Unless we work with multigraphs the listing of the edges is redundant, so we may speak more simply of the path as v0v1v2…vk. This definition allows for incredibly knotty, repetitious paths. If we want to rule out that possibility, we can speak of simple paths, which are paths in which no vertices (and thus no edges) are repeated.
No comments:
Post a Comment