[prev] 56 [next]

Directed Graphs (Digraphs) (cont)

Terminology for digraphs …

Directed path:   sequence of n ≥ 2 vertices v1 → v2 → … → vn

  • where (vi,vi+1) ∈ edges(G) for all vi,vi+1 in sequence
  • if v1 = vn, we have a directed cycle
Degree of vertex:   deg(v) = number of edges of the form (v, _) ∈ edges(G)
  • Indegree of vertex: deg-1(v) = number of edges of the form (_, v) ∈ edges(G)
Reachability:   w is reachable from v if ∃ directed path v,…,w

Strong connectivity:   every vertex is reachable from every other vertex

Directed acyclic graph (DAG):   graph containing no directed cycles