Directed Graphs Summary

Graph Theory · Axiom Academy

Let's review the key concepts of directed graphs and their unique properties. Directed Edges (Arcs): Edges with direction, represented as ordered pairs (u, v) from u to v Asymmetry: An arc from u to v does not imply an arc from v to u Directed Paths: Sequences of vertices where each arc follows the specified direction Directed Cycles: Closed directed paths where you can return to the starting vertex In-degree (deg - (v)): The number of arcs coming into vertex v Out-degree (deg + (v)): The number of arcs going out from vertex v Degree Sum Formula: The sum of all in-degrees equals the sum of all out-degrees, both equal to the number of arcs Source: A vertex with in-degree 0 (no incoming arcs) Sink: A vertex with out-degree 0 (no outgoing arcs) Definition: A directed graph is strongly connected if there is a directed path from every vertex to every other vertex Bidirectional Reachability: For all vertices u and v, there exists a path u → v and a path v → u Testing: Can be verified by checking reachability from a single vertex in both directions Applications: Web page ranking, circuit analysis, dependency resolution Definition: A directed graph is weakly connected if the underlying undirected graph is connected Ignoring Direction: Connectivity exists when arc directions are ignored Relationship: Strong connectivity implies weak connectivity, but not vice versa Components: Weakly connected components partition the vertex set Strongly Connected Components (SCCs)

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