第七章图与网络优化0.问题的提出1.图的基本概念2.树3.最短路问题4.网络最大流问题5.最小费用最大流问题6.中国邮递员问题
第七章 图与网络优化 0.问题的提出 1.图的基本概念 2.树 3.最短路问题 4.网络最大流问题 5.最小费用最大流问题 6.中国邮递员问题
O问题的提出图与网络问题是运筹学中一个有广泛应用的分支;关于图的第一篇论文是瑞士数学家欧拉（E.Euler）在1736年发表的解决“哥尼斯堡(Konisberg)"七桥难题的论文;哥尼斯堡的一条河上七座桥接河中的两个小岛，人们如何才能只走过每座桥一次后达到原出发地
图与网络问题是运筹学中一个有广泛应用 的分支； 关于图的第一篇论文是瑞士数学家欧拉（ E.Euler）在1736年发表的解决“哥尼斯堡 (Konisberg)”七桥难题的论文； 哥尼斯堡的一条河上七座桥连接河中的两 个小岛，人们如何才能只走过每座桥一次 后达到原出发地。 0 问题的提出
哥尼斯堡(Konisberg)七桥问题-在图中找一条经过每边一次且仅一艺欧拉回路。一由点和边组成DDB-AB
D C B A 哥尼斯堡(Konisberg)七桥问题 -在图中找一条经过每边一次且仅一 次的路——欧拉回路。 D A B C 由点和边组成
一笔画问题下图1从A出发经过每条边一次且仅一次回到A点？下图2从A到B能否经过每条边一次且仅一次？BBAA图2图1
一笔画问题 图1 图2 A B A B 下图2从A到B能否经过每 条边一次且仅一次？ 下图1从A出发经过每条边 一次且仅一次回到A点？
欧拉链与欧拉圈若在连通图G中存在一条链（或一个圈）通过每条边一次且仅一次，则称这条链（或圈）为欧拉链（或欧拉圈）欧拉定理连通图G中存在欧拉圈的充分必要条件是G的每个顶点都是偶顶点：G中存在欧拉链充分必要条件是G中正好有两个奇顶点。福B
欧拉链与欧拉圈 若在连通图G中存在一条链（或一个圈）通过每条边一次 且仅一次，则称这条链（或圈）为欧拉链（或欧拉圈） 欧拉定理 连通图G中存在欧拉圈的充分必要条件是G的每个顶点都 是偶顶点；G中存在欧拉链充分必要条件是G中正好有两 个奇顶点。 D A B C