资源描述：
《01introduction》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、15.082和6.855J2003春季网络最优化J.B.Orlin1欢迎!©欢迎来到15.082/6.855J©网络最优化介绍©授课教师：JamesB.Orlin©教材：《网络流：理论、算法与应用》(NetworkFlows:Theory,Algorithms,andApplications)作者：Ahuja,Magnanti和Orlin，被称为AMO.2快速概观©下一个：哥尼斯堡桥问题(KoenigsbergBridgeProblem)ò介绍网络和网络算法©一些课程管理问题©网络流和应用©计算复杂性©今天的课的总体目标是：为余下的课程设置氛围ò提供背景ò提供动机ò处理
2、一些课堂后勤3关于学生背景©本课的必需ò或者线性规划(LinearProgramming)(15.081J)ò或者数据结构(DataStructures)©有多少人已经学过线性规划？ò这个学期中，稍后将会有一节“复习”课©有多少人已经学过数据结构的课程？ò星期四有一节关于数据结构的“复习”课4课程方面©喜欢使用Powerpoint动画©“冷提问”作为一个加速学习算法的途径©与您的同伴交谈(教室中在您旁边的同学)©课堂时间：用来演示理论、算法、应用ò使用例子说明大部分证明轮廓(不是详细证明)ò详细的证明在教材中5哥尼斯堡的桥：欧拉(Euler)1736©“图论”开始于17
3、36©昂哈德.欧拉(LeonardEüler)ò访问哥尼斯堡ò人们疑惑是否有可能散步，且结束于开始散步的地方，恰恰经过每个桥一次ò通常情况下，这被认为是不可能的6哥尼斯堡的桥：欧拉(Euler)1736有没有可能从A出发，经过每一个桥恰好一次，并且最后回到A呢？7哥尼斯堡的桥：欧拉(Euler)1736概念化：陆地块是“结点”8哥尼斯堡的桥：欧拉(Euler)1736概念化：桥是“弧”9哥尼斯堡的桥：欧拉(Euler)1736是否存在一个从A开始，并结束于A的“通路”，经过每一条弧恰好一次？10符号和术语用在AMO中的网络术语无向图或无向网络有向图或有向网络网络(net
4、work)G=(N,A)结点集(nodeset)N={1,2,3,4}弧集(arcset)A={(1,2),(1,3),(3,2),(3,4),(2,4)}在无向图中，(i,j)=(j,i)11符号和术语路径(path)：例如：5,2,3,4.(或5,c,2,b,3,e,4)•无结点重复•忽略方向有向路径(directedpath)：例如：1,2,5,3,4(或1,a,2,c,5,d,3,e,4)•无结点重复•方向是重要的圈(cycle)(或circuit或loop)：1,2,3,1.(或1,a,2,b,3,e)•除了第一个结点是最后一个结点外，拥有2个或更多结点的路径
5、•忽略方向有向圈(directedcycle)：例如：(1,2,3,4,1)或1,a,2,b,3,c,4,d,1•无结点重复•方向是重要的12通路(walk)通路(walk)：结点和弧可以重复的路径有向通路(directedwalk)的例子：1-2-3-5-4-2-3-5如果一个通路的首结点和末结点是同一结点，则称此通路是闭合的(closed).回路(closedwalk)是结点和弧可重复的圈.13哥尼斯堡的桥：欧拉(Euler)1736是否存在这样的“通路”，它从A开始并结束于A，经过每一条弧恰好一次?这样的通路称为欧拉回路.14添加两桥创造这样的通路这就是这样的通路
6、.A,1,B,5,D,6,B,4,C,8,A,3,C,7,D,9,B,2,A注释：和B关联的弧的个数是B在通路上出现次数的2倍.15关于欧拉回路在无向图中的结点的度是关联此结点的弧的个数定理一个无向图是拥有欧拉回路当且仅当(1)每个结点的度数是偶数且(2)图是连通的(也就是说，任意两结点间都存在路径).16更多关于欧拉定理©两个必要条件ò任何欧拉回路“访问”每个结点偶数次ò任何欧拉回路都说明网络是连通的¢告诫：度数为零的结点©充分性条件ò假设适用于所有的拥有小于
7、A
8、条弧的图ò从某结点出发“散步”，直到发现一个圈C17更多关于欧拉定理©充分性条件ò从某结点出发“散步”，
9、直到发现一个圈Cò考虑G’=(N,AC)¢每个结点的度数是偶数¢每个组件是连接的ò因此，G’是欧拉回路的并ò通过添加C把G’连接成一个单独的欧拉回路18关于欧拉定理的评论1.它反映了在课堂上证明是如何做的，经常是以提纲挈领的形式说明关键思想.2.然而，这个证明不能导出一个有效率的算法.3.通常，我们关注于有效率的算法.1915.082/6.855J课程目标:1.为学生呈现当前最新解决网络流问题的理论和实践方面的知识.©自从1736年后，已经产生了很多2.提供给学生严谨的网络流算法的分析.©计算复杂性和最差情况分析3.帮助每个学生发展他的
