Directed Paths and Cycles

Graph Theory · Axiom Academy

LESSON Directed Paths and Cycles Understanding paths, cycles, and reachability in directed graphs (digraphs) 1. Directed Walks, Trails, and Paths Directed Walk: A sequence of vertices where each consecutive pair is connected by a directed edge in the correct direction . Vertices and edges may repeat. Directed Trail: A directed walk where no edge is repeated (but vertices may repeat). Directed Path: A directed walk where no vertex is repeated (which also means no edge is repeated). A directed cycle where no vertex appears more than once, except for the start/end vertex. A directed cycle of length 1: an edge from a vertex to itself. Every vertex can reach itself (trivially, via a path of length 0). If u can reach v and v can reach w , then u can reach w . 4. The Reachability Relation (Transitive Closure) 5. Undirected vs. Directed: Key Differences Path from u to v implies path from v to u Edge \ u,v\ can be traversed both ways Connectivity is an equivalence relation Path from u to v does NOT imply path from v to u Edge (u,v) can only be traversed from u to v Strong connectivity is needed for equivalence Web pages linking to each other (you can link to a page without it linking back) Social media following (you can follow someone who doesn't follow you) Task dependencies (task A must complete before B, but B doesn't affect A) One-way streets in a road network

This is the written version of the interactive lesson above. See the full Graph Theory course.