[高等教育]图论方法建模.pptVIP

第十二讲 图与网络建模方法; 主要内容; 三、最小生成树问题; 三、最小生成树问题; 三、最小生成树问题; 三、最小生成树问题; 三、最小生成树问题; 三、最小生成树问题; 三、最小生成树问题; 三、最小生成树问题; 四、匹配问题;这个问题可以用图的语言描述。其中 表示 工人, 表示工作，边 表示第i个人能 胜任第j项工作，这样就得到了一个二部图G，用点集 X表示{ }，点集Y表示{ } ,二部 图G=(X,Y,E)。上述的工作分配问题就是要在图G中找 一个边集E的子集，使得集中任何两条边没有公共端 点，最好的方案就是要使此边集的边数尽可能多，这 就是匹配问题。 ;二分图的概念;最大匹配;匈牙利算法;结论： P的路径长度必定为奇数，第一条边和最后一条边都不属于M。 M为G的最大匹配当且仅当不存在相对于M的增广路径。;;例1 求二部图G中的最大匹配。; M; 最大匹配就是：; 四、匹配问题;最佳匹配;KM算法;KM算法; 四、匹配问题;修改方法如下： 先将一个未被匹配的顶点u(u in {x})做一次增广 路，记下哪些结点被访问那些结点没有被访问。求 出d=min{lx[i]+ly[j]-w[i,j]}其中i结点被访问，j结点没 有被访问。然后调整lx和ly：对于访问过的x顶点， 将它的可行标减去d，对于所有访问过的y顶点，将 它的可行标增加d。修改后的顶标仍是可行顶标，原 来的匹配M仍然存在，相等子图中至少出现了一条 不属于M的边，所以造成M的逐渐增广。;KM算法步骤; 四、匹配问题; 五、旅行商问题; 五、旅行商问题; 五、旅行商问题; 五、旅行商问题; 五、旅行商问题; 五、旅行商问题; 五、旅行商问题; 六、最大流问题; 六、最大流问题; 六、最大流问题; 六、最大流问题; 六、最大流问题; 六、最大流问题; 六、最大流问题; 六、最大流问题; 六、最大流问题; 六、最大流问题; 六、最大流问题; 六、最大流问题; 六、最大流问题;问题解答?