筹学基础及应用第五版胡.pptxVIP

第6章图与网络分析Gra;6.1图的基本概念和模型单;一、基本概念图(graph)：;v1v2v3v4v5e1e2e;4、点v的次（或度，degre;链：图中保持关联关系的点和边的;v1v2v5v6v7v3v4e;单击此处添加大标题内容偶图（二;二、应用例有甲、乙、丙;解：构造一个六阶图如下：;6.2树图和图的最小部分树;证明（反证法）：2、树的性质设;n阶树必有n-1条边。单击此处;任何有n个点、n-1条边的连通;3、图的最小部分树（1）部分树;最小部分树（或最小支撑树）图G;最小部分树的求法1、原理图中与;SABCDE2、求法方法一：避圈法将;避圈法另一种做法：在剩余的边中;例：分别用两种避圈法构造下图的;3.V={S,A}重复第2;第二种做法求解过程：;方法二：破圈法求解步骤：从图;从剩余的子图中任找一回路，同样;破圈法的另一种解法：1.从;注意：一个图的最小部分树不唯一;§6.3最短路问题2、相关;3、狄克斯屈拉（Dijkstr;SABCDE（4）步骤在网络图中求s到t的;SABCDEV1V2V3V4V5V6V75;例求图中任意两点之间的最短距;4、矩阵算法求任意两点间;其中dij（1）=mi;其中dij（2）=mi;其中dij（3）=mi;说明：一般的对于D（k）=?;注意狄克斯屈拉算法矩阵算法优点;例：下图中v1—v7表示7个村;v1v2v3v4v5v6v7V;小学建在下列村子时，七个村子的;v1Sv2v3v4T§6.4;一、基本概念和基本结论弧的容量;4、容量网络（简称网络）：每条;6、流（flow）：加在网络中;10、网络的最大流：即使V(f;12、割的容量：割集中各弧的容;st4(4)8(7)μ+μ+μ;网络最大流的求法标号算法(Fo;3、步骤：对发点s标号：s（0;去掉所有标号，重复①。当t得到;8(8)v1sv2v3v4t7;8(8)v1sv2v3v4t7;例某河流中有4座岛屿B、C;ABCFED222131111;ABCFED2(1)2(0)2;ABCDEF;§6.5中国邮路问题问题：一;无标题;奇点：图中次为奇数的点称为奇点;步骤：两两连接所有的奇点，使之;v1v2v3v4v5v6v8v;§6.6网络模型的实际应用;解：用网络图模型描述，归结为最;例2：图示岛屿与河岸有数座桥相;ACFE311B2210102;例3：有3根相同的轴A1、A2