图论与网络流的主要定理

以下是图论与网络流中的一些主要定理：

1. 图论中的定理：

- 定理1：欧拉定理
对于连通的平面图，有 V - E + F = 2，其中 V、E、F 分别表示图中的顶点数、边数和面数。

- 定理2：哈密顿定理
对于简单无向图 G，如果 G 中任意两个不同的顶点 u、v 之间的距离（即 u 到 v 的最短距离）都不超过 ⌊|V(G)|/2⌋，则 G 中存在一条包含所有顶点的哈密顿回路。

- 定理3：最大流最小割定理
在网络流中，最大流的大小等于最小割的大小。

2. 网络流中的定理：

- 定理1：最大流最小割定理
在网络流中，最大流的大小等于最小割的大小。

- 定理2：Ford-Fulkerson 定理
网络流中最大流的大小等于任意一个增广路算法所得到的最大流的大小。

- 定理3：Dinic 定理
网络流中最大流的大小等于每个点的层次图中从源点到汇点的最短路数量。

- 定理4：Menger 定理
对于一个网络流中的有向图，一个顶点集合 S 到另一个顶点集合 T 的最小割大小等于 S 到 T 之间的最大流大小等于 S 和 T 之间的最小割数量。

- 定理5：Max-Flow Min-Cut 定理
网络流中最大流的大小等于图中所有 s-t 割中最小割的大小。