离散模型近代图论的历史可追溯到18世纪的七桥问题—穿过Königsberg城的七座桥，要求每座桥通过一次且仅通过一次。这就是著名的“哥尼斯堡7桥”难题。Euler1736年证明了不可能存在这样的路线。图的基本概念与模型图的基本概念与模型图的基本概念与模型图的基本概念与模型图的基本概念与模型图的基本概念与模型图的基本概念与模型图的基本概念与模型图的基本概念与模型图的基本概念与模型树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树树与图的最小树最短路问题最短路问题最短路问题算法例、用Dijkstra算法求下图从v1到v6的最短路。v1最短路问题最短路问题最短路问题最短路问题最大流问题（一）、基本概念1、设一个赋权有向图D=（V,E）,在V中指定一个发点vs和一个收点vt,其它的点叫做中间点。对于D中的每一个弧（vi,vj）∈E,都有一个非负数cij,叫做弧的容量。我们把这样的图D叫做一个容量网络，简称网络，记做D=（V，E，C）。网络D上的流，是指定义在弧集合E上的一个函数其中f(vi,vj)=fij叫做弧(vi，vj)上的流量。2、称满足下列条件的流为可行流：（1）容量条件：对于每一个弧（vi,vj）∈E有0≤fij≤cij。（2）平衡条件：对于发点vs，有对于收点vt，有对于中间点，有13(5)3、容量网络G，若为网络中从vs到vt的一条链，给定向为从vs到vt，上的弧凡与方向相同的称为前向弧，凡与方向相反的称为后向弧，其集合分别用和表示。f是一个可行流，如果满足：则称为从vs到vt的关于f的一条增广链。13(5)4、容量网络G=（V，E，C），vs为始点，vt为终点。如果把V分成两个非空集合使，则所有始点属于S，而终点属于的弧的集合，称为由S决定的截集,记作。截集中所有弧的容量之和，称为这个截集的容量，记为。13(5)13(5)（二）、求最大流的标号法标号过程：1．给发点vs标号（0，+∞）。2．取一个已标号的点vi，对于vi一切未标号的邻接点vj按下列规则处理：（1）如果边，且，那么给vj标号，其中：（2）如果边，且，那么给vj标号，其中：3．重复步骤2，直到vt被标号或标号过程无法进行下去，则标号结束。若vt被标号，则存在一条增广链，转调整过程；若vt未被标号，而标号过程无法进行下去，这时的可行流就是最大流。调整过程设1．令2．去掉所有标号，回到第一步，对可行流重新标号。求下图所示网络中的最大流，弧旁数为(1,0)13(5)13(11)设有5位待业者，5项工作，他们各自能胜任工作的情况如图所示，要求设计一个就业方案，使尽量多的人能就业。图中最大匹配问题，可以转化为最大流问题求解。在图中增加两个新点分别作为发点，收点。并用有向边把它们与原图中顶点相连，令全部边上的容量均为1。当网络流达到最大时，如果上的流量为1，就让作工作，此即为最大匹配方案。工人