【图论笔记】图论基础（6）：有向图

---

目录

• 1. 有向图的定义
• 2. 无向图的定向
• 3. 竞赛图
• 返回【图论笔记】

---

1. 有向图的定义

在前面所探讨的图中，边是没有方向的，也就是说，从$u$到$v$的边和从$v$到$u$的边是不加以区分的．这正像日常生活中，从甲地到乙地的路也可以让你从乙地回到甲地．但是现实生活中还有一种单行线，顺着单行线可以从甲到乙，但是反向走是不可以的．为了刻画这种问题，我们就需要引入有向图的概念．

有向图 $D$是由三个要素构成的，即顶点集$V(D)$（简记作$V$），有向边集$A(D)$（简记作$A$），以及由$A$到$V^{(2)}$的关联映射$\psi$，其中$V^{(2)}$是$V$上的可重复的二元有序组的全体．在上下文意义明确的前提下，通常将$\psi$隐藏，从而将有向图$D$记作$D(V,A)$．与有向图相对地，之前定义的图也叫无向图．

设$D(V,A)$是一个有向图．

• 设$a\in A$．如果$\psi(a)=(u,v)$，其中$u,v\in V$，那么称顶点$u$是有向边$a$的尾，$v$是有向边$a$的头，$u,v$合称$a$的端点；也说$a$是 从$u$到$v$ 的有向边，说$u$是 指向$v$的顶点．当我们省略$\psi$时，$\psi(a)=(u,v)$会记作$a=(u,v)$．

• 设$v\in V$．在$D$中，所有指向$v$的顶点都叫$v$的入邻点，$v$所指向的所有顶点都叫$v$的出邻点；$v$的所有入邻点的全体（不包括$v$）所构成的集合，叫做$v$的入邻域，记作$N^-_D(v)$或$N^-(v)$；$v$的所有出邻点的全体（不包括$v$）所构成的集合，叫做$v$的出邻域，记作$N^+_D(v)$或$N^+(v)$．

• 设$v\in V$．在$D$中，所有以$v$为头的有向边都叫$v$的入边，以$v$为尾的有向边都叫$v$的出边；$v$的所有入边的个数，叫做$v$的入度，记作$d^-_D(v)$或$d^-(v)$；$v$的所有出边的个数，叫做$v$的出度，记作$d^+_D(v)$或$d^+(v)$．

• $D$的最小入度和最大入度分别记作$\delta^-(D)$和$\Delta6-(D)$；$D$的最小出度和最大出度分别记作$\delta^+(D)$和$\Delta^+(D)$；$D$的平均入度和平均出度分别记作$d^-(D)$和$d^+(D)$．

• $D$的顶点数和有向边数分别记作$v(D)$和$a(D)$．

性质1.（有向图的握手定理） 设$D(V,A)$是有向图．那么$2a(D)=\sum_{v\in V(D)}d^+(v)=\sum_{v\in V(D)}d^-(v).$

我们实际画有向图的时候，通常将有向边$a=(u,v)$画成从$u$指向$v$的带箭头的曲线段．

• 如果$D$上每个顶点的出度和入度都是$k$，则称$D$是 $k$-正则有向图．

• $D$上入度为$0$的顶点叫源，出度为零的顶点叫汇．

源和汇在最大流最小割问题中有特殊的地位．

---

2. 无向图的定向

• 在有向图$D$上，将所有的有向边都换成对应的无向边，就得到了一个无向图，这个无向图叫做有向图$D$的基础无向图，记作$G(D)$．

• 设$G$是一个无向图，$e=uv\in E(G)$．将无向边$uv$替换成有向边$(u,v)$或$(v,u)$，这叫做无向边$e=uv$的定向．如果将$G$的所有边都定向，就得到了一个有向图，记作$\overrightarrow{G}$，$\overrightarrow{G}$叫做$G$的一个定向．

• 设$P=v_1v_2\dots v_r$是一个路．给$P$一个定向使得对于每个$i$，$v_i$指向$v_{i+1}$，那么我们就说$P$的这个定向是个有向路．

• 设$C=v_1v_2\dots v_rv_1$是一个圈．给$C$一个定向使得对于每个$i$，$v_i$指向$v_{i+1}$，其中$v_{r+1}=v_1$，那么我们就说$C$的这个定向是个有向圈．

---

3. 竞赛图

$n$阶完全图的定向叫做$n$阶竞赛图．之所以称之为竞赛图，是因为它体现了$n$个参赛队循环赛的比赛情况．我们用每个顶点表示一个参赛队，如果参赛队$v_i$战胜了参赛队$v_j$，那么就将$v_iv_j$定向为$(v_i,v_j)$．

---

• 返回【图论笔记】