Digraph Basics

Graph Theory · Axiom Academy

Understanding directed graphs and their fundamental properties A directed graph (or digraph) D consists of a set of vertices V and a set of arcs A, where each arc is an ordered pair of vertices. A ⊆ V × V is a set of arcs (ordered pairs) An arc (u, v) goes from u to v The key difference from undirected graphs: arcs are ordered pairs, not unordered sets. Directed and undirected graphs use different terminology to emphasize the presence or absence of direction. Undirected graphs have edges u, v (unordered) Directed graphs have arcs (u, v) (ordered) Arc (u, v): u is the tail , v is the head Digraphs are drawn with arrows (arrowheads) to indicate direction. The arrow points from the tail to the head of the arc. Vertices: drawn as circles or dots Arcs: drawn as arrows pointing from tail to head Arc (u, v): arrow points from u to v Arrowhead position indicates direction of the arc The animation below shows how direction is represented visually. 4. Underlying Undirected Graph Every digraph D has an associated underlying undirected graph U(D), obtained by "forgetting" the directions of all arcs. The underlying graph preserves connectivity information but loses directional information. 5. Symmetric and Antisymmetric Digraphs Digraphs can be classified based on how their arcs relate to each other in terms of direction. Symmetric: Mutual friendships (if A follows B, then B follows A) Antisymmetric: Hierarchies, partial orders (if A manages B, then B doesn't manage A)

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