What is a digraph (directed graph) D mathematically?
D = (V, E) where V is a finite non-empty set of vertices, and E is a set of ordered pairs of distinct vertices called arcs/directed edges. Arc (u,v) or ⃗uv goes FROM u TO v.
What is the order p(D) and size q(D) of a digraph?
Order: |V(D)| (number of vertices). Size: |E(D)| (number of arcs).
Define out-neighbourhood N⁺(v) and in-neighbourhood N⁻(v).
N⁺(v) = {u ∈ V(D) | ⃗vu ∈ E(D)} (vertices you can go TO from v). N⁻(v) = {u ∈ V(D) | ⃗uv ∈ E(D)} (vertices that can come FROM to v).
Digraphs D₁ and D₂ are isomorphic (D₁ ≅ D₂) if there exists…
…a one-to-one, onto function φ: V(D₁) → V(D₂) such that (u,v) ∈ E(D₁) iff (φ(u), φ(v)) ∈ E(D₂).
State the First Theorem for Digraphs.
For any digraph D with order p and size q: ∑ od(v) = ∑ id(v) = q. Every arc contributes 1 to an outdegree and 1 to an indegree.
What is outdegree od(v), indegree id(v), and degree deg(v)?
od(v) = |N⁺(v)|. id(v) = |N⁻(v)|. deg(v) = od(v) + id(v).
What is the underlying graph of a digraph D?
The undirected graph obtained by replacing all arcs uv or vu with the undirected edge uv.
True or False: In a digraph, it’s possible for ∑ deg(v) to be odd.
True. While ∑ od(v) = ∑ id(v) = q, ∑ deg(v) = ∑(od(v)+id(v)) = 2q, which is always even.
If uv is an arc in D, vertex u is ______ to v, and v is ______ from u.
u is adjacent to v; v is adjacent from u.
Arc uv is said to be ______ from u and ______ to v.
Incident from u; incident to v.
What must an isomorphism preserve in digraphs that’s different from undirected graphs?
Direction! Arc (u,v) must map to arc (φ(u), φ(v)) - same direction preserved.
What is an induced subdigraph ⟨S⟩ for S ⊆ V(D)?
The subdigraph with vertex set S and ALL arcs from D that have BOTH endpoints in S.
What is a spanning subdigraph?
A subdigraph H of D with V(H) = V(D) (uses all vertices, only some arcs).
Define a directed walk.
A finite alternating sequence v₁, ⃗e₁, v₂, ⃗e₂, …, vₙ₋₁, ⃗eₙ₋₁, vₙ where each ⃗eᵢ = (vᵢ, vᵢ₊₁) ∈ E(D). Must follow arc directions.
What is a directed path?
A directed walk with no repeated vertices (and thus no repeated arcs).
What is a directed cycle?
A directed walk that starts and ends at the same vertex, with no other vertex repeated. Length ≥ 2 in digraphs!
Key difference from undirected graphs: In digraphs, cycles of length __ are possible.
2! (v→u→v) because arcs have direction.
What is a semiwalk?
A sequence where for each step, you can travel EITHER with the arc direction (forward) OR against it (backward)
If in a semiwalk, ⃗eᵢ = (vᵢ, vᵢ₊₁), it’s a ______ arc. If eᵢ = (vᵢ₊₁, vᵢ), it’s a ______ arc.
Forward arc; backward arc.
Every directed walk is a semiwalk, but not every semiwalk is a directed walk. Why?
In a directed walk you can ONLY use forward arcs (follow direction). In a semiwalk you can use backward arcs too.
Define directed distance d_D(u,v).
The length (number of arcs) of the SHORTEST directed path FROM u TO v. If no such path exists, d_D(u,v) = ∞.
In digraphs, d(u,v) and d(v,u) are ______.
Not necessarily equal! Direction matters.
A digraph is weakly connected if…
…its underlying undirected graph is connected (can reach any vertex via semiwalks).
A digraph is strongly connected if…
…for EVERY pair u,v, there exists a directed path FROM u TO v AND FROM v TO u.
