此笔记基于图与网络流理论 （第二版）田丰、张运清著

以及Network flows theory algorithms and applications

第一章 图的基本概念

1 图与子图

• 无向图

通常所说的图是无向图，用G = (V,E)来表示，V指的是点集，E指的是边集

• 邻域、闭邻域

邻域：点v属于点集V，则v的邻域是所有能和v组成边且在E中的点集

$N_{G}(v)={u | u v \in E}$

闭邻域：邻域再把自己也算上就是闭邻域

2 链、圈、连通分图

• 链

点边交错构成链，链中所有点不重复称为初等链，所有边不重复称为简单链，也称为迹

两点之间最小链长（所含的边）称为距离

• 圈

首尾相接的链称为圈

• 连通图

任意两点之间都有边连接

• 子图

由G中部分点和边构成的的图称为生成子图

由一个图的全部顶点及连结这些顶点的部分边构成的连通图称为原图的支撑子图。

第八章 有向图

$D=(V, A)$

V代表点集，A代表弧集

• 度

给定有向图D=(V,A).以点v_i为始点的弧的个数称为点v_i的出度(out- degree) ,记为$d_{D}^{+}\left(v_{i}\right)$

以v_i为终点的弧的个数称为点v_i的入度(in-degree),记为$d_{D}^{-}\left(v_{i}\right)$;

在不会引起混淆时,通常将两者的和称为度

• 邻域

  定义出邻域与入邻域

  $O N_{D}\left(v_{i}\right)=\left{v_{j} \in V | v_{i} v_{j} \in A(D)\right}, \quad I N_{D}\left(v_{i}\right)=\left{v_{j} \in V | v_{j} v_{i} \in A(D)\right}$

• 路

有向的链若不改变方向就称为路，闭合成圈称为回路

若路P过有向图的每一点一 次且仅仅一次，则称之为哈密顿路(Hamiltonian path);类似定义哈密顿回路(Hamiltonian circuit); 若简单路包含有向图的每一弧,则称之为欧拉路(Eulerian path);类似定义欧拉回路(Eulerian circuit);

如果对任意两个点vi,vj, 有向图D中存在(vi,vj)-路, 也存在(vj,vi)-路,则称D是强有向图(strong digraph).

• 有向图的等价性

若vi,vj可互相到达，则称两者等价，由此可将图进行分类，称每个生成子图为强分图