形式陈述

有向图可定义为 $D=(V,A)$$D=(V,A)$，其中 $V$$V$ 是顶点集，$A\subseteq V\times V$$A\subseteq V\times V$ 是有序对组成的弧集。弧 $(u,v)$$(u,v)$ 从尾 $u$$u$ 指向头 $v$$v$。顶点 $v$$v$ 的出度和入度分别为

$$ d^+(v)=|\{(v,w)\in A\}|, \qquad d^-(v)=|\{(u,v)\in A\}|. $$$$d^{+}(v)=|\{(v,w)\in A\}|,d^{-}(v)=|\{(u,v)\in A\}|.$$

有限有向图满足

$$ \sum_v d^+(v)=|A|=\sum_v d^-(v). $$$$\sum _v{d}^{+}(v)=|A|=\sum _v{d}^{-}(v).$$

有向路要求弧方向连续一致；若 $u$$u$ 可达 $v$$v$ 且 $v$$v$ 可达 $u$$u$，二者处于同一强连通分量。把方向忽略后得到底层无向图，其连通性称弱连通。

直觉

有向边表达非对称关系：从 $u$$u$ 到 $v$$v$ 的可能性不自动允许反向。入度与出度分别计数流入和流出。

例子与边界

网页链接、状态转移和先修关系天然有方向。若 $A$$A$ 是集合，则同一有序对不能重复；多重有向图需把弧作为带端点映射的独立对象。是否允许环 $(v,v)$$(v,v)$ 取决于约定；关系模型自然允许环。无向边不能简单视作一个有序对，通常对应两条反向弧。强连通严格强于弱连通。DAG 是无有向环的有向图，它仍可能在底层无向图中含环。入度—出度恒等式对环的计数约定需一致：一个环对入度和出度各贡献一。

推论与应用

有向图建模依赖、流、自动机、因果网络和互联网，并支撑拓扑排序与强连通分解。

参考资料

• Eric Lehman, F. Thomson Leighton, and Albert R. Meyer, Mathematics for Computer Science, rev. 2018，§§10.1–10.5, digraphs, reachability, and DAGs。
• Douglas B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001，§1.4, directed graphs。