Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

  • Create BookmarkCreate Bookmark
  • Create Note or TagCreate Note or Tag
  • PrintPrint

9.2 PATHS

Example 9.17.

Consider the graph shown in Figure 9.19.

Let us imagine that the vertices are towns and the edges are roads connecting them. It is clear that we can travel from a to B by road but there is no such roadway between D and H. To reach B from a, we take the following route:

  1. A to E via e3.

  2. E to D via e4.

  3. D to C via e5.

  4. C to B via e6.

Figure 9.19.


Naturally, we may represent the above route as . Further, is also a route between A and B. is also a route, perhaps roundabout, between A and B. Let us also note that is not a meaningful route at all, for E is not an end of e6. We formalize the idea of a route, called a walk, in the following definition.

Definition 9.11: Let G be a graph and u, v be two vertices. A u - v walk in G is defined as a finite sequence


  

You are currently reading a PREVIEW of this book.

                                                                                                                    

Get instant access to over $1 million worth of books and videos.

  

Start a Free 10-Day Trial


  
  • Safari Books Online
  • Create BookmarkCreate Bookmark
  • Create Note or TagCreate Note or Tag
  • PrintPrint