有向图

箭头把无向的“彼此相邻”拆成“从这里可以直接走到那里”。一条弧提供一步许可，连续弧把许可复合成可达性；反向许可若没有明写，就不能从图形的连线形状中推断出来。方向因此会改变路径、连通、圈和割的含义。

入度与出度只描述一步的局部收支。一个顶点可以入度、出度都很大，却仍处在无法返回的单向区域；反过来，强连通图也无需每对顶点都有直接弧，只要沿箭头能够往返即可。判断整体行为必须追踪弧的排列，而不能只比较两组度数。

把所有箭头反转得到反向图 $D^{\mathrm{rev}}$。从 $u$ 到 $v$ 的路与 $D^{\mathrm{rev}}$ 中从 $v$ 到 $u$ 的路一一对应，这个简单对称性常把“能到达目标”的问题转成“哪些起点能到达当前点”。

构建步骤的先后图可令弧 $P\to Q$ 表示“步骤 $P$ 必须先于步骤 $Q$ 完成”。若存在有向圈，先后要求会沿箭头回到自身，拓扑构建顺序便不存在；忽略方向后看到的连通骨架无法暴露这种障碍。

设弧为 $a\to b,b\to c,c\to a$，三个顶点构成有向圈，每点入度、出度均为一。删去 $c\to a$ 后，无向骨架仍是一条连通路径，但 $c$ 到不了 $a$。再加入 $b\to a$ 只能让 $a,b$ 互达，仍不会自动把 $c$ 纳入同一个强连通分量。

无向图转成有向对象有两种常见操作。定向为每条无向边只选一个方向；对称有向化则把每条 $uv$ 换成 $u\to v$ 与 $v\to u$ 两条弧。前者可能破坏原可达性，后者精确保留无向路径，但弧数翻倍。它们都不同于原来的有限简单无向图公理库有限简单无向图Graph · Finite simple undirected graph · 图由有限顶点集与无序二元顶点子集组成的边集所确定的简单无向图。，使用结论时要核对模型。

若允许停留步 $(v,v)$，需要保留自环；若同一方向的多条航班或交易必须分别计数，需要多重有向图。oriented graph 还常额外禁止反向弧对，因此不会出现长度二的有向圈。不同教材对 “simple digraph” 的约定并不完全统一，遇到二圈时应先检查定义。

弧关系的传递闭包正是可达关系。把强连通分量各自收缩成一点后，所得凝聚图必为有向无环图公理库有向无环图Directed acyclic graph · DAG不含有向环的有向图。；若凝聚图仍有有向圈，圈上的分量原本就应彼此互达，和“分量已极大”矛盾。

有向无环图允许拓扑排序公理库拓扑排序Topological sort给有向无环图顶点排列线性次序，使每条边从前指向后。，强连通分量把循环依赖压成可管理的块，网络流公理库最大流Maximum flow在容量与流守恒约束下最大化源到汇净流量的问题。又在弧上加入容量并区分割的方向。三类问题都继承本页的箭头语义，却分别增加无圈性、等价类或数值约束。

程序状态、网页跳转和协议步骤都可用有向图作骨架。若弧还带动作标签，就进入标号转移系统公理库标号转移系统Labeled transition system · Labelled transition system · LTS在状态转移上标记动作，明确路径、可达性、使能动作以及终止与死锁的行为模型。；若边持续插删，还要另行规定动态图的更新协议。共享有向图表示并不会让运行轨迹、标签语义和算法成本自动相同。

无向路与圈公理库路与圈Path and cycle in a graph用相邻顶点序列刻画图中的行走、简单路径与首尾闭合的简单圈。中的删绕路论证仍可用于有向游走：删除一段从某顶点回到自身的闭合子游走，不会破坏剩余弧的方向。因此只要 $v$ 从 $u$ 可达，就存在一条从 $u$ 到 $v$ 的有向简单路。