m图论模型简介.docVIP

图论模型简介 一、图及其矩阵表示 1、起源：哥尼斯堡七桥问题： 欧拉为了解决这个问题，建立数学模型：陆地——点，桥——边，得到一个有四个“点”，七条“边”的“图”。问题转化为能否从任一点出发一笔画出七条边再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画判定法则：图是连通的，且每个顶点都与偶数条边相关联（这种图称为欧拉图）。由此可以得出结论：七桥问题无解。 2、基本概念： 图（graph）：由顶点和边（又称线，边的两端必须是顶点）组成的一个结构。 邻接：一条边的两个端点称是邻接的；关联：边与其两端的顶点称是关联的。 无向图（graph）：边无方向的图；有向图（digraph）：边有方向的图。 路(path)：由相邻边组成的序列，其中中间顶点互不相同。 圈(cycle)：首、尾顶点相同的路，即闭路。 连通图（connected graph）：图中任意两顶点间都存在路的图。 树（tree）：无圈连通图 完全图（complete graph）：任意两个顶点之间都有边相连的无向图，记为Kn。 竞赛图（tournament）：由完全图给每条边定向而得到的有向图。 二部图（bipartite graph）：图的顶点分成两部分，只有不同部分顶点之间才有边相连。 图G的子图H（subgraph）：H是一个图，H的顶点（边）是图G的顶点（边）。 网络（Network）：边上赋了权的有向图。 3、图的矩阵表示 无向图 有向图 4、著名的图论问题 例1 最短路问题（shortest path problem） 出租车司机要从城市甲地到乙地，在纵横交错的路中如何选择一条最短的路线？ 例2 最小生成树问题（minimum-weight spanning tree problem） 为了给小山村的居民送电，每户立了一根电杆，怎样连接可使连线最短？ 例3 中国邮递员问题（chinese postman problem） 一名邮递员负责投递某个街区的邮件。如何为他设计一条最短的投递路线？ （二部图的）最优匹配问题（optimum matching） 在赋权二部图中找一个权最大（最小）的匹配。 例5 旅行推销员问题（traveling salesman problem－TSP） 一名推销员准备前往若干城市推销产品。如何为他设计一条最短的旅行路线？ 例6 网络流问题（network flow problem） 如何在一个有发点和收点的网络中确定具有最大容量的流。 二、求最短路的迪克斯特拉（Dijkstra）算法 基本思想是按距由近到远的顺序，依次确定到的各顶点的最短路和距离。为避免重复并保留每一步的计算信息，采用标号算法。 STEP1：，，，，; STEP2：（）， － , , 计算，记达到这个最小值的一个顶点为，令; STEP3：若，停止；否则，转STEP2。 例 求右图中从顶点u1到其它各 点的最短路及相应的路径. 求解过程列表如下： 顶点 前驱点 序号 1 2 3 4 5 6 7 8 1 1 6 1 2 5 3 5 1 0 ( ( ( ( ( ( ( 2 2 8 1 ( ( ( ( 3 2 8 ( ( 10 ( 4 8 3 ( 10 ( 5 8 6 10 12 6 7 10 12 7 9 12 8 12 三、求最小生成树的prim算法 设置两个集合和，其中用于存放的最小生成树的顶点，存放的最小生成树的边。令的初值为（假设构造最小生成树时，从顶点出发），的初值为。prim算法的思想是，从所有，的边中，选取具有最小权值的边，将顶点加入中，将边加入中，如此不断重复，直到时，最小生成树构造完毕。 prim算法如下： STEP1：，； STEP2：while ， end 四、求最大流的Ford－Fulkerson算法 此方法由Ford和Fulkerson于1957年提出，基本思想是不断寻找可增广路，不断增加网络的流量，直到无可增广路为止。这种方法分为以下两个过程： A．标号过程：通过标号过程寻找一条可增广路。 B．增流过程：沿着可增广路增加网络的流量。 这两个过程的步骤分述如下。 A．标号过程： （i）给发点标号为。 （ii）若顶点已经标号，则对的所有未标号的邻接顶点按以下规则标号： ① 若，且时，令，给顶点标号为， 若，则不给顶点标号。 ② 若，且，令，给标号为， 若，则不给标号。 （iii）不断地重复步骤（ii）直到收点被标号，