摘要：最大流问题是指在指定的条件下，要求通过网络的流量为最大的问题。在实际生活中有非常广泛的应用，交通运输网络中的人流、车流、物流，供水网络中的水流，电力传输中的能量流等问题都属于最大流问题。本论文简述了图论中关于图的一些基本概念及结论，包括最大流最小截定理。在此基础上，介绍了求解最大流问题的常见算法， Ford-Fulkerson标号法和Dinic算法，并用C语言程序将这两个算法加以实现。最后把设计好的程序应用于解决一个实际问题-垒球队员的指派问题。

关键字：图；最大流最小截定理；Ford-Fulkerson标号法；Dinic算法

目录

摘要

Abstract

第一章 绪论-2

2.1图的基本概念-3

2.2图的同构-3

2.3子图-4

2.4顶点的度-4

2.5路和连通-5

2.6加权图和最短路-7

第三章 标号法和Dinic算法-8

3.1最小截定理-8

3.1.1定义-8

3.1.2定理-8

3.2 标号算法和Dinic算法-10

3.2.1标号法-10

3.2.2 Dinic算法-10

3.2.3例题-12

第四章 应用-15

结论-18

参考文献-19

附录：算法实现代码-20

致谢-24