有向图

在图论中, 有向图是指每条边均标有方向的图.

在非交换代数和表示论中, 有向图也称为箭图.

1定义

定义 1.1 (有向图). 有向图是指四元组 $G=(V,E,s,t)$, 其中

•	$V$ 是集合, 其元素称为 $G$ 的顶点.

•	$E$ 是集合, 其元素称为 $G$ 的边.

•	$s,t:E\to V$ 是映射, 分别将每条边映到其起点和终点.

我们还引入以下术语.

定义 1.2. 设 $G=(V,E,s,t)$ 是有向图.

•	若 $e\in E$ 将顶点连到自身, 即 $s(e)=t(e)$, 就说 $e$ 是圈.

•	若 $e_1,e_2\in E$ 连接同样的两个顶点且方向相同, 即 $s(e_1)=s(e_2)$, $t(e_1)=t(e_2)$, 且 $e_1\ne e_2$, 就说 $e_1,e_2$ 是重边.

•	若 $G$ 没有圈, 则称 $G$ 为无圈有向图.

•	若 $G$ 既没有圈也没有重边, 则称 $G$ 为简单有向图.

2性质

基本性质

•	所有有向图及其间的图同态构成一个范畴, 称为有向图范畴.

底图

设 $G=(V,E,s,t)$ 是有向图. 我们可以忽略 $G$ 中边的方向, 而将其视为图, 称为 $G$ 的底图. 具体地说, 我们考虑的是图 $(V,E,d)$, 其中映射 $d:E\to ⟨\genfrac{}{}{0ex}{}{V}{2}⟩$ 定义为$$d(e)=(s(e),t(e)).$$这也给出了有向图范畴到图范畴的遗忘函子.

与范畴的联系

每个小范畴都能视为有向图, 其顶点对应范畴的对象, 而边对应范畴的态射. 这给出了范畴的 $1$-范畴到有向图范畴的遗忘函子. 该函子具有左伴随, 从而我们得到一对自由–遗忘伴随. 这样, 对任何有向图 $G$, 我们可以谈论 $G$ 生成的自由范畴. 大致来说, 该范畴的对象即为 $G$ 的顶点, 而态射为 $G$ 中的有向路径.

3相关概念

•

箭图

术语翻译

有向图 • 英文 directed graph • 德文 gerichteter Graph (m) • 法文 graphe orienté (m) • 日文 有向グラフ (ゆうこうグラフ) • 韩文 유향 그래프

起点 • 英文 source

终点 • 英文 target